방학도 했겠다, 정렬 알고리즘을 다뤄보고자 한다.

지난 시간 잠깐씩 다뤘던 것들까지 수정할 수 있으면 다같이 정리해보고 싶다. 기초적인 알고리즘들부터 다루면 어떨까 싶다. 사람들한테 제일 친숙한건 Selection, Insertion 정도일텐데 Bubble부터 다루는게 된 이유는 딱히 없다. 그냥 제일 자주 쓰기도 하고, 편해서...

사람 손은 두 개다. 양 손에 집어든 물건의 대소 비교를 진행할 수 있다.이번 정렬도 딱 그 컨셉으로 진행된다. Bubble이라고 만든 것은 서로 이웃한 item 두 개를 비교하면서 큰 것과 작은 것을 분류해가는 정렬이다.

정렬되지 않은 list 가 있을 때, index가 가장 낮은 두 item을 Bubble로 만든다. 더 큰 것을 더 큰 index를 가지도록 서로 순서를 바꾸거나 바꾸지 않는 작업을 반복하면서 list를 순회한다. 반복이 한 번 종료되면 가장 큰 item은 가장 큰 index를 가지게 될 것이다. 이제 list 길이 상한을 하나씩 줄여가면서 여러 번 반복하면 전체 list는 정렬된다.

전체 list 길이가 n이라고 하면 n-1 번 순회, n-2 번 순회, ... , 1번 순회 하는 과정을 반복하게 된다.

따라서 시간 복잡도를 가진다.