[Data Structure] 정렬 알고리즘(sort algorithm)

---

정렬

 

 

여러가지 값들이 규칙없이 모여있을 때 이를 규칙에 맞게 정렬해야 한다면 여러가지 정렬 알고리즘을 사용할 수 있다. 위 영상은 여러가지 정렬 알고리즘을 시각화한 것이다.

정렬은 효율적인 탐색에도 필수적인데, 예를 들어 사전에서 단어들이 알파벳 순서가 아니라 랜덤으로 섞여 있다고 가정해보자. 알파벳 순으로 정렬되어 있을 때는 우리는 알파벳이 어디 있는지 알 수 있지만, 랜덤으로 섞여 있다면 사전의 모든 페이지를 확인해야 할 것이다.

일반적으로 정렬 대상을 레코드(record)라 하고, 레코드는 필드(field)라는 레코드보다 작은 단위로 구성된다. 이때 키필드(key field)를 기준으로 레코드를 구별하고 정렬한다.

모든 경우에 최적인 정렬 알고리즘은 없다. 레코드 수, 레코드의 크기, 키의 특성, 가용 가능한 메모리 등 여러가지 것들을 고려하여 최적의 정렬 알고리즘을 선택해야 한다. 또한 정렬 알고리즘을 구현하여 사용해야 할 경우는 구현이 복잡한지, 간편한지도 생각해야 할 것이다.

내부 정렬(internal sorting)은 모든 데이터가 주기억장치에 저장된 상태에서 정렬하는 것이고, 외부 정렬(external sorting)은 외부기억장치에 대부분 데이터가 있고, 일부만 주기억장치에 저장된 상태에서 정렬하는 것이다.

정렬 알고리즘에서 안정성(stability)은 동일한 키 값을 가지는 레코드들의 상대적 위치가 정렬이 끝난 후에도 바뀌지 않는 것을 말한다. 즉 바뀌지 않으면 안정적인 정렬 알고리즘인 것이고, 바뀐다면 안정적이지 않은 정렬 알고리즘인 것이다. 일반적으로 퀵 정렬, 힙 정렬, 선택 정렬, 셸 정렬은 안정적이지 않은 정렬 알고리즘이다. 단 어떤 정렬은 구현 시 안정적으로 바꿀 수도 있다.

 

---

대표적인 정렬 알고리즘 시간복잡도

 

정렬 알고리즘 (링크있음)	최선	평균	최악
버블 정렬	$ \mathcal{O} (n^2) $	$ \mathcal{O} (n^2) $	$ \mathcal{O} (n^2) $
선택 정렬	$ \mathcal{O} (n^2) $	$ \mathcal{O} (n^2) $	$ \mathcal{O} (n^2) $
삽입 정렬	$ \mathcal{O} (n) $	$ \mathcal{O} (n^2) $	$ \mathcal{O} (n^2) $
셸 정렬	$ \mathcal{O} (n) $	$ \mathcal{O} (n^{1.5}) $	$ \mathcal{O} (n^{1.5}) $
퀵 정렬	$ \mathcal{O} (n \log_2 n) $	$ \mathcal{O} (n \log_2 n) $	$ \mathcal{O} (n^2) $
힙 정렬	$ \mathcal{O} (n \log_2 n) $	$ \mathcal{O} (n \log_2 n) $	$ \mathcal{O} (n \log_2 n) $
병합 정렬	$ \mathcal{O} (n \log_2 n) $	$ \mathcal{O} (n \log_2 n) $	$ \mathcal{O} (n \log_2 n) $
기수 정렬	$ \mathcal{O} (kn) $	$ \mathcal{O} (kn) $	$ \mathcal{O} (kn) $
계수 정렬	$ \mathcal{O} (n+k) $	$ \mathcal{O} (n+k) $	$ \mathcal{O} (n+k) $