2-2 bubble sort 구현, big O

버블소트의 구현과, 빅오에 대해 알아보겠습니다.

 

아래와 같이 코드로 한번 구현해봤습니다.

 

얘의 출력 과정을 알아보면 아래와 같이 찍힙니다.

 

처음 버블 소트를 봤다면, 머리속에서 코드가 출력되는 부분이 시뮬레이션 잘 안될 수 있습니다.

 

아래의 출력물을 참고하시면 더 좋을 듯 합니다.

 

-----------
i = 0
j = 0
list[j] = 64    list[j+1] = 34
j = 1
list[j] = 64    list[j+1] = 25
j = 2
list[j] = 64    list[j+1] = 12
j = 3
list[j] = 64    list[j+1] = 22
j = 4
list[j] = 64    list[j+1] = 11
j = 5
list[j] = 64    list[j+1] = 90
-----------
i = 1
j = 0
list[j] = 34    list[j+1] = 25
j = 1
list[j] = 34    list[j+1] = 12
j = 2
list[j] = 34    list[j+1] = 22
j = 3
list[j] = 34    list[j+1] = 11
j = 4
list[j] = 34    list[j+1] = 64
-----------
i = 2
j = 0
list[j] = 25    list[j+1] = 12
j = 1
list[j] = 25    list[j+1] = 22
j = 2
list[j] = 25    list[j+1] = 11
j = 3
list[j] = 25    list[j+1] = 34
-----------
i = 3
j = 0
list[j] = 12    list[j+1] = 22
j = 1
list[j] = 22    list[j+1] = 11
j = 2
list[j] = 22    list[j+1] = 25
-----------
i = 4
j = 0
list[j] = 12    list[j+1] = 11
j = 1
list[j] = 12    list[j+1] = 22
-----------
i = 5
j = 0
list[j] = 11    list[j+1] = 12

 

여기까지 했으면, 버블소트가 이해되셨을 것이라 생각합니다.

 

시간 복잡도인 BIg-O는 반복문이 중첩으로 들어갔기 때문에 O(n^2)입니다.

 

n-1, n-2, … , 2, 1 번 = n(n-1)/2 = O(n^2)

 

이 것을 조금 다르게 구현할 수도 있는데 swapped라는 애를 만들어줍니다.

 

이 swapped 이라는 애를 통해, 정렬이 잘 되어 있으면 반복문을 그만 돌리도록 해줍니다.

 

자, bubbleSort2라는 애를 만들었는데 얘를 그냥 bubbleSort랑 비교해보겠습니다.

 

case1 - bubbleSort

 

list = [1, 2, 3, 5, 4, 8, 7]
bubbleSort(list)

 

 

 

case2 - bubbleSort2

 

list = [1, 2, 3, 5, 4, 8, 7]
bubbleSort2(list)

 

 

이렇게 확연히 실행이 줄어든 것을 볼 수 있습니다 :)