06_sorting

Size: px

Start display at page:

Download "06_sorting"

지석 낭
5 years ago
Views:

1 정렬 Data Structures and Algorithms

2 목차 버블정렬 선택정렬 삽입정렬 힙정렬 병합정렬 퀵정렬 기수정렬 Data Structures and Algorithms 2

3 버블정렬 Data Structures and Algorithms 3

4 버블정렬 Data Structures and Algorithms 4

5 버블정렬 Data Structures and Algorithms 5

6 구현 void BubbleSort(int arr[], int n) int i, j; int temp; for(i=0; i<n-1; i++) for(j=0; j<(n-i)-1; j++) if(arr[j] > arr[j+1]) temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; Data Structures and Algorithms 6

7 구현 int main(void) int arr[4] = 3, 2, 4, 1; int i; BubbleSort(arr,sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; Data Structures and Algorithms 7

8 성능평가 성능평가의두가지기준 비교의횟수 : 두데이터간의비교연산의횟수 이동의횟수 : 위치의변경을위한데이터의이동횟수 비교의횟수 for(i=0; i<n-1; i++) for(j=0; j<(n-i)-1; j++) if(arr[j] > arr[j+1]) 최악의경우 비교의횟수와이동의횟수일치 Data Structures and Algorithms 8

9 선택정렬 Data Structures and Algorithms 9

10 선택정렬 하나씩선택해서정렬 추가메모리공간필요 Data Structures and Algorithms 10

11 개선된선택정렬 가장작은값선택 정렬된위치에삽입 Data Structures and Algorithms 11

12 구현 void SelSort(int arr[], int n) int i, j; int maxidx; int temp; for(i=0; i<n-1; i++) maxidx = i; // 정렬순서상가장앞서는데이터의 index for(j=i+1; j<n; j++) // 최소값탐색 if(arr[j] < arr[maxidx]) maxidx = j; /* 교환 */ temp = arr[i]; arr[i] = arr[maxidx]; arr[maxidx] = temp; Data Structures and Algorithms 12

13 구현 int main(void) int arr[4] = 3, 4, 2, 1; int i; SelSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; Data Structures and Algorithms 13

14 성능평가 for(i=0; i<n-1; i++) for(j=i+1; j<n; j++) if(arr[j] < arr[maxidx]) temp = arr[i]; arr[i] = arr[maxidx]; arr[maxidx] = temp; 최악의경우와최상의경우구분없이 데이터이동의횟수동일 Data Structures and Algorithms 14

15 삽입정렬 Data Structures and Algorithms 15

16 삽입정렬 뒤로밀어내기 구현 Data Structures and Algorithms 16

17 구현 void InserSort(int arr[], int n) int i, j; int insdata; for(i=1; i<n; i++) insdata = arr[i]; // 정렬대상을 insdata에저장. for(j=i-1; j>=0 ; j--) if(arr[j] > insdata) arr[j+1] = arr[j]; else break; // 삽입위치찾았으니탈출! // 비교대상한칸뒤로밀기 arr[j+1] = insdata; // 찾은위치에정렬대상삽입! Data Structures and Algorithms 17

18 구현 int main(void) int arr[5] = 5, 3, 2, 4, 1; int i; InserSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<5; i++) printf("%d ", arr[i]); printf("\n"); return 0; Data Structures and Algorithms 18

19 성능평가 데이터의비교및이동연산이안쪽 for 문안에존재 최악의경우빅 - 오는버블및삽입정렬과마찬가지로 O(n²) for(i=1; i<n; i++) for(j=i-1; j>=0 ; j--) if(arr[j] > insdata) // 데이터간비교연산 arr[j+1] = arr[j]; // 데이터간이동연산 else break; // 최악의경우 break문실행안됨 Data Structures and Algorithms 19

20 힙정렬 Data Structures and Algorithms 20

21 힙정렬 힙의특성 힙에데이터를삽입후추출을하는과정에서값이정렬됨 int PriComp(int n1, int n2) return n2-n1; // 오름차순정렬 // return n1-n2; void HeapSort(int arr[], int n, PriorityComp pc) Heap heap; int i; HeapInit(&heap, pc); for(i=0; i<n; i++) // 정렬대상으로힙구성 HInsert(&heap, arr[i]); for(i=0; i<n; i++) // 하나씩꺼내정렬 arr[i] = HDelete(&heap); Data Structures and Algorithms 21

22 main 함수 int main(void) int arr[4] = 3, 4, 2, 1; int i; HeapSort(arr, sizeof(arr)/sizeof(int), PriComp); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; Heap 의구현은 UsefulHeap.c 참고 Data Structures and Algorithms 22

23 성능평가 하나의데이터를힙에넣고빼는경우에대한시간복잡도 데이터저장시간복잡도 : 데이터삭제시간복잡도 : N 개의데이터 빅오비교테이블 Data Structures and Algorithms 23

24 병합정렬 Divide and Conquer Data Structures and Algorithms 24

25 병합정렬 : Divide And Conquer 1 단계분할 (Divide) 해결이용이한단계까지문제분할 2 단계정복 (Conquer) 해결이용이한수준까지분할된문제해결 3 단계결합 (Combine) 분할해서해결한결과결합 Data Structures and Algorithms 25

26 병합정렬 Data Structures and Algorithms 26

27 분할과정렬 재귀적분할과정 더이상분할할수 없을때까지분할 병합과정이중요 Data Structures and Algorithms 27

28 1 단계 : 분할 void MergeSort(int arr[], int left, int right) int mid; if(left < right) mid = (left+right) / 2; // 중간지점계산 MergeSort(arr, left, mid); // 둘로나눠서각각을정렬 MergeSort(arr, mid+1, right); // 정렬된두배열을병합한다. MergeTwoArea(arr, left, mid, right); Data Structures and Algorithms 28

29 3 단계 : 병합 void MergeTwoArea(int arr[], int left, int mid, int right) int fidx = left; int ridx = mid+1; int i; int * sortarr = (int*)malloc(sizeof(int)*(right+1)); int sidx = left; while(fidx<=mid && ridx<=right) if(arr[fidx] <= arr[ridx]) sortarr[sidx] = arr[fidx++]; else sortarr[sidx] = arr[ridx++]; sidx++; if(fidx > mid) for(i=ridx; i<=right; i++, sidx++) sortarr[sidx] = arr[i]; else for(i=fidx; i<=mid; i++, sidx++) sortarr[sidx] = arr[i]; for(i=left; i<=right; i++) arr[i] = sortarr[i]; free(sortarr); 병합결과를담을메모리공간할당 병합할두영역의데이터를비교하여 배열 sortarr 에저장! 배열의앞부분이 sortarr 로모두이동되어서배열 뒷부분에남은데이터를모두 sortarr 로이동! 배열의뒷부분이 sortarr 로모두이동되어서배열 앞부분에남은데이터를모두 sortarr 로이동! 병합결과를옮겨담는다! Data Structures and Algorithms 29

30 병합정렬 : 병합함수의코드설명 병합결과 병합코드 while(fidx<=mid && ridx<=right) if(arr[fidx] <= arr[ridx]) sortarr[sidx] = arr[fidx++]; else sortarr[sidx] = arr[ridx++]; sidx++; Data Structures and Algorithms 30

31 성능평가 : 비교연산 데이터의비교및데이터의이동은 MergeTwoArea 함수를중심으로진행! 병합정렬의성능은 MergeTwoArea 함수를기준으로계산! while(fidx<=mid && ridx<=right) if(arr[fidx] <= arr[ridx]) sortarr[sidx] = arr[fidx++]; else sortarr[sidx] = arr[ridx++]; sidx++; MergeTwoArea 의핵심 Data Structures and Algorithms 31

32 성능평가 : 비교연산 1과 4 비교후 1 이동 5와 4 비교후 4 이동 5와 6 비교후 5 이동 6을이동하기위한비교 Data Structures and Algorithms 32

33 성능평가 : 비교연산 정렬대상데이터가 n 개일때, 병합단계마다최대 n 번비교 비교연산횟수 : 빅오 : Data Structures and Algorithms 33

34 성능평가 : 이동 임시배열에데이터를병합하는과정에서한번! 배열에저장된모든데이터를원위치로옮기는과정에서한번! 8과 2를정렬해서옮기면서 2회 그결과를다시옮기면서. 2회 최악, 최선상관없이! Data Structures and Algorithms 34

35 퀵정렬 Data Structures and Algorithms 35

36 퀵정렬 : 1 단계, 초기화 총 5 개 (left, right, pivot, low, high) 핵심변수선언 정렬대상의가장왼쪽지점 정렬대상의가장오른쪽지점 피벗기준중심축 피벗을제외한가장왼쪽 피벗을제외한가장오른쪽 Data Structures and Algorithms 36

37 퀵정렬 : 2 단계, low and high 이동 low 의이동 : 피벗보다클때까지우측으로 high 의이동 : 피벗보다작을때까지 Data Structures and Algorithms 37

38 퀵정렬 : 3 단계, low 와 high 교환 1 low 와 high 이동 2 low와 high의데이터교환 3 1, 2번반복 4 high와 low가역전할때까지반복 Data Structures and Algorithms 38

39 퀵정렬 : 4 단계, 피벗이동 1 high와 low가역전 2 피벗과 high의데이터교환 3 두개의영역으로나누어반복 Data Structures and Algorithms 39

40 구현 int Partition(int arr[], int left, int right) int pivot = arr[left]; // 피벗의위치는가장왼쪽! int low = left+1; int high = right; while(low <= high) // 교차되지않을때까지반복 while(pivot > arr[low]) low++; while(pivot < arr[high]) high--; if(low <= high) // 교차되지않은상태라면 Swap 실행 Swap(arr, low, high); // low와 high가가리키는대상교환 Swap(arr, left, high); // 피벗과 high가가리키는대상교환 return high; // 옮겨진피벗의위치정보반환 Data Structures and Algorithms 40

41 구현 : 파티션 int Partition(int arr[], int left, int right) int pivot = arr[left]; int low = left+1; int high = right; while(low <= high) while(pivot > arr[low]) low++; while(pivot < arr[high]) high--; if(low <= high) Swap(arr, low, high); Swap(arr, left, high); return high; Data Structures and Algorithms 41

42 구현 : 재귀적파티션 void QuickSort(int arr[], int left, int right) if(left <= right) int pivot = Partition(arr, left, right); // 둘로나눠서 QuickSort(arr, left, pivot-1); // 왼쪽영역을정렬 QuickSort(arr, pivot+1, right); // 오른쪽영역을정렬 int Partition(int arr[], int left, int right) while(low <= high) // 항상참일수밖에없는상황존재 while(pivot >= arr[low] && low <= right) // 문제상황해소 low++; while(pivot <= arr[high] && high >= (left+1)) // 문제상황해소 high--; Data Structures and Algorithms 42

43 퀵정렬 : 피벗 피벗은중앙값에가까울수록성능이좋음 확률적으로중앙에가까운값선정방법 : 첫번째, 마지막, 가운데의값을선택하여중앙값으로사용 첫세개의값중중앙값사용 정렬과정에서피벗변경횟수가적을수록성능이좋음 불규칙한패턴인경우성능이좋음 어느정도정렬이되어있고피벗이한쪽끝에있으면성능최악 Data Structures and Algorithms 43

44 최선의경우성능평가 모든데이터가피벗과데이터비교 : n번 피벗이동후약 n번비교 1차 : 31개의데이터가있을때 15개씩둘로나뉘어 2 덩어리 2차 : 7개씩 2덩어리, 총 4덩어리 3차 : 3개씩 2덩어리, 총 8덩어리 4차 :1개씩 2덩어리, 총 16덩어리 계속반씩나뉘는구조 최선의경우빅오 Data Structures and Algorithms 44

45 최악의경우성능평가 둘로나뉘는횟수 : n 피벗선정후비교횟수 : n 최악의경우빅오 : 퀵정렬은평균적으로가장좋은성능을보이는정렬알고리즘 데이터이동이적음 별도의메모리공간유지필요없음 Data Structures and Algorithms 45

46 기수정렬 Data Structures and Algorithms 46

47 기수정렬 특징 정렬순서가앞섬이나뒤섬을비교하지않음 정렬알고리즘의한계로알려진 O(nlog2n) 을뛰어넘을수도있음 적용할수있는대상이매우제한적임 길이가동일한데이터들의정렬에용이함 기수정렬사용가능예 배열에저장된 1, 7, 9, 5, 2, 6을오름차순으로정렬하라! 영단어 red, why, zoo, box를사전편찬순서대로정렬하여라! 배열에저장된 21, -9, 125, 8, -136, 45를오름차순으로정렬하라! Data Structures and Algorithms 47

48 원리 기수 (radix): 주어진데이터를구성하는기본요소 ( 기호 ) 버킷 (bucket): 기수의수에해당하는만큼의버킷을활용 버킷에값을넣고순서대로추출, 비교가없음 Data Structures and Algorithms 48

49 기준 : Least Significant Digit (LSD) 1/3 List Significant Digit 을시작으로정렬 Data Structures and Algorithms 49

50 기준 : Least Significant Digit (LSD) 2/3 Data Structures and Algorithms 50

51 기준 : Least Significant Digit (LSD) 3/3 마지막까지진행을해야값의우선순위대로정렬됨 Data Structures and Algorithms 51

52 기준 : Most Significant Digit (MSD) MSD 는정렬의기준선정방향이 LSD 와반대이다! 방향성외의차이는무엇인가? 점진적으로정렬이완성됨 중간과정에서정렬이완료된데이터는더이상의정렬하지않아야함 Data Structures and Algorithms 52

53 LSD 정렬기준구현 MSD와 LSD의빅오는같음 LSD를기준으로하는구현이일반적임 LSD 기준은모든데이터에동일한정렬방법을적용할수있음 MSD 기준은경우를나눠정렬해야함 ( 양의정수 only) LSD 기반정렬용자릿수추출알고리즘 NUM으로부터첫번째자리숫자추출 : NUM / 1 % 10 NUM으로부터두번째자리숫자추출 : NUM / 10 % 10 NUM으로부터세번째자리숫자추출 : NUM / 100 % 10 Data Structures and Algorithms 53

54 구현 void RadixSort(int arr[], int num, int maxlen) // maxlen은가장긴데이터의길이 Queue buckets[bucket_num]; int bi; int pos; int di; int divfac = 1; int radix; for(bi=0; bi<bucket_num; bi++) QueueInit(&buckets[bi]); for(pos=0; pos<maxlen; pos++) // 가장긴데이터의길이만큼반복 for(di=0; di<num; di++) // 정렬대상의수만큼반복 radix = (arr[di] / divfac) % 10; // N 번째자리의숫자추출 Enqueue(&buckets[radix], arr[di]); // 추출한숫자를데이터버킷에저장 for(bi=0, di=0; bi<bucket_num; bi++) // 버킷수만큼반복 // 버킷에저장된것순서대로다꺼내서다시 arr 에저장 while(!qisempty(&buckets[bi])) arr[di++] = Dequeue(&buckets[bi]); divfac *= 10; // N 번째자리의숫자추출을위한피제수의증가 Data Structures and Algorithms 54

55 성능평가 버킷에데이터삽입 / 추출을근거로빅 - 오결정! void RadixSort(int arr[], int num, int maxlen) for(pos=0; pos<maxlen; pos++) for(di=0; di<num; di++) radix = (arr[di] / divfac) % 10; Enqueue(&buckets[radix], arr[di]); for(bi=0, di=0; bi<bucket_num; bi++) while(!qisempty(&buckets[bi])) arr[di++] = Dequeue(&buckets[bi]); divfac *= 10; 삽입 추출 삽입 + 추출 = 한쌍 maxlen x num O( L n ) L: 정렬대상길이 N: 정렬대상수 Data Structures and Algorithms 55

슬라이드 1

슬라이드 1 CHAP 9: 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수 ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬의단위 레코드 정렬의대상 학생들의레코드 이름학번주소연락처 레코드 필드필드필드필드 키 (key) 정렬알고리즘의개요 많은정렬알고리즘존재 단순하지만비효율적인방법