Sorting (Heap, Quick, Merge Sort)

Heap Sort

Heap Tree에서의 Heap을 사용 (Max Heap 또는 Min Heap) 따라서 complete binary tree 임 Max Heap일 때 parent node는 child node(subtree)의 key보다 무조건 큼 binary search tree가 아님 Tree의 Heap은 정렬을 위함이 아닌 Insert와 Delete를 위함 Max(Min) Heap의 내용은 Heap 에서 확인

1. Max(Min) Heap을 만든 다음 모든 데이터를 넣음

2. (Max Heap이라 할 때) 만든 heap tree에서 root node를 지우고 정렬하고자 하는 list에 지운 root node를 넣음

3. (Max Heap이라 할 때) heap tree를 재조정해서 루트를 결정한 다음, 다시 루트를 지우고 list에 해당 값을 넣음

4. 이 방식을 트리가 없어질 때 까지 진행

퍼포먼스

시간복잡도는 O(nlog₂n)

• n은 트리의 노드 개수

Heap tree의 전체 높이가 log₂n(완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 Heap tree를 재구성하는데에 log₂n 만큼 소요됨

insertion 또는 deletion 하는 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 소요됨

저장공간이 적게 필요

• Heap tree를 구성하는 공간만 필요함 (+ 정렬된 값을 저장하는 리스트)

빠르고 저장공간이 적게 필요하기에 임베디드 시스템에 유용

Quick Sort

정렬하고자 하는 값 중, 1개를 선택하고 선택된 값을 기준으로 작으면 왼쪽, 크면 오른쪽으로 나눈 다음 2개로 분할한 리스트에서 각 정렬한 후 합침.

• 위와 같이 분할 후, 합치는 방식으로 divide and conquer 라고 부름

  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

  • 분할 정복 방법은 대개 순환 호출을 이용하여 구현

• merge sort와 다르게 리스트를 균등하지 않게 분할함

Quick Sort 종류 Plain Quick Sort Quick sort with randomized pivot In-place quick sort

1. 정렬하고자 하는 리스트에서 값 1개를 선택 (선택한 값을 pivot이라 부름)

• 보통 정렬하고자 하는 리스트의 가장 왼쪽, 중간 또는 가장 오른쪽을 선택

2. 다음 pivot을 중심으로 pivot 보다 작으면 왼쪽 pivot 보다 크면 오른쪽으로 분류 (divide)

3. 분류를 한 다음, 왼쪽과 오른쪽으로 분류된 값들 중, 각각 가장 왼쪽에 있는 수를 다시 pivot으로 잡고 다시 분류를 함.

• 만약 수가 변하지 않으면 다음 수를 pivot으로 잡음
• 가장 왼쪽에 있는 수가 바뀌었을 시, 해당 수를 pivot으로 잡고 다시 정렬

4. 더이상 정렬할 값이 없으면 분류한 값을 새로운 리스트에 담고 종료

예시

예시2

예시3

항상 마지막의 수를 선택

아래와 같은 방식이 in-place quick sort로 추가적인 저장공간이 필요없음

• in-place : 입력된 리스트 내부에서 정렬이 일어남

예시4

상세 예시

6 3 8 7 9 2 1 5 pivot은 P, 왼쪽에서 시작하는 값은 L, 오른쪽에서 시작하는 값은 R이라 가정 L은 P보다 큰 값이 나올때까지 오른쪽으로 이동 R은 P보다 작거나 같은 값이 나올때까지 왼쪽으로 이동 L이나 R이 위 공식이 성립한다면 해당 값에 멈춤 L과 R이 전부 멈췄을 때 위치를 변경 R의 인덱스가 L보다 작아질 경우 P와 R 값의 위치를 변경 L과 R이 동일한 인덱스에 있을 경우, P와 R 값의 위치를 변경

pivot을 리스트의 가장 왼쪽 값을 선택하는 경우

1. 초기 값 세팅

6, 3, 8, 7, 9, 2, 1, 5 Pㅤㅤㅤㅤㅤㅤㅤㅤ R L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5 PㅤㅤL ㅤㅤㅤㅤㅤ R

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8 PㅤㅤL ㅤㅤㅤㅤㅤ R

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8 PㅤㅤㅤL ㅤㅤㅤR

5. 두 값의 위치 변경

6, 3, 5, 1, 9, 2, 7, 8 PㅤㅤㅤL ㅤㅤㅤR

6. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 1, 9, 2, 7, 8 Pㅤㅤㅤㅤ L R

7. 두 값의 위치 변경

6, 3, 5, 1, 2, 9, 7, 8 Pㅤㅤㅤㅤ L R

8. 해당 위치부터 다시 2번내용

6, 3, 5, 1, 2, 9, 7, 8 Pㅤㅤㅤㅤ R L

9. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

2, 3, 5, 1, 6, 9, 7, 8 ㅤㅤㅤㅤㅤP

1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행 (왼쪽 먼저 진행)

2, 3, 5, 1, 6, 9, 7, 8 PㅤㅤㅤR L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

2, 3, 5, 1, 6, 9, 7, 8 P LㅤㅤR

3. 두 값의 위치 변경

2, 1, 5, 3, 6, 9, 7, 8 P LㅤㅤR

4. 해당 위치부터 다시 2번내용 수행

2, 1, 5, 3, 6, 9, 7, 8 P RㅤL

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 2, 5, 3, 6, 9, 7, 8 ㅤP

1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행

• 왼쪽에 값이 1개밖에 없으므로 오른쪽만 진행

1, 2, 5, 3, 6, 9, 7, 8 ㅤㅤ P R ㅤㅤ L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 5, 3, 6, 9, 7, 8 ㅤㅤ P R ㅤㅤㅤ L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 9, 7, 8 ㅤ ㅤㅤ P

1. 처음 pivot을 6으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 9, 7, 8 ㅤㅤㅤㅤㅤㅤ PㅤㅤR ㅤㅤㅤㅤㅤㅤ L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 9, 7, 8 ㅤㅤㅤㅤㅤㅤ PㅤㅤR ㅤㅤㅤㅤㅤㅤㅤㅤㅤ L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 8, 7, 9 ㅤㅤㅤㅤㅤㅤㅤㅤㅤP

P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

1, 2, 3, 5, 6, 8, 7, 9 ㅤㅤㅤ ㅤㅤㅤ P R ㅤㅤ ㅤㅤㅤㅤ L

1. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 8, 7, 9 ㅤㅤ ㅤㅤㅤㅤ P R ㅤㅤㅤㅤㅤㅤㅤㅤL

2. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9 ㅤㅤㅤㅤㅤㅤㅤㅤP

Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pivot을 리스트의 중간 값을 선택하는 경우

1. pivot을 리스트의 인덱스 중간으로 선택

6, 3, 8, 7, 9, 2, 1, 5 L ㅤㅤㅤPㅤㅤㅤㅤ R

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5 ㅤ ㅤ L Pㅤㅤㅤㅤ R

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8 ㅤ ㅤ L Pㅤㅤㅤㅤ R

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8 ㅤㅤㅤㅤP LㅤㅤR

5. 두 값의 위치 변경

6, 3, 5, 7, 1, 2, 9, 8 ㅤㅤㅤㅤP LㅤㅤR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 1, 2, 9, 8 ㅤㅤㅤㅤP ㅤ R L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

6, 3, 5, 2, 1, 7, 9, 8 ㅤㅤ ㅤㅤㅤㅤP

1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

• pivot을 리스트의 인덱스 중간으로 선택

6, 3, 5, 2, 1, 7, 9, 8 L ㅤ PㅤㅤR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 5, 2, 1, 7, 9, 8 L ㅤ PㅤㅤR

3. 두 값의 위치 변경

1, 3, 5, 2, 6, 7, 9, 8 L ㅤ PㅤㅤR

4. 해당 위치부터 다시 2번내용 수행

1, 3, 5, 2, 6, 7, 9, 8 ㅤㅤPㅤR L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 3, 2, 5, 6, 7, 9, 8 ㅤ ㅤㅤP

1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

• pivot 5의 우측 리스트는 값이 1개이므로 왼쪽만 진행

1, 3, 2, 5, 6, 7, 9, 8 L P R

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 3, 2, 5, 6, 7, 9, 8 ㅤP R ㅤㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 9, 8 ㅤㅤP

1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

• 좌측의 경우 1, 2인데 1에 P와 R이 동일한 위치가 되므로 변경되는 값은 없음

1, 2, 3, 5, 6, 7, 9, 8 P L R

1. 처음 pivot을 7으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 7, 9, 8 ㅤㅤㅤㅤㅤㅤㅤㅤP R ㅤㅤㅤㅤㅤㅤㅤㅤL

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 7, 9, 8 ㅤㅤㅤㅤㅤㅤㅤㅤP R ㅤㅤㅤㅤㅤㅤㅤㅤㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9 ㅤㅤㅤㅤㅤㅤㅤㅤㅤP

Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pseudo code

위 예시를에 해당하는 코드 컨셉

int partition(int list[], int low, int high ) { int left, right; int pivot; int pivot_item; pivot_item = list[low]; pivot = left = low; right = high; while ( left < right ) { /* Move left while item < pivot */ while( list[left] <= pivot_item ) left++; /* Move right while item > pivot */ while( list[right] > pivot_item ) right--; if ( left < right ) swap(&list[left],&list[right]); } /* right is final position for the pivot */ list[low] = list[right]; list[right] = pivot_item; return right; }

퍼포먼스

시간복잡도는 O(n·log₂n) - worst case 제외

• list의 개수인 n 번만큼 비교 x log₂n 실행

  log₂n 번 만큼 어떻게 실행? Quick Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다. 더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음. n 번 만큼 어떻게 비교? 위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남. 따라서 n·log₂n

  
  

• 시간복잡도가 worst case에서는 O(n²)까지 발생함

문제점

위와 같이 이미 정렬된 상태에서 가장 왼쪽의 값을 pivot으로 잡으면 시간복잡도가 O(n²)이 발생

• O(n²)이 나오는 경우는 리스트에서 pivot을 가장 왼쪽이나 오른쪽을 잡을 때 발생함

해결책

• 최악의 경우를 피하기 위해 pivot을 랜덤하게 선택
• 3개의 pivot을 고른 후, median (중앙값)을 사용
• Insertion Sort를 사용하여 확인
  • Insertion Sort는 규모가 작고 거의 정렬이 다된 리스트에서 효율적으로 동작

Merge Sort

Quick Sort와 마찬가지로 divide and conquer 

• 
  
• split: 주어진 리스트를 두개의 서브 리스트로 완벽하게 쪼갬
• merge: 두개의 서브리스트를 정렬된 리스트에 합침

예시

예시2

상세 예시

6 5 3 1 8 7 2 4

Split

Merge

1. 6과 5를 비교하여 작은 수를 왼쪽, 큰 수를 오른쪽에 배치하여 길이가 2인 리스트에 저장

2. 나머지 값들도 동일하게 생성

3. [5, 6] 과 [1, 3] 에서 각 리스트의 값을 비교하여 작은 순서대로 길이가 4인 리스트에 저장

4. 나머지 리스트인 [7, 8] , [2, 4]도 동일한 로직으로 적용 

5. 두 리스트에 대해 위의 로직을 적용

6. 정렬 완성

퍼포먼스

O(nlog₂n) 만큼의 속도가 나옴

• 리스트 내 키의 개수 n * 리스트를 쪼갠 뒤, 합치는 비용 log₂n
  

  log₂n 번 만큼 어떻게 실행? merge sort에서 split은 단순히 반씩 쪼개기 때문에 값의 비교나 각 단계별 비교한 값의 이동 연산이 수행되지 않음 Merge Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다. 더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음. n 번 만큼 어떻게 비교? 위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.

  
  

O(n)개의 저장공간이 필요함

merge sort는 stable sort라고 볼 수 있음

병렬처리가 가능함

external sorting에 적응력이 높음

어레이에 있는 키의 개수 n과 쪼개고 다시 합치는 데에 log₂n만큼 든다.

Stable Sort

서브로 정렬한 결과의 순서가 뒤바뀌지 않을 때 stable sort라 함

• merge sort, insertion sort, bubble sort
  

다시 말해 {key:value} 쌍의 값들이 있을 때, 같은 키 값을 가지는 2개 이상의 데이터를 정렬할 때, 기존의 순서가 바뀌지 않으면 stable 이라 하고 아니라면 unstable이라 함

웹 페이지에서 특정 데이터의 정렬된 결과를 항상 동일하게 보여줘야 한다고 할 때, unstable sort는 보여주는 데이터와 연관 없는 데이터가 추가되어도 웹페이지를 새로고침 했을 때 순서가 계속 바뀔 수 있음.

예시