2-1 bubble sort 원리

처음으로 해볼 정렬은 버블 정렬 bubble sort 입니다. 버블 정렬하면 저는 현아의 퍼블팝밖에 생각이 안나네요... https://www.youtube.com/watch?v=bw9CALKOvAI

 

자, 버플팝이 중요한게 아니라 버블 정렬을 해보겠습니다.

 

버블 정렬의 이론은, 옆에 있는 원소와 비교해서 정렬해주는 알고리즘입니다. 거품이 비비듯이 움직인다고 해서 버블소트라는 이름을 가지고 있는 것으로 알고 있습니다.

 

오른쪽에 있는 애가, 왼쪽에 있는 애보다 작으면, 위치를 바꿔줍니다. 

 

예를 들면, 아래와 같은 애들을 순서대로 정렬하고 싶은데, 버블 소트를 이용해서 한번 해 보겠습니다.

 

과정들을 쭉 지켜보시면 버블 소트가 어떻게 동작하는지 알 수 있을 겁니다.

 

일단 1라운드

 

이렇게 앞의 2개 비교해서 바꿔주고, 이 작업을 반복해나갑니다.

 

5와 8중에 오른쪽에 있는 8이 5보다 크므로, 여기서는 순서를 체인지 하지 않습니다.

여기까지 했으면 1라운드가 끝났습니다.

 

맨 큰 숫자가 오른쪽으로 정렬되었고, 2라운드에서 1,4,2,5 부분을 다시 정렬합니다.

 

 

 

 

여기까지 하면 2라운드 끝.

 

이제 원리는 이해 하셨을 것이라고 생각합니다.

 

나머지 부분도, 1,2,4 이렇게 3개를 차례대로 정렬하면서 가장 큰 순서대로 하나씩 오른쪽으로 정렬하는 과정을 거치면 버블 정렬이 끝납니다.

 

이제 버블 정렬의 원리를 이해하셨으니, 코드를 작성하고 시간복잡도를 알아보겠습니다.