슬라이드 1

Transcription

1 CHAP 9: 정렬

2 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수 ( 예 ) 만약사전에서단어들이정렬이안되어있다면?

3 정렬의단위 레코드 정렬의대상 학생들의레코드 이름학번주소연락처 레코드 필드필드필드필드 키 (key)

4 정렬알고리즘의개요 많은정렬알고리즘존재 단순하지만비효율적인방법 : 삽입정렬, 선택정렬, 버블정렬등 복잡하지만효율적인방법 : 퀵정렬, 히프정렬, 합병정렬, 기수정렬등 모든경우에최적인알고리즘은없음 응용에맞게선택 정렬알고리즘의평가 비교횟수 이동횟수

5 선택정렬 (selection sort) 선택정렬 (selection sort): 정렬이안된숫자들중에서최소값을선택하여배열의첫번째요소와교환 selection_sort(a, n) for i 0 to n-2 do least A[i], A[i+1],..., A[n-1] 중에서가장작은값의인덱스 ; A[i] 와 A[least] 의교환 ; i++; 분석 최소값을선택하는데걸리는시간 : O(n) 숫자의개수가 n 전체시간복잡도 : O(n 2 )

6 삽입정렬 (insertion sort) 삽입정렬은정렬되어있는부분에새로운레코드를적절한위치에삽입하는과정을반복 삽입정렬의과정

7 삽입정렬유사코드 Algorithm InsertionSort(list, n): Input: n 개의정수를저장하고있는배열 list Output: 정렬된배열 list for i 1 to n-1 do { } 정렬된리스트에서 list[i] 보다더큰요소들이동 ; list[i] 를정렬된리스트의적절한위치에삽입 ; i++;

8 삽입정렬프로그램 // 삽입정렬 void insertion_sort(int list[], int n) { } int i, j, key; for(i=1; i<n; i++){ } key = list[i]; for(j=i-1; j>=0 && list[j]>key; j--) list[j+1] = list[j]; /* 레코드의오른쪽이동 */ list[j+1] = key; 많은이동 -> 레코드가클경우불리 안정된정렬방법 이미정렬되어있으면효율적

9 삽입정렬복잡도분석 최상의경우 : 이미정렬되어있는경우 비교 : n-1번 복잡도 O(n) 최악의경우 : 역순으로정렬 모든단계에서앞에놓인자료전부이동 비교 : n 1 i 1 i n n 1) 2 ( 2 O( n ) 이동 : n n 1) 2 ( 2 2( n 1) O( n )

10 버블정렬 (bubble sort) 인접한레코드가순서대로되어있지않으면교환 전체가정렬될때까지비교 / 교환계속

11 버블정렬유사코드 BubbleSort(A, n) for i n-1 to 1 do for j 0 to i-1 do i--; j 와 j+1 번째의요소가크기순이아니면교환 j++;

12 버블정렬 C 코드 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void bubble_sort(int list[], int n) { } int i, j, temp; for(i=n-1; i>0; i--){ } for(j=0; j<i; j++) /* 앞뒤의레코드를비교한후교체 */ if(list[j]>list[j+1]) SWAP(list[j], list[j+1], temp);

13 버블정렬분석 비교횟수 버블정렬의비교횟수는최상, 평균, 최악의어떠한경우에도항상일정 n 1 i 1 i n n 1) 2 ( 2 O( n ) 이동횟수 평균 : O(n 2 )

14 쉘정렬 (Shell sort) 삽입정렬이어느정도정렬된배열에대해서는대단히빠른것에착안한방법 쉘정렬은삽입정렬보다빠르다. 삽입정렬의최대문제점은요소 들이이동할때, 이웃한위치로만 이동 쉘정렬에서는요소들이멀리떨 어진위치로도이동할수있다. 전체리스트를일정간격의부분 리스트로나누고부분리스트를 정렬한다. 간격 (gap) 은점점줄어들게된다. 평균적인경우시간복잡도는 O(n 1.5 )

15 쉘정렬프로그램 // gap 만큼떨어진요소들을삽입정렬 // 정렬의범위는 first 에서 last inc_insertion_sort(int list[], int first, int last, int gap) { } int i, j, key; for(i=first+gap; i<=last; i=i+gap){ } key = list[i]; for(j=i-gap; j>=first && key<list[j];j=j-gap) list[j+gap]=list[j]; list[j+gap]=key; // void shell_sort( int list[], int n ) { } int i, gap; for( gap=n/2; gap>0; gap = gap/2 ) { } if( (gap%2) == 0 ) gap++; // n = size for(i=0;i<gap;i++) // 부분리스트의개수는 gap inc_insertion_sort(list, i, n-1, gap);

16 합병정렬 (merge sort) 합병정렬은리스트를두개로나누어, 각각을정렬한다음, 다시하나로합치는방법 합병정렬은분할정복기법에바탕

17 분할정복법 분할정복법 (divide and conquer) 은문제를작은 2 개의문제로분리하고각각을해결한다음, 결과를모아서원래의문제를해결하는전략이다. 분리된문제가아직도해결하기어렵다면, 즉충분히작지않다면분할정복방법을다시적용한다. 이는재귀호출을이용하여구현된다. 1. 분할 (Divide): 배열을같은크기의 2 개의부분배열로분할한다. 2. 정복 (Conquer): 부분배열을정렬한다. 부분배열의크기가충분히작지않으면재귀호출을이용하여다시분할정복기법을적용한다. 3. 결합 (Combine): 정렬된부분배열을하나의배열에통합한다. 입력파일 : 분할 (Divide): 배열을 과 의 2 개의부분배열로분리 2. 정복 (Conquer): 부분배열을정렬하여 과 를얻는다. 3. 결합 (Combine): 부분배열을통합하여 을얻는다.

18 합병정렬의전체과정

19 합병정렬의유사코드 merge_sort(list, left, right) if left < right mid = (left+right)/2; merge_sort(list, left, mid); merge_sort(list, mid+1, right); merge(list, left, mid, right); 합병정렬은하나의리스트를두개의균등한크기로분할하고분할된부분리스트를정렬한다음, 두개의정렬된부분리스트를합하여전체가정렬된리스트를얻고자하는것 합병정렬에서실제로정렬이이루어지는시점은 2 개의리스트를합병하는단계이다.

20 합병과정

21 합병알고리즘 merge(list, left, mid, last): // 2 개의인접한배열 list[left..mid] 와 list[mid+1..right] 를합병 b1 left; e1 mid; b2 mid+1; e2 right; sorted 배열을생성 ; index 0; while b1 e1 and b2 e2 do if(list[b1]<list[b2]) then sorted[index] list[b1]; b1++; index++; else sorted[index] list[b2]; b2++; index++; 요소가남아있는부분배열을 sorted 로복사한다 ; sorted 를 list 로복사한다 ;

22 합병정렬의분석 비교횟수 크기 n 인리스트를정확히균등분배하므로 logn 개의패스 각패스에서리스트의모든레코드 n 개를비교하여합병하므로 n 번의비교연산수행 복잡도 : O(nlogn) 이동횟수 배열을이용하는합병정렬은임시배열에이동했다가다시가져와야함으로레코드의이동이 2n 번발생 전체레코드의이동은 2nlogn 번발생한다. 복잡도 : O(nlogn) 복잡도 : O(nlogn)

23 퀵정렬 (quick sort) 평균적으로가장빠른정렬방법 분할정복법사용 퀵정렬은전체리스트를 2 개의부분리스트로분할하고, 각각의부분리스트를다시퀵정렬로정렬

24 퀵정렬알고리즘 void quick_sort(int list[], int left, int right) { if(left<right){ int q=partition(list, left, right); quick_sort(list, left, q-1); quick_sort(list, q+1, right); } } partition 함수를호출하여피벗을기준으로 2 개의리스트로분할한다. partition 함수의반환값은피봇의위치가된다. 1) left 에서피봇위치바로앞까지를대상으로순환호출 2) 피봇위치바로다음부터 right 까지를대상으로순환호출

25 partition 함수 피봇 (pivot): 가장왼쪽숫자라고가정 두개의변수 low 와 high 를사용한다. low 는피봇보다작으면통과, 크면정지 high 는피봇보다크면통과, 작으면정지 정지된위치의숫자를교환 low 와 high 가교차하면종료

26 partition 함수구현 int partition(int list[], int left, int right) { int pivot, temp; int low,high; low = left; high = right+1; pivot = list[left]; do { do low++; while(low<=right &&list[low]<pivot); do high--; while(high>=left && list[high]>pivot); if(low<high) SWAP(list[low], list[high], temp); } while(low<high); } SWAP(list[left], list[high], temp); return high;

27 퀵정렬의분석 평균복잡도 : O(nlogn) 속도가빠르고추가메모리공간을필요로하지않는다

28 기수정렬 (Radix Sort) 기수정렬 (radix sort) 은레코드를비교하지않고정렬하는방법 시간복잡도 : O(n) ( 예 ) 한자리수의기수정렬 (8, 2, 7, 3, 5) 단순히자리수에따라버킷에넣었다가꺼내면정렬됨 기수정렬의단점은정렬할수있는레코드의타입이한정 -> 레코드의키들이동일한길이를가지는숫자나문자열로구성

29 기수정렬 만약 2 자리수이면? (28, 93, 39, 81, 62, 72, 38, 26) 낮은자리수로먼저분류한다음, 순서대로읽어서다시높은자리수로분류하면된다.

30 기수정렬알고리즘 RadixSort(list, n): for d LSD 의위치 to MSD 의위치 do { } d 번째자릿수에따라 0 번부터 9 번버킷에집어놓는다. 버킷에서숫자들을순차적으로읽어서하나의리스트로합친다. d++; 버킷은큐로구현 버킷의개수는키의표현방법과밀접한관계 이진법을사용한다면버킷은 2개. 알파벳문자를사용한다면버킷은 26개 십진법을사용한다면버킷은 10개 32비트의정수의경우, 8비트씩나누어기수정렬의개념을적용한다면 -> 필요한상자의수는 256개가된다. 대신에필요한패스의수는 4개로십진수표현보다줄어든다.

31 정렬알고리즘의비교