버블정렬(Bubble sort)

버블정렬

시간복잡도	공간복잡도
전체 요소를 순회하기 위해 N 인접 요소를 비교하기 위해 N N x N = O(N²)	인접 요소 비교 후 스왑을 하기 위해 O(1)

 

버블 정렬은 인접한 두 요소를 비교하며 큰 값을 뒤로 보내는 방식이다.

 

[4, 1, 3, 5, 6, 2]

 

예를 들어 이렇게 주어진 배열을 정렬한다고 해보자.

 

배열은 총 6개의 요소를 가지고 있다.

이때 배열의 0번 요소부터 인접한 두 개 요소를 비교한다.

 

첫번째 loop는 

0번과 1번, 1번과 2번, 2번과 3번, 3번과 4번, 4번과 5번을 비교한다. 만약 앞의 요소(i번째)가  뒤의 요소(i + 1번째)보다 크다면 둘의 위치를 바꾸고, 뒤의 요소가 더 크다면 다음 비교로 넘어간다.

 

두번째 loop는 다시

0번과 1번, 1번과 2번, 2번과 3번, 3번과 4번을 비교한다. 4번과 5번은 비교할 필요가 없다. 이미 이전 loop를 돌면서 배열 전체에서 가장 큰 수를 뒤로 보냈기 때문이다. 매번 loop를 돌 때마다 탐색 범위 내에서 가장 큰 수를 뒤로 보내기 때문에 매 loop마다 탐색 범위가 하나씩 줄어든다.  

 

 

구현

def bubble_sort(input_array):
    print('>>', input_array)
    for i in range(len(input) - 1, 0, -1):
        for j in range(i):
            print(f'i:{i} j:{j}')
            if input[j] > input[j + 1]:
                input[j], input[j + 1] = input[j + 1], input[j]
        print(input_array)

    return input_array;


if __name__ == '__main__':
    bubble_sort([7, 4, 5, 1, 3])
    
    
    
    
>> [7, 4, 5, 1, 3]
i:4 j:0
i:4 j:1
i:4 j:2
i:4 j:3
[4, 5, 1, 3, 7]
i:3 j:0
i:3 j:1
i:3 j:2
[4, 1, 3, 5, 7]
i:2 j:0
i:2 j:1
[1, 3, 4, 5, 7]
i:1 j:0
[1, 3, 4, 5, 7]

 

i는 이번 loop에서 몇 번 인덱스에 있는 요소까지 비교할지 결정한다.

비교할 요소, 비교할 요소 + 1번째 요소를 비교하기 때문에 i는 배열 길이의 -1로 설정한다.

그리고 이렇게 결정된 i를 이용하여 j는 0번부터 i번까지의 인접 요소들을 비교한다.

첫번째 전체 순회를 끝내면 다음 순회에서는 마지막 요소를 제외하고 비교해도 되기 때문에 i는 순회를 돌 때마다 1씩 줄여준다.

 

최적화

이전 순회에서 스왑이 몇 번째 요소에서 마지막으로 일어났는지 기억하는 변수를 사용하면 그 이후 요소들은 정렬이 된 것으로 판단하고 다음 순회에서는 그 이전 요소까지만 체크할 수 있다.

 

 

참고

https://www.dalecoding.com/algorithms/bubble-sort

거품 정렬 (Bubble Sort) | 달레코딩