정렬 알고리즘 (합병, 퀵, 힙, 쉘, 기수)

합병 정렬 (Merge Sort)

• 분할 정복 알고리즘 (Divide & Conquer) 이다.
• 주어진 배열을 원소 하나하나로 쪼갠다.
• 쪼갠 원소들을 정렬하면서 다시 합친다.

퀵 정렬 (Quick Sort)

• 분할 정복 알고리즘 (Divide & Conquer) 이다.
• 임의의 원소로 pivot을 정한다.
• pivot을 기준으로 pivot보다 작은 수끼리, pivot보다 큰 수끼리 새로운 배열을 만든다.
• 새로운 배열에서 다시 pivot을 정하고 같은 과정을 반복한다.

힙 정렬 (Heap Sort)

• 힙 자료구조를 사용한다.
• 오름차순으로 정렬할 땐 최소 힙 트리, 내림차순으로 정렬할 땐 최대 힙 트리를 사용한다.
• 오름차순으로 정렬하는 경우,
  • 완전 이진 트리 형태의 최소 힙을 만든다.
  • 삭제연산을 수행한다 -> 최댓값인 루트노드를 꺼낸다.
  • 트리를 재구성한다.
  • 모든 노드를 삭제할 때까지 반복한다. 

쉘 정렬 (Shell Sort)

• 삽입정렬을 보완한 알고리즘이다.
• 리스트를 부분 리스트로 쪼갠 후 삽입정렬을 이용하여 정렬한다.
• 더 적은 개수의 부분 리스트로 쪼갠 후 다시 삽입정렬을 이용하여 정렬한다.
• 부분 리스트의 개수가 1일 때까지 반복한다.

기수 정렬 (Radix Sort)

• 비교연산을 하지 않지만, 기수테이블을 위한 메모리가 필요하다.
• 0, 1, 2, ... 9번 큐를 준비한다.
• 일의 자리수가 0, 1, 2, ... 9 인지에 따라 분류하여 큐에 넣는다.
• 0번 큐부터 시작하여 데이터를 하나씩 꺼내어 하나의 배열로 만든다.
• 자릿수를 하나씩 높여가며 가장 높은 자리수까지 같은 작업을 반복한다.