버블 정렬 (Bubble Sort)

정렬이란?

데이터를 순서대로 나열하는 방법을 의미.

이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게도 한다.

 

버블 정렬

버블 정렬은 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, ... 이런식으로

(n - 1) 번째 자료와 n 번째 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다. 

 

ex) 첫 루프에서 두 개씩 비교해서 끝까지 가면 제일 큰 수가 마지막에 위치하게 된다.

이제 마지막 수는 고려하지 않아도 되므로 제외하고 다시 처음부터 마지막-1 번째까지 두 개씩 비교하고

다시 마지막-1 번째도 제외하고.. 를 반복해서 정렬시키는 방식이다.

https://www.google.com/url?sa=i&url=https%3A%2F%2Fgfycat.com%2Fko%2Fexaltedinconsequentialdwarfrabbit&psig=AOvVaw3VaULnsbKIQS9rzYXoze1R&ust=1602902999761000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCKCE3JKNuOwCFQAAAAAdAAAAABA9

 

코드로 구현해보자

input = [4, 6, 2, 9, 1]

위와 같은 숫자로 이루어진 배열이 있을 때 버블 정렬을 통해 정렬을 한다면 어떻게 코드를 짜야할까?

arr = [4, 6, 2, 9, 1]

# 0 1 2 3 0 1 2 0 1 0
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            print(j)
            
bubble_sort(arr)

이렇게 연달아 출력되는데 이는 우리가 비교하기 위해 구하려는 인덱스와 같다는걸 알 수 있다.

(j와 j+1 인덱스를 비교해 위치 교환)

이를 응용하면 다음과 같다.

input = [4, 6, 2, 9, 1]

def bubble_sort(arr):
    n = len(arr)
    for i in range(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

bubble_sort(input)
print(input)

 

버블 정렬의 시간 복잡도

버블 정렬은 2차 반복문이 나왔고, array의 길이 만큼 반복하고 있으므로 O(N²)의 시간 복잡도를 가진다고 볼 수 있다.