티스토리 뷰
삽입 정렬(Insertion Sort)
- 삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬함
- 두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전)하고, 계속해서 ★ n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식임
- 예제 ) 8, 5, 6, 2, 4를 삽입 정렬로 정렬하시오
＊ 초기 상태
＊ 1회전
- 두 번째 값을 첫 번째 값과 비교하여 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킴
＊ 2회전
- 세 번째 값을 첫 번째, 두 번째 값과 비교하여 6을 8자리에 삽입하고 8은 한 칸 뒤로 이동시킨다
＊ 3회전
- 네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킴
＊ 4회전
- 다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한 칸씩 뒤로 이동시킴
쉘 정렬(Shell Sort)
- 쉘 정렬은 삽입 정렬(Insertion Sort)을 확장한 개념임
＊ 입력 파일을 어떤 매개변수(h)의 값으로 서브 파일을 구성하고, 각 서브 파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식(보통 h = 3√n), 즉 임의의 레코드 키오 h 값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식임
＊ 입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식
★ 선택 정렬(Selection Sort)
- 선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식임
- 예제 ) 8, 5, 6, 2, 4를 선택 정렬로 정렬하시오
＊ 초기 상태
＊ 1회전
＊ 2회전
＊ 3회전
＊ 4회전
★ 버블 정렬(Bubble Sort)
- 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식임
- 계속 정렬 여부를 플래그 비트(f)로 결정함
- 예제 ) 8, 5, 6, 2, 4를 버블 정렬로 정렬하시오
＊ 초기 상태
＊ 1회전
＊ 2회전
＊ 3회전
＊ 4회전
퀵 정렬(Quick Sort)
- 퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브 파일로 분해시키는 방식으로 정렬함
＊ 정렬 방식 중에서 가장 빠르방식이며, 프로그램에서 되부름(자기 자신)을 이용하기 때문에 스택(Stack)이 필요함
힙 정렬(Heap Sort)
- 17, 14, 13, 15, 16, 19, 11, 18, 12를 Heap 트리로 구성하시오
① 주어진 파일의 레코드를 전이진 트리로 구성한다
② 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드를 비교하여 큰 값을 위로 올림
③ 교환된 노드들을 다시 검토하여 위의 과정을 반복함
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 |
기수 정렬(Radix Sort) = Bucket Sort
- 기수 정렬은 Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식임
＊ 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬함