[은행 필기대비 자료구조-04] 정렬 알고리즘_2

5. 퀵정렬

==> 데이터의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬

 

==> 1번째 데이터를 중심으로 중간값 설정 , 중간값을 적당한 곳에 위치시켜서 대상 자료를

부분적으로 나누어가는 방식

 

EX) [5 ,3 ,8 ,4 ,9 ,1 ,6 ,2 ,7]

 

㉠ 1회전

 

1. 5[pivot] 3 8 4 9 1 6 2 7[end]

 

2.start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 8 4 9 1 6 2 7[end]

 

3. 교환 ==> 5[start, pivot] 3 2 4 9 1 6 8 7[end]

 

4. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 2 4 9 1 6 8 7[end]

 

5. 교환 ==> 5[start, pivot] 3 2 4 6 1 9 8 7[end]

 

6. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 2 4 6 1 9 8 7[end]

 

7. 교환 ==> 5[start, pivot] 3 2 4 1 6 9 8 7[end]

 

8. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기 ==> 5[start, pivot] 3 2 4 1 6 9 8 7[end]

 

9. 큰값과 , 작은 값이 엇갈린다! ==> 작은값과 pivot 값 교환 ==> 1[start, pivot] 3 2 4 5 6 9 8 7[end]

 

==> 1 3 2 4 5 6 9 8 7

 

㉡ 2회전

 

1. 1[start, pivot] 3 2 4[end]  // 6[start, pivot] 9 8 7[end]

 

2. start부터 pivot보다 큰값 찾기 , end부터 pivot보다 작은 값 찾기

==> 1 3[start, pivot] 2 4[end] ==> end부터 pivot 보다 작은 값 없다. pivot값 3으로 변경

==> 6[start, pivot] 9 8 7[end] ==> end부터 pivot 보다 작은 값 없다. pivot값 9로 변경

 

3. 교환

==>1 3[start, pivot] 2 4[end] ==> 큰값과 , 작은 값이 엇갈린다! ==> 작은값과 pivot 값 교환 ==> 1 2 3 4

==> 6 7[start, pivot] 8 9[end] ==> 큰값과 , 작은 값이 엇갈린다! ==> 작은값과 pivot 값 교환 ==>6 7 8 9

 

 

6. 힙정렬

 

1. 전이진 트리를 이용한 정렬 방식 ==> 이진 트리를 힙 정렬로 변환하는 방법

 

2. 전이진 트리형태로 노드의 배치가 상위에서 하위로 내려가면서 좌측에서 우측으로 순서적으로 배치하여 트리를 구성

 

3. 부모 노드가 자식 노드보다 큰 값(최대 힙) 이거나 작은 값(최소 힙) 이 되도록 구성

 

 

==> 최대힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 힙 ==> 루트 노드에 가장 큰 원소가 위치

 

==> 최소힙:  부모 노드의 키 값이 자식 노드의 키 값 보다 작은 힙 ==> 루트 노드에 가장 작은 원소가 위치

 

EX) [10 , 9 , 5 , 8 , 3 , 2 , 4 , 6 , 7 , 1]

 

전 이진 트리

 

1> 최대힙의 루트 노드를 배열의 마지막 값과 교환 , 가장 큰 값은 배열의 마지막에 저장

 

==>[1, 9 , 5 , 8 , 3 , 2 , 4 , 6 , 7 ,10]

 

2> 마지막 요소를 제외한 크기가 9인 힙을 다시 재구조화

 

==> [9 , 8 , 5 , 7 , 3 , 2 , 4 , 6 , 1 , 10]

 

3> 다시 최대힙의 루트 노드를 배열의 마지막 값과 교환

 

==> [1, 8 , 5 , 7 , 3, 2, 4 , 6 , 9 ,10]

 

4> 마지막 요소를 제외한 크기가 8인 힙을 다시 재구조화

 

==>[8, 7 , 5 , 6 , 3, 2, 4 ,1 , 9 ,10] 

 

5> 다시 최대힙의 루트 노드를 배열의 마지막 값과 교환

 

==>[1, 7 , 5 , 6 , 3, 2, 4 , 8  , 9 ,10] 

 

반복········> [ 1, 2, 3, 4, 5 , 6 , 7 , 8 , 9 , 10]

 

 

7. 2진 병합 정렬

 

==> 주어진 입력 파일을 크기가 2인 서브파일로 모두 나누어서 각 서브 파일들을 정렬

 

==> 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다.

 

EX) [7 , 3 , 6 , 4 , 1 , 8 , 9 , 2]

 

{7,3} {6,4} {1,8} {9,2}

 

==> {3,7} , {4,6} , {1,8} , {2,9}

 

==>{3,4,6,7} , {1,2,8,9}

 

==> {1,2,3,4,6,7,8,9}