Chapter 9 정렬 (sorting) SANGJI University Kwangman KO (kkman@sangji.ac.kr)
정렬 (sorting) 이란? 정의 물건을크기순으로오름차순이나내림차순으로나열하는것 컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적. ( 예 ) 만약사전에서단어들이정렬이안되어있다면?
정렬알고리즘의개요 정렬알고리즘분류 단순하지만비효율적인방법 삽입정렬, 선택정렬, 버블정렬, 복잡하지만효율적인방법 퀵정렬, 히프정렬, 합병정렬, 기수정렬, 정렬알고리즘선택 모든경우에최적인알고리즘은없음 응용에맞추어선택 정렬알고리즘의평가 비교횟수 이동횟수
버블 (bubble) 정렬 알고리즘 왼쪽부터 0,1,2,3,,N-1로가정 0에있는막대와 1에있는막대를비교 오른쪽이왼쪽보다작으면자리바꿈 그렇지않으면자리를바꾸지않음 위치를오른쪽으로한자리이동 위치를이동한다음 1과 2를비교 위과정반복
4 가지단계로정리됨 첫번째, 두개의항목을비교. 두번째, 오른쪽항목이작으면자리바꿈. 세번째, 오른쪽으로한자리이동. 네번째, 가장오른쪽에한항목을비교할때까지앞의 3 단계를반복.
버블 (bubble) 정렬
가장왼쪽부터비교시작 위치 0 와위치 1 을항목을비교 33 이 11 보다크기때문에서로자리를바꿈
위치 1 과위치 2 를비교 33 이 99 보다작기때문에자리를바꾸지않음
위치를오른쪽으로하나이동해서비교 99 가 1 보다크기때문에자리를바꿈 99 가 22, 88, 55, 44, 66, 77 보다크므로매번자리를바꿈
첫번째정렬후 오른쪽끝의막대는정렬된상태가됨
두번째정렬후 마지막막대를뺀나머지를정렬대상으로함
버블정렬 in 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); } }
버블정렬분석 비교횟수 항목의개수가 N 이면비교횟수 정리 첫번째과정은 N-1 번 두번째과정은 N-2 번 (N-1) + (N-2) + (N-3) +... + 1 = N * (N-1) / 2 비교횟수는최상, 평균, 최악의어떠한경우에도항상일정
선택 (selection) 정렬 선택정렬 버블정렬의자리바꿈횟수감소목적 정렬이안된숫자들중에서최소값을선택하여배열의첫번째요소와교환
알고리즘 첫번째항목을기준으로다른항목과비교 가장작은것과기준항목과치환 ( 교환 ) 단계 0 에있는막대와 1~9 까지의막대를비교 가장작은막대를 0 에있는막대와치환
단계 기준항목을오른쪽으로하나이동 위치1에있는막대와 2~9까지의막대를비교 가장작은막대를위치1에있는막대와치환
선택정렬 in C static int[] selectionsort (int[] arr) { int min; for (int i=0; i<arr.length-1; i++) { // 항목선택 min = i; for(int j=i+1 ; j<arr.length; j++) { if (arr[j] < arr[min]) { min = j; // 가장작은값을변경 } } swap(arr, i, min); displayarray(arr); System.out.println(); } return arr; }
10 개의자료에대한선택정렬결과 33, 11, 99, 1, 22, 88, 55, 44, 66, 77 *INPUT : 33 11 99 1 22 88 55 44 66 77 STEP 1 : 1 11 99 33 22 88 55 44 66 77 STEP 2 : 1 11 99 33 22 88 55 44 66 77 STEP 3 : 1 11 22 33 99 88 55 44 66 77 STEP 4 : 1 11 22 33 99 88 55 44 66 77 STEP 5 : 1 11 22 33 44 88 55 99 66 77 STEP 6 : 1 11 22 33 44 55 88 99 66 77 STEP 7 : 1 11 22 33 44 55 66 99 88 77 STEP 8 : 1 11 22 33 44 55 66 77 88 99 STEP 9 : 1 11 22 33 44 55 66 77 88 99
선택정렬분석 비교횟수 버블정렬과항목의비교횟수는동일 10개의항목의경우비교회수는 N*(N-1)/2=45로동일 자리바꿈횟수 버블정렬보다작음 자리바꿈횟수는 10 회이하
삽입 (insertion) 정렬 특성 정렬되어있는부분에새로운레코드를적절한위치에삽입하는과정을반복 세개의기본정렬기법중에서가장큰효율성 버블정렬보다 2 배, 선택정렬보다약간빠름. 0 1 2 3 4 5 6 7 8 9
과정 _1 위치 6 의막대보다 4, 5 의막대가크므로 4, 5 에위치한막대를오른쪽으로 1 칸이동.
과정 _2 위치 6 에있던막대를위치 4 에있던막대의왼쪽에삽입 (insert) 이러한방법으로나머지막대도적절한위치에삽입.
삽입정렬 in C // 삽입정렬 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; }
10 개의자료에대한삽입정렬결과 33, 11, 99, 1, 22, 88, 55, 44, 66, 77 *INPUT : 33 11 99 1 22 88 55 44 66 77 STEP 1 : 11 33 99 1 22 88 55 44 66 77 STEP 2 : 11 33 99 1 22 88 55 44 66 77 STEP 3 : 1 11 33 99 22 88 55 44 66 77 STEP 4 : 1 11 22 33 99 88 55 44 66 77 STEP 5 : 1 11 22 33 88 99 55 44 66 77 STEP 6 : 1 11 22 33 55 88 99 44 66 77 STEP 7 : 1 11 22 33 44 55 88 99 66 77 STEP 8 : 1 11 22 33 44 55 66 88 99 77 STEP 9 : 1 11 22 33 44 55 66 77 88 99
삽입정렬분석 최상의경우 : 이미정렬되어있는경우 비교 : n-1번 이동 : 2(n-1) 번 최악의경우 : 역순으로정렬 모든단계에서앞에놓인자료전부이동
기본정렬비교 버블정렬 가장간단함 비효율적 정렬대상이적을경우사용하는것이바람직함 선택정렬 자리바꿈횟수를최소화 비교횟수는여전히많음 정렬할대상이적거나, 자리바꿈시간이비교시간보다상대적으로클때사용하는것이유용
삽입정렬 정렬대상이적은경우 부분적으로정렬이된경우에효율적 정렬의위해필요한메모리의양? 정렬알고리즘에대한수행속도를비교 http://cg.scs.carleton.ca/~morin/misc/sortalg/
쉘 (shell) 정렬 특징 삽입정렬의단점을극복하고장점을이용하여만든정렬 전체 N 개라는하나의배열을일정한간격 (interval) 으로나눔 작은자료의개수로이루어진하위배열을각각삽입정렬 더좁은간격으로하위배열로나누고최종적으로전체배열을삽입정렬
3 가지단계로정리됨 N 개의항목으로이루어진하나의배열을일정한간격으로나눔 여러개의하위배열로구성. 여러개의하위배열에대해각각삽입정렬 보다작은간격을두어여러개의하위배열을구성 위단계반복.
[22, 1, 11, 88, 55, 99, 77, 66, 44, 33] 간격 '4' 로나눈 4 개의하위배열로구분
4-sort 과정 [22, 1, 11, 66, 44, 33, 77, 88, 55, 99] 로변화
4-sort 과정종료 '4' 가아닌간격 '1' 로줄여삽입정렬알고리즘적용 간격 '1, 삽입정렬과동일한의미
쉘정렬 in C 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); } }
항목이더많아진다면간격조정? 10개의항목을정렬하기위해처음에는간격을 '4' 로사용 최적의성능을보일수있는간격 크누스방식 (Knuth s interval sequence) 개발자스스로좋은아이디어가있으면적용
퀵 (quick) 정렬 특징 C.A.R Hoare, 1962 정렬알고리즘중가장우수한평균수행속도 분할알고리즘 (partition algorithm) 사용 2 개의그룹으로분할 배열의양끝방향즉, 왼쪽끝에서오른쪽으로그리고오른쪽끝에서왼쪽으로탐색 각각피봇값보다큰값과작은값을발견하면그값들을서로치환하는방식
분할알고리즘 정렬하고자하는배열을 2 개의하위배열로분할 각각의하위배열에서다시재귀적으로자신의배열을분할 멀리떨어진자료를직접적으로치환함으로써정렬의수행속도를개선
퀵정렬알고리즘 배열을 2 개의하위배열로분할 왼쪽하위배열은피봇값보다작은값으로이루어진배열 오른쪽하위배열은피봇값보다큰값으로이루어진배열. 왼쪽하위배열에퀵정렬을다시실행 오른쪽하위배열에퀵정렬을다시실행 피봇 (pivot) 하위배열로분할하는특정값.
퀵정렬과정 배열 [1, 11, 88, 55, 99, 77, 66, 44, 22, 33] 피봇값을가장우측의값인 33 왼쪽에서오른쪽으로피봇값보다큰값을탐색 오른쪽에서왼쪽으로피봇값보다작은값을탐색 찾은값끼리서로치환 이과정을계속해서진행하되서로의자리값이엇갈리면피봇값과왼쪽에서찾은값을서로바꿈
2 개의하위배열로분할된상태 다시퀵정렬재귀적적용 피봇값선정 피봇값을배열의가장오른쪽에위치한값으로선택 퀵정렬에서는피봇값을선정하는작업이아주중요.
피봇값선정방식 중간값 (median of three) 선택방식 배열의첫번째왼쪽값, 중간값그리고마지막오른쪽값을정렬해서중간값을피봇으로사용
퀵정렬 in C 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); } }
특징 정렬할범위가 2 개이상의데이터이면 partition 함수를호출하여피벗을기준으로 2 개의리스트로분할 partition 함수의반환값은피봇의위치 left 에서피봇위치바로앞까지를대상으로순환호출 ( 피봇은제외 ). 피봇위치바로다음부터 right 까지를대상으로순환호출 ( 피봇은제외 ).
분할함수 피봇 (pivot) 가장왼쪽숫자라고가정 두개의변수 low와 high를사용 low는피봇보다작으면통과, 크면정지 high는피봇보다크면통과, 작으면정지 정지된위치의숫자를교환 low와 high가교차하면종료
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;
퀵정렬분석 퀵정렬알고리즘 분할알고리즘을기본으로하는방식 분할알고리즘의시간복잡도는 O(N) 각각의하위배열은처음에 2 개, 그다음 4, 8, 16, 퀵정렬을재귀적실행을위한시간복잡도 O(N * logn)
최악의경우 불균등한리스트로분할되는경우 패스수 : n 각패스안에서의비교횟수 : n 총비교횟수 : n2 총이동횟수 : 비교횟수에비하여무시가능
최선의경우 거의균등한리스트로분할되는경우 패스수 : log 2 n 각패스안에서의비교횟수 : n 총비교횟수 : n log 2 n 총이동횟수 : 비교횟수에비하여무시가능
기수 (radix) 정렬 특성 정렬할대상에대한기본적인가정을가지고출발 음수가아닌숫자 (digit) 로이루어져있을때만기수정렬알고리즘이사용가능 각각의항목을여러자리로나누어각각의자리에서의숫자를정렬 자료항목간비교하는단계는존재하지않음
알고리즘 3 개의숫자로이루어진자료가 5 개있다고할때이를정렬하기위해서기수정렬규칙. 각각의자료를 3 개의자리수로나눈다. 1 단위자리에서각각의자료의숫자를확인해재배열. 10 단위자리에서각각의자료의숫자를확인해재배열, 1 단위자리에서재배열한상태를유지한채 10 단위재배열을한다. 100 단위자리에서각각의자료의숫자를확인해재배열하면기수정렬이완성.
한자리수의기수정렬 (8, 2, 7, 3, 5)
두자리수의기수정렬 (28, 93, 39, 81, 62, 72, 38, 26)
문제점 배열의전체크기와동일한크기의기수테이블을위한메모리가필요 음수, 부동소수점처럼특수한비교연산이필요한자료에는적용불가능 복잡도 복사횟수는자료항목의개수와비례 O(N)