정렬2 : 분할정복을 이용한 정렬

분할정복을 이용한 정렬

• Merge Sort
• Quick Sort

 

 

Merge Sort

merge sort

• pseudo algorithm

1. 정렬할 데이터 집합을 반으로 나눈다

2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1번 작업을 반복한다

3. 원래 같은 집합에서 나뉘어진 두 개의 하위 데이터 집합의 원소들을 크기 순서에 맞춰 정렬하고 병합.

4. 데이터 집합이 하나가 될 때까지 3번작업을 반복

 

• 시간복잡도
  • worst : O(nlogn)
  • average : O(nlogn)
  • best : O(nlogn)

 

Quick Sort

quick sort

 

• 분할 정복 알고리즘을 이용한 매우 빠른 수행 속도를 자랑하는 정렬
• 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• psuedocode

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽, 피벗보다 큰 요소들은 피벗의 오른쪽으로 나눈다 
3.  피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   • 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
   • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

• 시간복잡도
  • worst : O(n^2)
  • average : O(nlogn)
  • best : O(nlogn)