1. 자료구조

- 정렬

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)