comparison-based sort

comparison-based sorting is the way to define comparison with ordering relationship.

Selection Sort

가장 크거나 작은 요소를 찾은 뒤, 리스트의 앞이나 뒤로 옮기는 작업을 반복하는 정렬 알고리즘. 직관적이여서 구현이 어렵지 않지만, 시간 복잡도가 O($n^2$)라는 단점이 있다. 공간 복잡도는 O(1)로 메모리 사용량은 적다. 그리고 stable하지 않아서 같은 층위의 요소들의 순서들까지 섞인다.

Bubble Sort

If there two adjacent elements are out of order, bubble sort will swap them and keep doing this by looping. 시간 복잡도가 O($n^2$)이고 공간 복잡도는 O(1)다. 버블 소트는 같은 요소들은 스왑하지 않기 때문에 stable하다. 쉽지만 느려서 현업에서 잘 안쓰인다.

Insertion Sort

작은 수를 찾으면 앞으로 옮기는 일을 반복하는 알고리즘.

리스트를 돌면서 순서에 맞지 않는 요소를 발견하면 그 요소를 이전 순서로 이전으로 당겨준다. 이전 순서로 당겨진 요소의 위치가 부적절 한 경우, 즉 다시 당겨져야 하는 경우 제 위치를 찾을 때까지 당겨준다. 이를 끝까지 반복한다.

'Insertion Sort는 최악의 경우 O($n^2$)이다. 하지만 2가지 시나리오의 경우 매우 빠른데, 하나는 거의 정렬이 완료된 배열인 경우이고 다른 하나는 배열의 크기가 작을 경우다. 그래서 일반적으로 많은 정렬 함수가 정렬할 대상의 사이즈의 크기를 확인한 후, 일정 수준보다 낮을 경우 insertion sorting을 적용한다.