[Python] 알고리즘 기초 : 버블정렬

파이썬 공부할 겸 알고리즘 문제 풀자고 했당.

 

 

버블 정렬 코드 예제

버블 정렬은 인접한 두 값을 비교하면서 큰 값을 뒤로 보내는 방식

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):  # 총 n-1번 반복
        for j in range(n - i - 1):  # 비교 범위를 점점 줄임
            if arr[j] > arr[j + 1]:  # 앞이 뒤보다 크면
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 값 교환
    return arr

# 테스트
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print("정렬된 리스트:", sorted_numbers)

 

코드 분석

• n = len(arr)

배열의 길이를 가져옵니다.

• for i in range(n - 1)

리스트를 반복하면서 마지막 요소는 정렬 범위에서 제외합니다.

• for j in range(n - i - 1)

매 반복마다 가장 큰 값이 뒤로 밀리므로 비교 범위를 점점 줄입니다.

• if arr[j] > arr[j + 1]

현재 값이 다음 값보다 크면 위치를 바꿉니다.

 

 

실습

문제 1 : 숫자리스트 [10, 2, 3, 5, 4]를 정렬하세요.

문제 2 : 버블 정렬을 사용해 내림차순 정렬을 하려면 어떻게 수정해야 할까요?

def bubble_sort(arr, descending=False):
    n = len(arr)
    for i in range(n - 1):  # 배열 크기 - 1 만큼 반복
        for j in range(n - i - 1):  # 정렬 범위 점점 줄이기
            if (descending and arr[j] < arr[j + 1]) or (not descending and arr[j] > arr[j + 1]):
                # 조건에 따라 값 교환
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 테스트
numbers = [10, 2, 3, 5, 4]
print("오름차순 정렬:", bubble_sort(numbers))  # 오름차순 정렬
print("내림차순 정렬:", bubble_sort(numbers, descending=True))  # 내림차순 정렬