정렬 알고리즘 - 버블 정렬 - Bubble sort

버블 정렬은 정렬할 항목 목록을 반복적으로 살펴보고 인접한 요소를 비교하여 순서가 잘못된 경우 교체하는 간단한 정렬 알고리즘입니다. 이 알고리즘의 이름은 작은 요소가 목록의 맨 위로 '버블'되는 방식에서 유래했습니다.

버블 정렬의 기본 개념은 다음과 같습니다:

목록의 시작 부분부터 시작합니다.
처음 두 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 서로 바꿉니다.
다음 요소 쌍(즉, 두 번째 및 세 번째 요소)으로 이동하여 2단계를 반복합니다.
목록 끝에 도달할 때까지 이 과정을 계속합니다.
목록의 시작 부분에서 다시 시작하여 스왑이 필요하지 않을 때까지 1~4단계를 반복합니다.
다음은 버블 정렬이 어떻게 작동하는지에 대한 예시입니다:

다음과 같은 숫자 목록이 있다고 가정해 보겠습니다:

[5, 2, 9, 1, 5]

처음 두 요소(5와 2)를 비교하는 것부터 시작하여 5가 2보다 크므로 서로 바꿉니다. 이제 목록은 다음과 같습니다:

[2, 5, 9, 1, 5]

그런 다음 다음 두 요소(5와 9)를 비교하는데, 이미 올바른 순서이므로 그대로 둡니다. 목록의 끝에 도달할 때까지 요소를 계속 비교합니다.

이 시점에서 목록에 대한 한 번의 통과를 완료했습니다. 그런 다음 목록의 시작 부분에서 다시 시작하여 더 이상 스왑이 필요하지 않을 때까지 이 과정을 반복합니다. 이 경우 목록이 완전히 정렬되기 전에 세 번의 패스를 더 수행해야 합니다:

패스 2: [2, 5, 1, 5, 9](5와 1로 스왑)
패스 3: [2, 1, 5, 5, 9](5와 1, 5와 2로 교체)
패스 4: [1, 2, 5, 5, 9] (2와 1로 교체)

이제 목록이 오름차순으로 정렬됩니다.

버블 정렬은 이해하고 구현하기는 쉽지만 큰 목록에는 그다지 효율적이지 않습니다. 시간 복잡도가 O(n^2)이므로 대규모 데이터셋을 정렬하는 데 적합하지 않습니다.

 

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already sorted
        for j in range(n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

 

 

bubble_sort 함수는 배열 arr을 입력으로 받아 정렬된 배열을 반환합니다.

이 함수는 변수 n을 입력 배열 배열의 길이로 초기화하는 것으로 시작합니다.

외부 for 루프는 배열의 각 요소를 반복합니다.

내부 for 루프는 인접한 요소를 비교하고 순서가 잘못된 경우 요소를 바꿉니다. 외부 루프를 반복할 때마다 가장 큰 요소가 배열의 끝에 오도록 보장되므로 다시 비교할 필요가 없으므로 루프는 n-i-1까지 올라갑니다.

어떤 요소가 다음 요소보다 크면 if 문은 Python의 튜플 언패킹 구문을 사용하여 요소를 바꿉니다.

두 루프가 모두 반복을 완료하면 함수는 정렬된 배열을 반환합니다.

다음은 bubble_sort 함수 사용 예시입니다:

 

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print(sorted_arr)

이 코드는 원본 배열의 정렬된 버전인 [11, 12, 22, 25, 34, 64, 90]을 출력합니다.