CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005

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

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

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

선택정렬(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(n2) 안정성을 만족하지 않는다.

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

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

삽입정렬 프로그램 많은 이동-> 레코드가 클 경우 불리 안정된 정렬방법 이미 정렬되어 있으면 효율적 // 삽입정렬 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; } 많은 이동-> 레코드가 클 경우 불리 안정된 정렬방법 이미 정렬되어 있으면 효율적

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

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

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

버블정렬 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); }

버블정렬 분석 비교횟수 이동횟수 버블정렬의 비교횟수는 최상, 평균, 최악의 어떠한 경우에도 항상 일정 최악: 역순정렬 이동 = 3*비교 최상: 이미정렬 이동 = 0 평균: O(n2) 애플릿 확인

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

쉘정렬 프로그램 // 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 ) // n = size int i, gap; for( gap=n/2; gap>0; gap = gap/2 ) { if( (gap%2) == 0 ) gap++; for(i=0;i<gap;i++) // 부분 리스트의 개수는 gap inc_insertion_sort(list, i, n-1, gap);

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

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

합병정렬의 전체과정

합병정렬의 유사코드 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개의 리스트를 합병하는 단계이다.

합병과정

합병 알고리즘 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++; 요소가 남아있는 부분배열을 sorted로 복사한다; sorted를 list로 복사한다;

합병정렬의 분석 비교횟수 합병정렬은 크기 n인 리스트를 정확히 균등 분배하므로 퀵정렬의 이상적인 경우와 마찬가지로 정확히 logn개의 패스를 가진다. 각 패스에서 리스트의 모든 레코드 n개를 비교하여 합병하므로 n 번의 비교 연산이 수행된다. 따라서 합병정렬은 최적, 평균, 최악의 경우 모두 큰 차이 없이 nlogn번의 비교를 수행하므로 O(nlogn)의 복잡도를 가지는 알고리즘이다. 합병정렬은 안정적이며 데이터의 초기 분산 순서에 영향을 덜 받는다. 이동횟수 배열을 이용하는 합병정렬은 레코드의 이동이 각 패스에서 2n번 발생하므로 전체 레코드의 이동은 2nlogn번 발생한다. 이는 레코드의 크기가 큰 경우에는 매우 큰 시간적 낭비를 초래한다. 그러나 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 따라서 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 이용하는 합병정렬은 퀵정렬을 포함한 다른 어떤 정렬 방법보다 매우 효율적이다.

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

퀵정렬 알고리즘 3 정렬할 범위가 2개 이상의 데이터이면 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); } 3 정렬할 범위가 2개 이상의 데이터이면  4 partition 함수를 호출하여 피벗을 기준으로 2개의 리스트로 분할한다. partition 함수의 반환값은 피봇의 위치가 된다. 5 left에서 피봇 위치 바로 앞까지를 대상으로 순환호출한다(피봇은 제외된다). 6 피봇 위치 바로 다음부터 right까지를 대상으로 순환호출한다(피봇은 제외된다).

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

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); 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; }

퀵정렬 전체과정 밑줄친 숫자: 피봇

퀵정렬의 분석 최상의 경우: 거의 균등한 리스트로 분할되는 경우 패스 수: log2n 2->1 4->2 8->3 … n->log2n 각 패스안에서의 비교횟수: n 총비교횟수: n log2n 총이동횟수: 비교횟수에 비하여 무시가능

퀵정렬의 분석(cont.) 최악의 경우: 불균등한 리스트로 분할되는 경우 패스 수: n 각 패스안에서의 비교횟수: n 총이동횟수: 비교횟수에 비하여 무시가능 (예) 정렬된 리스트가 주어졌을 경우 (1 2  3  4  5  6  7  8  9) 1 (2  3  4  5  6  7  8  9) 1  2 (3  4  5  6  7  8  9) 1  2  3 (4  5  6  7  8  9) 1  2  3  4 (5  6  7  8  9)                     ... 1  2  3  4  5  6  7  8  9

기수정렬(Radix Sort) 이때까지의 정렬 방법들은 모두 레코드들을 비교하여 정렬 (예) 한자리수의 기수정렬 기수 정렬은 레코드를 비교하지 않고도 정렬하는 방법 기수 정렬(radix sort)은 O(nlogn) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법이다. 기수 정렬은 O(kn) 의 시간 복잡도를 가지는데 대부분 k<4 이하 기수 정렬의 단점은 정렬할 수 있는 레코드의 타입이 한정->레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성 (예) 한자리수의 기수정렬 (8, 2, 7, 3, 5) 단순히 자리수에 따라 버킷에 넣었다가 꺼내면 정렬됨

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

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

정렬 알고리즘의 비교