#08. 버블 정렬(Bubble Sort)

 

버블 정렬(Bubble Sort)

• 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

 

버블 정렬은 단 두 개의 요소만 정렬해 주는 좁은 범위의 정렬에 집중한다.

 

이 방법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

 

 

중첩 루프를 돌아야 하고, n 개의 값이 주어졌을 때 각 루프는 각각 (n-1) 번, (n-2) 번 반복되므로 버블 정렬의 실행 시간의 상한은 O(n^2)

 

 

또한 정렬이 되어 있는지 여부에 관계없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 된다.

 

 

---

References

 

dojang.io/mod/page/view.php?id=637%EF%BB%BF

C 언어 코딩 도장: 73.1 거품 정렬 구현하기