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

내부 정렬 기법

 

㉠ 삽입법 : 삽입 정렬 , 셀 정렬

㉡ 교환법 : 선택 정렬 , 버블 정렬 , 퀵 정렬

㉢ 선택법 : 힙 정렬

㉣ 분배법 : 기수 정렬

㉤ 병합법 : 2진 병합 정렬

 

외부 정렬 기법

 

==> 대용량의 데이터를 보조기억장치에서 몇 개의 서브 파일로 나누어 내부 정렬이후 주기억장치에서 각 서브 파일 병합

==> 속도는 느리지만 , 정렬하고자 하는 양이 많을 경우 효과적

㉠ 균등 병합 정렬

㉡ 다단계 병합 정렬

㉢ 계단식 병합 정렬

㉣ 교대식 병합 정렬

 

1) 내부정렬

1. 삽입정렬

==> 기준이 되는 키 값의 앞쪽 자료들의 값과 비교하여 자신의 위치를 찾아 삽입하여 정렬

 

==> 자료 일부가 정렬 되어있을 때 유리

 

==> 총 비교 횟수(N은 노드 수) : N*(N-1) / 4

 

EX) 15 , 11, 1 , 3, 8 삽입 정렬

 

1. 11 15 1 3 8

 

2. 1 11 15 3 8

 

3. 1 3 11 15 8 

 

4. 1 3 8 11 15

 

2. 셸 정렬

==> 매개변수 설정--> 데이터를 모아서 매개변수 간격만큼 파일 생성 --> 매개변수의 간격을 감소하면서 정렬

 

==> 주어진 데이터를 매객변수의 값으로 적절한 것으로 선택 --> 이를 점차 감소시키면서 셸 정렬 --> 매개변수가 1이 될때 종료

 

1> 나누는 간격 k

2> 간격 k의 초깃값 : (데이터 개수) / 2

 

3> 매 회전마다 k는 절반으로 나눈다. 항상 홀수가 되도록 값을 수정한다. (짝수인 경우 +1)

 

EX) 10 2 5 4 1 6 9 8 7 3 ==> 셸 정렬 이용

 

N = 10

K = N/2 = 5

 

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

 

2. 1회전

 

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

3. K = 5/2 +1 = 3 , 2회전

 

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

 

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

 

4. K = 3/2 + 1 = 2 , 3회전

 

[3,1]

[5,4]

[2,7]

[6,8]

[10,9]

 

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

 

5. K = 2/2 = 1 , 4회전

 

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

==> 삽입정렬로 정렬

 

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

 

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

 

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

 

 

셸 정렬에서 간격(K) 1일 때 삽입 정렬 ==> 배열의 처음 상태보다 어느 정도 정렬이 되어있으므로, 처음부터 삽입 정렬을 하는 것보다 속도가 빠르다.

 

 

3. 선택정렬

==> 정렬되지 않은 DATA들에 대해 가장 작은 DATA를 찾아 가장 앞의 DATA와 교환

 

==> 총 비교횟수 : N*(N-1) /2 

 

EX) 8 3 4 9 7

 

1. 3 8 4 9 7

 

2. 3 4 8 9 7

 

3. 3 4 7 8 9

 

4. 버블정렬

 

==> 인접한 데이터와 비교하여 위치가 맞지 않을 경우 서로 자리를 교환

 

==> 최대 수행 단계는 데이터 개수보다 1개 적은 횟수만큼 단계 수행

 

EX) 5 8 4 2 6 9 3

 

1. 5 4 8 2 6 9 3 ==> 2번째 요소부터 바로 뒤에꺼랑 2개씩 비교

 

2. 5 4 2 8 6 9 3

 

3. 5 4 2 6 8 9 3

 

4. 5 4 2 6 8 3 9

 

5. 4 5 2 6 8 3 9

 

6. 4 2 5 6 8 3 9

 

7. 4 2 5 6 3 8 9

 

8 . 2 4 5 6 3 8 9

 

9. 2 4 5 3 6 8 9

 

10. 2 4 3 5 6 8 9

 

11. 2 3 4 5 6 8 9