- 정렬
1. 내부정렬
정렬할 대상의 크기가 크지 않아 주 기억 장치에서 정렬이 이루어지는 방식
삽입법 : 삽입(Insertion), 셀(Shell)
교환법 : 버블(Bubble), 퀵(Quick), 선택(Selection)
선택법 : 히프(Heap)
합병법 : 2-way(2-way merge) 합병
분배법 : 기수(radix)
1.1 삽입 정렬(Internal Sort)
Data의 개수 -1개의 횟수를 거친다.
처음 데이터는 정렬되어있는 것으로 가정한다.
TEMP 앞방의 번호와 비교했을 때, TEMP가 더 크면 STOP 이외의 경우는 자리를 뒤로 이동하고 바꾼 자리에서 또 앞의 것과 비교한다. 비교가 끝났을 때 방에 TEMP값을 삽입한다.
끝나는 경우 : TEMP와 앞방보다 큰 경우
|
5 |
6 |
4 |
9 |
7 |
temp |
비교회수 |
1 단계 |
5 |
6 |
4 |
9 |
7 |
6 |
1 |
2 단계 |
4 |
5 |
6 |
9 |
7 |
4 |
2 |
3 단계 |
4 |
5 |
6 |
9 |
7 |
9 |
1 |
4 단계 |
4 |
5 |
6 |
7 |
9 |
7 |
2 |
|
9 |
12 |
6 |
7 |
8 |
temp |
비교회수 |
1단계 |
9 |
12 |
6 |
7 |
8 |
12 |
1 |
2단계 |
6 |
9 |
12 |
7 |
8 |
6 |
2 |
3단계 |
6 |
7 |
9 |
12 |
8 |
7 |
3 |
4단계 |
6 |
7 |
8 |
9 |
12 |
8 |
3 |
기억공간 : s = n
수행시간 : O(n^2)
특징 :
간단하며 안정적이다.
순서가 틀린 레코드의 순서가 전체 레코드 수에 비해 현저하게 적은 경우 효율적이다.
전체 레코드 수가 20 ~ 25 이하인 경우 가장 빠른 정렬 기법이다.
1.2 버블 정렬(Bubble Sort)
각 단계마다 인접한 레코드들을 정렬하여 최종단계에서는 전체 리스트가 정렬되도록 하는 방법
1 |
3 |
4 |
2 |
5 |
1 |
3 |
2 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
보라색 : 정렬 확정
이미 정렬이 끝났지만 계속 정렬을 시도하려한다. 이 문제를 FLAG 를 이용하여 알고리즘 개선이 가능하다.
9 |
12 |
6 |
7 |
8 | 기존 |
9 |
6 |
7 |
8 |
12 | FLAG = 1 |
6 |
7 |
8 |
9 |
12 | FLAG = 1 |
6 |
7 |
8 |
9 |
12 | FLAG = 0 |
기억공간 : s = n
수행시간 : O(n^2)
특징:
어떤 데이터가 제 위치에서 멀리 떨어져있다면, 여러번 교환이 발생하는 단점을 가지고 있음
Flag를 사용하여 알고리즘을 개선시킬 수 있다.
2. 외부정렬
내부 정렬 기법을 통해서 정렬된 여러개의 리스트를 디스크나 자기 테이프와 같은 보조기억장치를 사용해서 합병하는 방식
균형합병(balanced merge)
다단계합병(polyphase merge)
교대합병(oscillating merge)
계단식합병(cascade merge)