내부정렬

1. 삽입 정렬

삽입 정렬은 가장 간단한 정렬방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬

초기상태 8 5 6 2 4

1 회전 (8) 5 6 2 4

1 결과 5 8 6 2 4

2 회전 5 8 (6) 2 4

2 결과 5 6 8 2 4

3 회전 5 6 8 (2) 4

3 결과 2 5 6 8 4

4 회전 2 5 6 8 (4)

4 결과 2 4 5 6 8

-> n 번째마다 n번째 번호를 빼서 맨 처음부터 차례대로 비교를 하면서 n 번째 숫자보다 작으면 자리 바꿈.

 

2. 쉘 정렬

쉘 정렬은 삽입 정렬을 확장한 개념

- 입력 파일을 어떤 매개 변수(h)의 값으로 서브 파일을 구성하고, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식

즉 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화 되어 있지 않으면 서로 교환하는 것을 반복하는 정렬방식

- 입력 파일이 부분적으로 정렬되어 있는 경우 유리한 방식

3. 선택 정렬

선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 n-1개 중에서 다시 최소값을

찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬

초기상태 8 5 6 2 4

1 회전  8 5 6 2 4 -> (8) (5) 6 2 4 -> (5) 8 (6) 2 4 -> (2) 8 6 (5) 4 -> (2) 8 6 5 (4) -> 2 8 6 5 4

-> 따라서, 1 회전에서는 8을 고정으로 두고 2번째 숫자인 5와 비교했을 때 5가 크고 5를 앞으로 두고 5를 고정시켜 

3번째, 4번째 5번째 숫자와 비교해서 2가 가장 작으므로 2를 맨앞으로 나오는 결과가 생긴다.

2 회전 2 8 6 5 4  -> 2 (6) (8) 5 4 -> 2 (6) 8 (5) 4 -> 2 (5) 8 6 (4) -> 2 4 8 6 5

-> 따라서, 2 회전에서는 8이 시작 숫자이고 1회전과 마찬가지로 동일 과정을 거친다.

3 회전 2 4 8 6 5 -> 2 4 (8) (6) 5 -> 2 4 (6) 8 (5) -> 2 4 5 8 6 

-> 따라서, 3 회전에서는 8이 시작 숫자이고 1,2 회전과 마찬가지로 동일 과정을 거친다.

4 회전 2 4 5 8 6 -> 2 4 5 (8) (6) -> 2 4 5 6 8

-> 따라서, 4 회전에서는 8이 시작 숫자이고 1,2, 3 회전과 동일과정을 거친다.

---> n번째마다 n번째 숫자와 나머지 숫자들과 비교해서 작은 숫자를 앞에 놓고, 교환 후에도 앞의 과정을 다시 반복하며, 가장 마지막 자리의 숫자와 비교할 때 까지 반복한다. 

4. 버블 정렬

버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키값을 비교하며 그 크기에 따라 레코드 위치를 서로 교환하는 

정렬 방식

계속 정렬 여부를 플래그 비트(f)로 결정

초기 상태 8 5 6 2 4

1 회전 8 5 6 2 4 -> 5-8 6 2 4 -> 5 6-8 2 4 -> 5 6 2-8 4 -> 5 6 2 4-8

2 회전 5 6 2 4 8 -> 5-6 2 4 8 -> 5 2-6 4 8 -> 5 2 4-6 8 -> 5 2 4 6-8 

3 회전 5 2 4 6 8 -> 2-5 4 6 8 -> 2 4-5 6 8 -> 2 4 5-6 8 -> 2 4 5 6-8

4 회전 2 4 5 6 8 -> 2-4 5 6 8 -> 2 4-5 6 8 -> 2 4 5-6 8 -> 2 4 5 6-8

-> 인접한 두 개의 값을 비교해서 작은 숫자가 앞으로 가고 큰 숫자가 뒤로 가는 방식, 이 과정을 계속 반복하며

계속 정렬 여부를 플래그 비트 f로 결정, 

5. 퀵 정렬

퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정려하는 방법으로 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬한다.

-정렬방식중에서는 가장 빠른 방식이며, 프로그램에서 되부름을 이용하기 때문에 스택이 필요한다.

6. 힙 정렬

힙 정렬은 전이진 트리를 이용한 정렬 방식

- 구성된 전이진트리를 힙 트리로 변환하여 정렬

초기값 17 14 13 15 16 19 11 18 12

1. 주어진 파일의 레코드들을 전이진 트리로 구성

17

     |                |

   14              13

 |      |         |      |    

15   16        19   11

 |

 ------

 |     |

18  12

2. 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드를 비교하여 큰 값을 위로 올린다. (맨 밑차수부터시작)

3. 교환된 노드들을 담시 검토하여 위의 과정을 반복

7. 2-way 합병 정렬

2-way Merge Sort는 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

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

- 순서대로 정렬된 각 쌍들의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다.

- 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복

초기상태 71 2 38 5 7 61 11 26 53 42 를 2 way합병 정렬

1 회전

(71 2) (38 5) (7 61) (11 26) (53 42) ->  (2 71) (5 38) (7 61) (11 26) (42 53)

2 회전

 ((2 71) (5 38)) ((7 61) (11 26)) (42 53) ->  (2 5 38 71) (7 11 26 61) (42 53)

3 회전

 ((2 5 38 71) (7 11 26 61)) (42 53) ->  (2 5 7 11 26  38  61 71) (42 53)

4 회전

((2 5 7 11 26  38  61 71) (42 53))-> 2 5 7 11 26  38 42 53 61 71

1회전에서는 두 개씩 묶어서 묶음 안에서 크기 비교해서 정렬하고

2회전에서는 묶음들을 두 개씩 묶어서 그 안에서 크기 비교해서 정렬하고 묶이지 못한 묶음은 나중으로 미룬다.

3회전에서는 2회전을 반복

4회전에서는 3회전을 반복하고, 하나의 정렬된 파일이 되었으므로 여기서 종료.

8. 기수 정렬

기수 정렬은 Queue를 이용하여 자리수(Digit)별로 정리하는 방식

- 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내 정렬