CHAP 9: 정렬 (part 2) 2016. 11. 17 순천향대학교 컴퓨터학부 하 상 호.

Presentation on theme: "CHAP 9: 정렬 (part 2) 2016. 11. 17 순천향대학교 컴퓨터학부 하 상 호."— Presentation transcript:

1 CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호

2 Remind: 다음 정렬 방법을 비교하시오. 알고리즘의 복잡도는? 더 나은 정렬 알고리즘은? 선택정렬 삽입정렬 버블정렬
쉘 정렬 더 나은 정렬 알고리즘은?

3 합병정렬 개념 합병정렬은 분할과 정복기법에 기반
리스트를 두 개의 균등한 크기로 분할하고, 분할된 각 부분 리스트를 정렬하고, 2개의 정렬된 부분 리스트를 합병하는 방법

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

5 합병정렬의 전체과정

6 합병정렬 알고리즘 merge_sort(list: array of integers, left, right: integer) if (left < right) then mid = (left+right)/2; merge_sort(list, left, mid); merge_sort(list, mid+1, right); merge(list, left, mid, right); endif end merge_sort 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것 merge() 알고리즘은?

7 merge(): 합병과정 임시 배열 sorted 사용 2개 배열로부터 원소를 작은 순서대로 sorted에 이동
어느 한 개의 리스트가 소진될 때까지 위 단계를 반복 다른 리스트의 나머지 원소를 sorted에 이동 배열 sorted

8 합병 알고리즘 merge(a: array of integers low, mid, high: integer)
// 2개의 인접한 배열 a[left..mid]와 a[mid+1..right]를 합병 b1, b2, e1, e2, idx: integer sorted: array of integers b1←low; e1←mid; // 첫번째 배열 인덱스: (하한,상한) b2←mid+1; e2←high; // 두번째 배열 인덱스:(하한,상한) indx←low; //sorted 배열 인덱스 // 2개 배열을 sorted 배열로 합병: // 2개 배열 원소를 비교하여 오름차순으로 sorte로 이동 // 어느 한 배열이 소진되면, 다른 배열 원소를 sorte로 이동 // sorted 배열을 a 배열로 다시 이동 end merge

9 합병정렬의 분석 merge_sort(list: array of integers, left, right: integer) if (left < right) then mid = (left+right)/2; merge_sort(list, left, mid); merge_sort(list, mid+1, right); merge(list, left, mid, right); endif end merge_sort 비교횟수 이동횟수

10 평가: 합병 정렬 최악, 평균, 최상의 경우 차이가 있는가? 단점 배열이 아닌 연결리스트로 표현하면? 임시 배열 사용
이동회수가 많다 배열이 아닌 연결리스트로 표현하면? 이동은 링크만 변경하는 것으로 대체 가능

11 퀵 정렬(quick sort) 평균적으로 가장 빠른 정렬 방법 개념 분할과 정복의 기법에 기반
합병 정렬과는 달리 비균등 분할 사용 한 항목을 피봇(pivot)으로 사용 (당분간, 리스트의 첫번째 항목으로 고려) 피봇보다 작은 항목은 왼쪽으로, 큰 항목은 오른쪽으로 이동 피봇 기준으로 2개의 리스트 분할 위의 각 부분 리스트에 대해서 위의 과정 반복 pivot low high

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

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

14 퀵정렬 알고리즘 void quick_sort(int list[], int left, int right)
if left < right then int q=partition(list, left, right); // 배열을 피봇 기준으로 2개로 분할하고, 피봇 위치 반환 quick_sort(list, left, q-1); quick_sort(list, q+1, right); endif end quick_sort

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

16 Quiz 다음 배열을 퀵 정렬하라.

17 partition 함수 구현 int partition(int a[], int left, int right)
int pivot, low, high; low = left; high = right+1; // low, high 위치 설정 // 비교 전에 low는 증가, high는 감소 pivot = a[left]; // 피봇은 첫번째 원소로 설정 return high; // 피봇 위치 반환 end partition do // 피봇보다 작은 항목은 왼쪽으로, 큰 항목은 오른쪽으로 // 피봇보다 큰 항목을 찾는다. // 피봇보다 작은 항목을 찾는다 //두 항목을 교체 while (low <high); // 피봇을 중앙에 위치

18 퀵정렬의 분석 비교 회수 이동 회수 최상, 최악의 경우는?

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

20 퀵정렬의 분석(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

21 퀵 정렬 평가 동일 복잡도를 가진 정렬 방법 가운데서 가장 빠르다. 그 이유는? 퀵 정렬에서 다음 경우를 고려하면?
불필요한 데이터 이동을 줄이고 먼 거리의 데이터 교환 피봇은 추후 연산에서 고려 제외 퀵 정렬에서 다음 경우를 고려하면? 가장 오른쪽 항목을 피봇으로 선택 첫번째, 중간번째, 마지막번째 값중에서 중간 값을 갖는 항목을 피봇으로 선택

22 기수정렬(Radix Sort) 개념 예제: 한 자리 수로 이루어진 수: (8 2 7 3 5) 비교 연산 없이 데이터 정렬
기수와 일치하는 다단계 정렬 예제: 한 자리 수로 이루어진 수: ( ) 10개의 버킷 필요 데이터를 각 자리수 값에 따라 버킷에 넣고 위쪽 버킷부터 순차적으로 버킷 안의 숫자를 읽어들인다. 그 결과는 데이터 정렬

23 기수정렬 만약 2자리수이면? (28, 93, 39, 81, 62, 72, 38, 26) 방법? 몇 개의 버킷이 필요한가?

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

25 기수정렬 다음에서 필요한 버킷의 개수는 데이터 키가 2진법으로 표현되면? 키가 알파벳 문자이면?
키가 32비트 정수이고, 8비트씩 나누어서 기수정렬 적용하면?

26 기수정렬 알고리즘 RadixSort(list : array of integers, n: integer) { for d←LSD의 위치 to MSD의 위치 do    d번째 자릿수에 따라 0번부터 9번 버킷에 집어놓는다.    버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.    d++; end for } 버킷은 어떻게 구현하는가?

27 기수정렬 알고리즘 RadixSort(list : array of integers, n: integer) {
QueueType q[BUCKETS]; for (d=0; d<DIGITS; d++) { // 데이터를 버킷에 넣는다 // 데이터를 버킷에서 꺼내어 배열에 저장한다 i=0; for (b=0; b<BUCKETS; b++) do while (!isEmpty(q[b]) do a[i++] = dequeue(q[b]); end while end for }

28 기수 정렬 알고리즘 분석 복잡도 정렬 데이터의 타입이 정수형으로 제한 데이터의 정수가 d개의 자리수를 가질 경우
실수의 경우는?

29 정렬 알고리즘의 비교

30 문제 다음 정렬 방법을 비교하라. 각 정렬방법에 대해서 데이터 항목 수에 따른 실행시간 추이도를 그래프로 그려라
정렬 방법: 삽입, 선택, 버블, 쉘, 퀵, 합병 정렬 대상 데이터 항목: 주어진 개수의 난수(범위: 1~10,000) 발생 오름차순 정렬 분석 기준 (프로그램 실행 5회의 평균치로 측정할 것) 실행 시간 각 정렬방법에 대해서 데이터 항목 수에 따른 실행시간 추이도를 그래프로 그려라 데이터 항목 수: 2만개, 4만개, 6만개, 8만개, 10만개