[c++] 알고리즘 개념공부 :: 정렬 (개요)

정렬

 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제가 '정렬'이다. 보통 컴퓨터에서는 탐색을 위해서 정렬을 수행한다. 탐색은 정렬을 통해 하는 것보다 더 강력한 알고리즘이 있지만, 한 번 데이터를 정렬해두면 다음부터는 이진 탐색이라는 빠른 알고리즘을 몇 번이고 사용할 수 있기 때문에 유용하다.

 그래서 주어진 무작위의 데이터를 정렬하는 것에 많은 연구자들이 방법을 내놓았는데, 앞으로 설명할 6개의 정렬 알고리즘이다. 그 외에도 많은 정렬 알고리즘이 존재한다.

 모든 정렬의 설명에 앞서서 예제로 설명할 데이터는 다음 그림과 같이 무작위로 배치되어있는 1~7의 데이터이다.

 정렬 알고리즘의 시간 복잡도는 비교 + 이동으로 측정한다.

 

특성

정렬 알고리즘은 여러 기준에 따라 나뉠 수 있다.

• 시간 복잡도에 따른 분류
  • 단순하지만 비효율적인 O(n^2) 알고리즘 : 삽입 정렬, 선택 정렬, 버블 정렬 등
  • 복잡하지만 효율적인 O(nlgn) 알고리즘 : 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등
• 안정성에 따른 분류
  • 안정 정렬 : 정렬 후에도 동일한 키 값을 갖는 원소의 상대적 위치가 바뀌지 않음
  • 불안정 정렬 : 안정 정렬과 반대

선택 정렬, 버블 정렬, 삽입 정렬

퀵 정렬, 합병 정렬

힙 정렬, 쉘 정렬