[Algorithm] Bubble Sort(버블 정렬)

Bubble Sort

인접한 두 원소를 비교하고, 비교 조건에 따라 두 자리를 교체하며 정렬을 진행하는 알고리즘이다.
안정정렬에 속한다.

구현 방법

전체 리스트의 길이에서 1씩 줄여가며 순환, 순환하면서 두 원소를 비교하여 swap을 진행한다.
1번의 순환을 진행하고 나면 탐색한 리스트 내의 가장 큰 값이 젤 뒤에 들어가게된다. 이 과정을 반복하면 정렬이 완성된다.

구현(Python)

#bubble sort
input_array = [19, 16, 6, 34, 38, 41, 49, 28, 36, 45, 43]
for steps in reversed(range(len(input_array))):
    for step in range(steps):
        if input_array[step] > input_array[step+1]:
            input_array[step], input_array[step+1] = input_array[step+1], input_array[step]

print(input_array)

시간복잡도

전체 길이가 n일때, (n-1)+(n-2)+(n-3)+...+1 의 계산이 필요하므로 O(n^2)의 시간복잡도가 나온다.
현재 상태와 관계없이 계산은 해야하기 때문에 최선, 최악의 경우 둘 다 O(n^2)이 소요된다.

공간복잡도

추가 공간을 쓰지 않고 리스트 내에서 서로 swap 하며 진행하기 때문에
전체 길이가 n일때, O(n)이다.