자료구조 실습 14주차

내부 정렬
정렬할 자료를 메인메모리에 올려 정렬하는 방식
외부 정렬 - 보조기억장치에 저장함

외부 정렬 방식
병합방식 - (2-way 병합, n-way 병합)

선택 정렬
전체 원소들 중에서 기준위치에 맞는 원소를 선택하고 자리를 교환하는 방식(작은 순서대로 그 자리에 있는 원소와 교환한다고 생각해도 됨)
평균 시간복잡도 : O(n²)
{ 69 10 30 2 16 8 31 22 }
69 10 30 2 16 8 31 22 : 69, 2 교환

2 10 30 69 16 8 31 22 : 10, 8 교환

2 8 30 69 16 10 31 22 : 30, 10 교환

2 8 10 69 16 30 31 22 : 69, 16 교환

2 8 10 16 69 30 31 22 : 69, 22 교환

2 8 10 16 22 30 31 69 : 최종

버블 정렬
인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
평균 시간복잡도 : O(n²)

퀵 정렬
정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법

왼쪽 중앙값 먼저

45 15 50 / 69 10 20 / 30 71 2 / 16 8 31
x >= 20                                x < 20

45, 8 교환

8 15 50 / 69 10 20 / 30 71 2 / 16 45 31
x >= 20                                x < 20
50, 16 교환

8 15 16 / 69 10 20 / 30 71 2 / 50 45 31
x >= 20                                x < 20

69, 2 교환 , 20 확정

오른쪽 중앙값 먼저
8 15 16 / 2 10 20 / 30 71 69 / 50 45 31
x >= 16                                x < 16

16, 10 교환 , 16 확정

8 15 10 / 2 16 20 / 30 71 69 / 50 45 31
x >= 16                                x < 16

15, 2 교환 , 15 확정

8 2 10 / 15 16 20 / 30 71 69 / 50 45 31
x >= 16                                x < 16

2, 8 교환 , 2,8 확정

2 8 10 / 15 16 20 / 30 71 69 / 50 45 31
x >= 20                                x < 20

15 확정

2 8 10 / 15 16 20 / 30 71 69 / 50 45 31 : 최종

삽입 정렬
정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법
부분집합 S와 U로 나눠 S는 정렬된 앞부분 원소, U는 정렬되지 않은 나머지 원소들을 의미한다
평균 시간복잡도 : O(n²)

{ 69 10 30 2 16 8 31 22 }

10 69 / 30 2 16 8 31 22

10 30 69 / 2 16 8 31 22

2 10 30 69 / 16 8 31 22

2 10 16 30 69 / 8 31 22

2 8 10 16 30 69 / 31 22

2 8 10 16 30 31 69 / 22

2 8 10 16 22 30 31 69 : 최종

셀 정렬
일정한 간격으로 떨어져있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법
일반적인 시간복잡도 : O(n¹.²⁵)
{ 69 10 30 2 16 8 31 22 }
원소 개수가 8개이므로 h=4

16 10 30 2 69 8 31 22 : 69, 16 교환
16 8 30 2 69 10 31 22 : 10, 8 교환
16 8 30 2 69 10 31 22 : 30, 31 그대로
16 8 30 2 69 10 31 22 : 2, 22 그대로

h=2로 변경
첫번째 부분집합 { 16 30 69 31 }
두번째 부분집합 { 8 2 10 22 }

16 8 30 2 31 10 69 22 : 69, 31 교환
16 2 30 8 31 10 69 22 : 8, 2 교환

h=1로 변경

2 8 10 16 22 30 31 69 : 최종

병합 정렬
여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법
2-way = 2의 배수 -> 2 , 4 , 8 , 10 ...
3-way = 3의 배수 -> 3 , 6 , 9 , 12 ...
n-way = n의 배수

{ 69 10 30 2 16 8 31 22 }

69 10 30 2 / 16 8 31 22 로 두갈래로 나눔
69 10 / 30 2 / 16 8 / 31 22 로 각각 두갈래로 나눔
69 / 10 / 30 / 2 / 16 / 8 / 31 / 22 로 각각 모두 나눔
10 69 / 2 30 / 8 16 / 22 31 로 순서대로 묶음
2 10 30 69 / 8 16 22 31 로 순서대로 묶음
2 8 10 16 22 30 31 69 로 모두 순서대로 묶음

문제 { 45 15 50 69 10 20 30 71 2 16 8 31 22 1 63 5 }

45 15 50 69 10 20 30 71 2 16 8 31 22 1 63 5
45 15 50 69 10 20 / 30 71 2 16 8 31 / 22 1 63 5 n n
45 15 / 50 69 / 10 20 / 30 71 / 2 16 / 8 31 / 22 1 / 63 5
45 / 15 / 50 / 69 / 10 / 20 / 30 / 71 / 2 / 16 / 8 / 31 / 22 / 1 / 63 / 5
15 45 / 50 69 / 10 20 / 30 71 / 2 16 / 8 31 / 1 22 / 5 63
10 15 20 45 50 69 / 2 8 16 30 31 71 / 1 5 22 63

1 2 5 8 10 15 16 20 22 30 31 45 50 63 69 71 : 최종