36. Other Sorting Method

칵테일 정렬(Cocktail Sort)은 버블 정렬과 비슷한데 앞의 원소와 뒤의 원소를 번갈아서 정렬한다. 시뮬레이션은 다음과 같다.

---

콤브 정렬(Comb Sort) 역시 버블 정렬과 비슷하지만 인접한 원소를 비교하지 않고 특정한 간격을 정해서 그 간격만큼 떨어진 원소를 비교한다. 이 간격을 좁혀나가면서 정렬을 수행한다.

---

트리 정렬(Tree Sort)은 주어지는 데이터로 이진 트리를 만들어 데이터를 정렬하는 방식이다. 힙 정렬과 비슷하지만 힙 정렬이 실행될 때는 트리의 형태에 제약이 있는 반면 트리 정렬이 실행될 때는 트리의 형태에 제약이 없다. 이진 트리가 만들어졌다면 중위 순회를 통해서 데이터의 순서를 정할 수 있다.

---

팀 정렬(Tim Sort)은 병합 정렬과 삽입 정렬을 결합한 것이다. 기본적으로 병합 정렬을 수행하되 정렬할 데이터의 수가 작으면 삽입 정렬을 사용해서 성능을 향상시킨다. 시뮬레이션은 다음과 같다.

---

인트로 정렬(Intro Sort)은 퀵 정렬과 힙 정렬을 결합한 것이다. 퀵 정렬을 기본적으로 실행하고 재귀호출의 깊이가 깊어지면 힙 정렬을 사용한다. C++의 std::sort() 함수에 가장 많이 사용되는 정렬 방법이 인트로 정렬이며 C#에도 사용된다. 시뮬레이션은 다음과 같다.

---

셸 정렬(Shell's Sort)은 삽입 정렬을 일정한 간격을 두고 수행한 다음 그 간격을 점차 좁혀나가면서 전체 데이터를 정렬하는 방법이다. 성능이 상당이 좋은 편이지만 잘 사용되는 편은 아니다.

---

보고 정렬(Bogo Sort; Stupid Sort)은 데이터를 랜덤으로 재배열한 후 정렬되었는지 검사하는 것을 반복하는 정렬 방법이다. 평균 시간복잡도가 $\Theta(n\times n!)$이고 최악의 경우 정렬이 끝나지 않을 수도 있다. 유전 알고리즘과 결합되어 사용되는 경우 외에는 사실상 사용되지 않는다.

---

보고보고 정렬(Bogobogo Sort)은 보고 정렬과 비슷하지만 데이터가 정렬되었는지 검사하는 것을 보고보고 정렬을 재귀호출하는 식으로 수행한다. 즉 현재 구간의 마지막 원소가 그 구간에서 가장 클 경우 나머지 원소들을 보고보고 정렬로 정렬하고, 그렇지 않다면 데이터를 다시 섞는 방식으로 작동한다. 평균 시간복잡도는 $\Theta(n!^{n!})$이라고 한다. 

---

대기 정렬(Sleep Sort)은 각각의 값에 해당하는 프로세스를 생성한 다음 그것들을 각각의 값만큼 슬립(Sleep)해서 데이터를 정렬하는 방법이다. 슬립이 끝나고 먼저 발생하는 프로세스의 값부터 차례로 나열하면 데이터를 정렬한 결과가 된다. 하지만 시스템의 상태에 따라 지연이 발생해서 순서가 바뀌는 등 정렬이 잘못될 수 있기 때문에 엄밀한 의미에서 알고리즘이라고 보기는 어렵다.

---

중력 정렬(Gravity Sort)은 정렬할 값들을 왼쪽이나 오른쪽으로 미는 방식으로 데이터를 정렬하는 방법이다. 시뮬레이션은 다음과 같다.

 

→ solved.ac tag: sorting