13-2 자료 정렬 방법 2

1. 셀정렬

① 셀정렬

 - 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입정렬을 수행하는 작업을 반복하며 원소들을 정렬하는 방법

 

2. 병합 정렬

① 병합 정렬의 이해

 - 부분집합으로 분할하고, 각 부분집합에 대해서 정렬 작업을 완성한 후 정렬된 부분집합들을 다시 결합하는 분할 정복

 - 메모리 사용공간

   각 단계에서 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요

 

 

② 병합정렬 종류

③ 2-way 병합 정렬 과정

- 분할 단계

- 정복과 결합 단계 : 부분집합 두개를 정렬하여 하나로 결합 -> 전체 원소가 집합 하나로 묶일 때까지 반복

 

3. 히프정렬과 트리정렬 

① 히프 정렬의 이해

- 히프에서 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환

-  1) 초기 상태 - 삽입연산으로 최대 히프 구성

- 2) 삭제연산 수행하여 루트 노드의 원소를 배열의 마지막 자리에 저장

      -> 나머지 히프를 최대 히프로 재구성

- 3) 삭제연산 + 최대 히프로 재구성

- 4) 공백 히프되면 히프 정렬 종료

② 트리 정렬의 이해

- 1) 원소를 이진 탐색 트리로 구성

   2)  중위 순회 방법으로 순회하며 원소 저장

 

③ 정렬 알고리즘 성능 비교