버블 정렬 복습(Bubble Sort)

오늘은 버블 정렬에 대해 배워 보았습니다. 분명 1,2 학년때 다 한건데 3학년이 된 지금에서야 다시 복습을 하는게 바보같다는 생각이 들 때도 있지만 지금이라도 열심히 해야지라는 생각이 듭니다. 

 

버블 정렬은 O(N^2) 인 세개의 정렬(선택,버블,삽입) 중에서도 가장 비효율적인 정렬입니다. 

 

버블정렬은 무조건 옆에 요소와 비교하고 교환합니다. 여기서 무조건 교환을 하기 때문에 알고리즘의 비효율적인 부분이 커집니다. 애를 들어 설명해보겠습니다.

 

 

3 1 4 5 2

 

라는 배열이 존재합니다.

 

첫번째

첫번째 3 을 옆에 요소 1과 비교 합니다. 1이 더 크기 때문에 교환합니다. 

 

1 3 4 5 2 

 

그리고 두번째 수 3을 다시 4와 비교한 후 크면 교환합니다. 여기선 4보다 작기 때문에 교환을 하지는 않습니다.

 

1 3 4 5 2

 

세번째 수를 5와 비교합니다. 또 변하진 않습니다. 

 

1 3 4 5 2 

 

그럼 4번째 수 5를 2와 다시 비교합니다. 

 

1 3 4 2 5

 

버블 정렬은 한번 정렬을 마치면 가장 마지막 원소가 가장 큰 수가 됩니다.  그래서 선택 정렬과는 다르게 2번째로 마지막 원소까지 정렬을 진행합니다. 

 

 

두번째 

1과 3을 비교합니다. 

 

1 3 4 2 5

 

3 과 4를 비교합니다. 

 

1 3 4 2 5 

 

4 과 2를 비교합니다.

 

1 3 2 4 5 

 

 

 

두번째 반복에서는 또다시 두번째로 큰 수인 4가 제자리를  찾아갑니다. 

 

 

세번째 

1과 3을 비교합니다. 

 

1 3 2 4 5

 

3 과 2를 비교합니다.

 

1 2 3 4 5 

 

세번째 반복에서는 또 다시 세번째로 큰 수인 3이 제자리를 찾아갑니다. 

 

이 예시에서는 정렬이 완료됐지만 실제로 컴퓨터에서는 계속 4번째 비교가 진행됩니다. 

4 + 3 + 2 +1 비교가 진행됐습니다. 

일반화하면 

 

(n-1)n/2 즉 O(N^2) 의 시간복잡도입니다. 

선택정렬과 시간복잡도는 동일하지만 가장 작은 수를 찾고 한번의 Swap을 진행하는 선택정렬과 달리 버블정렬은 매번 비교하고 Swap을 진행하기 때문에 수행시간에서 차이가 많이 납니다. 

 

 

c와 파이썬으로 구현을 해보았습니다.

 

버블정렬 C

 

 

버블정렬 파이썬