[자료구조] 정렬방법

목차

버블정렬(Bubble sort)
선택 정렬(Selection sort)
쉘 정렬(Shell sort)
퀵 정렬(Quick sort)
2원 병합 정렬(2-way Merge sort)
트리 정렬(Tree sort)
기수 정렬(Radix sort)

본문내용

가장 단순한 정렬 방법 중의 하나로서 이미 정렬되어 있는 서브 파일에서 적당한 위치를
찾아 새로운 레코드를 삽입한다. 삽입 레코드가 포함된 서브 파일은 계속 정렬 상태를 유지
하게 되며 이때 첫 레코드는 이미 정렬되어 있는 것으로 간주한다.

(1) 삽입 정렬의 실행 단계
① 두번째 키를 기준으로 첫 번째 키와 두 번째 키를 비교하여 키 값에 따라 순서대로 나 열 한다.
② 다시 세 번째 키 기준으로 하여 첫 번째 키와 두 번째 키를 비교하여 키 값에 따라 순 서 대로 나열한다.
③ 계속하여 n번째 키를 앞의 n-1개의 키와 비교하여 삽입될 적당한 위치를 찾아 삽입한 다.
정렬되지 않은 n개의 레코드 R1, R2, …, Rn으로 구성된 파일을 R이라고 할 때, R에서 I번째 레코드를 Ri라고 하고, Ri 레코드의 키를 Ki라고 하며, 삽입될 새로운 레코드의 키를 K라고하면, 삽입될 새로운 레코드의 키 값에 따라 오름차순으로 삽입 정렬하는 알고리즘 INSERTASCEN은 다음과 같다.


<삽입정렬 알고리즘>
procedure INSERTASCEN(R, n)
for j ← 2 to n do // 삽입될 새로운 레코드의 키 선택 //
R ← Rj // 삽입할 레코드 선택 //
K ← Kj // 삽입할 레코드의 키 선택 //
i ← j-1 // 정렬된 레코드의 수 //
while i> 0 and > do
// 삽입될 위치 결정 및 레코드 이동 //
Ri +1 ← Ri
i ← i - 1
end
Ri+1 ← R
end
end INSERTASCEN
<C로 구현한 삽입 정렬>
void insert_sort(int a[], int n){
int i, j, t;
for (i = 1 ; i < n ; i++){
t = a[i];
j = i;
while(a[j-1] > t && j > 0){ /* 삽입될 곳을 찾음 */
a[j] = a[j-1]; /* 뒤로 옮김 */
j--;
}
a[j] = t; /* 삽입함 */
}
}

참고자료

· 없음