Microsoft PowerPoint - ch11_정렬 [호환 모드]

Transcription

1 정렬 자바로배우는쉬운자료구조

2 이장에서다룰내용 1 정렬 6 셸정렬 2 선택정렬 7 병합정렬 3 버블정렬 8 기수정렬 4 퀵정렬 9 힙정렬 5 삽입정렬 10 트리정렬 2

3 정렬 (1) 정렬 (sort) 2 개이상의자료를작은것부터큰순서 ( 오름차순, ascending) 로정렬또는큰것부터작은것순서 ( 내림차순, descending) 로재배열하는것 키 : 자료를정렬하는데사용하는기준값 정렬의예 3

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

5 정렬 (3) 정렬방법의분류 실행방법에따른분류 비교식정렬 (comparative sort) 비교하고자하는각키값들을한번에두개씩비교하여교환하는방식으로정렬을실행하는방법 분산식정렬 (distribute sort) 키값을기준으로하여자료를여러개의부분집합으로분해하고, 각부분집합을정렬함으로써전체를정렬하는방식으로실행하는방법 5

6 정렬 (4) 정렬장소에따른분류 내부정렬 (internal sort) 정렬할자료를메인메모리에올려서정렬하는방식 정렬속도가빠르지만정렬할수있는자료의양이메인메모리의용량에따라제한됨 내부정렬방식 교환방식 : 키를비교하고교환하여정렬하는방식» 선택정렬, 버블정렬, 퀵정렬 삽입방식 : 키를비교하고삽입하여정렬하는방식» 삽입정렬, 셸정렬 병합방식 : 키를비교하고병합하여정렬하는방식» 2-way 병합, n-way 병합 분배방식 : 키를구성하는값을여러개의부분집합에분배하여정렬하는방식» 기수정렬 선택방식 : 이진트리를사용하여정렬하는방식» 힙정렬, 트리정렬 6

7 정렬 (5) 외부정렬 (external sort) 정렬할자료를보조기억장치에서정렬하는방식 내부정렬보다속도는떨어지지만내부정렬로처리할수없는대용량자료에대한정렬가능 외부정렬방식 병합방식 : 파일을부분파일로분리하여각각을내부정렬방법으로정렬하여병합하는정렬방식» 2-way 병합, n-way 병합 7

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

9 정렬 (7) 정렬은왜할까? 9

10 선택정렬 (1) 선택정렬 (selection sort) 전체원소들중에서기준위치에맞는원소를선택하여자리를교환하는방식으로정렬 수행방법 1 전체원소중에서가장작은원소를찾아서선택하여첫번째원소와자리를교환한다. 2 그다음두번째로작은원소를찾아선택하여두번째원소와자리를교환한다. 3 그다음에는세번째로작은원소를찾아서세번째원소와자리를교환한다. 4 이과정을반복하면서정렬을완성한다. 10

11 선택정렬 (2) 선택정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을선택정렬방법으로정렬하는과정을살펴보자. 1 첫번째자리를기준위치로정하고, 전체원소중에서가장작은원소 2 를선택하여기준위치에있는원소 69와자리교환 11

12 선택정렬 (3) 2 두번째자리를기준위치로정하고, 나머지원소중에서가장작은원소 8을선택하여기준위치에있는원소 10과자리교환 12

13 선택정렬 (4) 3 세번째자리를기준위치로정하고, 나머지원소중에서가장작은원소 10을선택하여기준위치에있는원소 30과자리교환 13

14 선택정렬 (5) 4 네번째자리를기준위치로정하고, 나머지원소중에서가장작은원소 16을선택하여기준위치에있는원소 69와자리교환 14

15 선택정렬 (6) 5 다섯번째자리를기준위치로정하고, 나머지원소중에서가장작은원소 22를선택하여기준위치에있는원소 69와자리교환 15

16 선택정렬 (7) 6 여섯번째자리를기준위치로정하고, 나머지원소중에서가장작은원소 30을선택하여기준위치에있는원소 30과자리교환 ( 제자리 ) 16

17 선택정렬 (8) 7 일곱번째자리를기준위치로정하고, 나머지원소중에서가장작은원소 31을선택하여기준위치에있는원소 31과자리교환. ( 제자리 ) 8 마지막에남은원소 69는전체원소중에서가장큰원소로서이미마지막자리에정렬된상태이므로실행을종료하고선택정렬이완성된다. 17

18 선택정렬 (9) 선택정렬알고리즘 selectionsort(a[],n) [ 알고리즘 11-1] for (i 1; i<n; i i+1) { a[i],,a[n-1] 중에서가장작은원소 a[k] 를선택하여, a[i] 와교환한다 ; } end selectionsort() 선택정렬알고리즘분석 메모리사용공간 n개의원소에대하여 n개의메모리사용 비교횟수 1단계 : 첫번째원소를기준으로 n개의원소비교 2단계 : 두번째원소를기준으로마지막원소까지 n-1개의원소비교 3단계 : 세번째원소를기준으로마지막원소까지 n-2개의원소비교 18

19 선택정렬 (10) i 단계 : i 번째원소를기준으로 n-i 개의원소비교 어떤경우에서나비교횟수가같으므로시간복잡도는 O(n 2 ) 19

20 선택정렬 (11) 선택정렬프로그램 01 class Sort{ 02 public void selectionsort(int a[]){ 03 int i, j, min; 04 for(i=0; i<a.length-1; i++){ 05 min = i; 06 for(j=i+1; j<a.length; j++){ 07 if(a[j] < a[min]) 08 min = j; 09 } 10 swap(a, min, i); 11 System.out.printf("\n선택정렬 %d 단계 : ", i+1); 12 for(j=0; j<a.length-1; j++) 13 System.out.printf("%3d ", a[j]); 14 } 15 } public void swap(int a[], int i, int j){ [ 예제 11-1] >> 계속 20

21 선택정렬 (12) 18 int temp = a[i]; 19 a[i] = a[j]; 20 a[j] = temp; 21 } 22 } class Ex11_1{ 25 public static void main(string args[]){ 26 int a[] = {69, 10, 30, 2, 16, 8, 31, 22}; 27 Sort S = new Sort(); 28 System.out.printf("\n정렬할원소 : "); 29 for(int i=0; i<a.length; i++) 30 System.out.printf(" %d", a[i]); 31 System.out.println(); 32 S.selectionSort(a); 33 } 34 } [ 예제 11-1] 21

22 선택정렬 (13) 실행결과 22

23 버블정렬 (1) 버블정렬 (bubble sort) 인접한두개의원소를비교하여자리를교환하는방식 첫번째원소부터마지막원소까지반복하여한단계가끝나면가장큰원소가마지막자리로정렬 첫번째원소부터인접한원소끼리계속자리를교환하면서맨마지막자리로이동하는모습이물속에서물위로올라오는물방울모양과같다고하여버블 (bubble) 정렬이라함. 버블정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을버블정렬방법으로정렬하는과정을살펴보자. 1 인접한두원소를비교하여자리를교환하는작업을첫번째원소부터마지막원소까지차례로반복하여가장큰원소 69를마지막자리로정렬 23

24 버블정렬 (2) 24

25 버블정렬 (3) 2 버블정렬을수행하여나머지원소중에서가장큰원소 31을끝에서두번째자리로정렬. 25

26 버블정렬 (4) 3 버블정렬을수행하여나머지원소중에서가장큰원소 30을끝에서세번째자리로정렬. 26

27 버블정렬 (5) 4 버블정렬을수행하여나머지원소중에서가장큰원소 22를끝에서네번째자리로정렬. 27

28 버블정렬 (6) 5 버블정렬을수행하여나머지원소중에서가장큰원소 16을끝에서다섯번째자리로정렬. 28

29 버블정렬 (7) 6 버블정렬을수행하여나머지원소중에서가장큰원소 10을끝에서여섯번째자리로정렬. 29

30 버블정렬 (8) 7 버블정렬을수행하여나머지원소중에서가장큰원소 8을끝에서일곱번째자리로정렬. 마지막에남은첫번째원소는전체원소중에서가장작은원소로이미정렬된상태이므로실행을종료하고버블정렬이완성된다. 30

31 버블정렬 (9) 버블정렬알고리즘 bubblesort(a[],n) for (i n-1; i 0; i i-1) { for (j 0; j<i; j j+1) { if (a[j]>a[j+1]) then { temp a[j]; a[j] a[j+1]; a[j+1] temp; } } } end bubblesort() [ 알고리즘 11-2] 31

32 버블정렬 (10) 버블정렬알고리즘분석 메모리사용공간 n개의원소에대하여 n개의메모리사용 연산시간 최선의경우 : 자료가이미정렬되어있는경우 비교횟수 : i 번째원소를 (n-i) 번비교하므로, n(n-1)/2 번 자리교환횟수 : 자리교환이발생하지않는다. 최악의경우 : 자료가역순으로정렬되어있는경우 비교횟수 : i 번째원소를 (n-i) 번비교하므로, n(n-1)/2 번 자리교환횟수 : i 번째원소를 (n-i) 번교환하므로, n(n-1)/2 번 평균시간복잡도 : O(n 2 ) 32

33 버블정렬 (11) 버블정렬프로그램 01 class Sort{ 02 public void bubblesort(int a[]){ 03 int i, j, temp, size; 04 size = a.length; 05 for(i=size-1; i>0; i--){ 06 System.out.printf("\n버블정렬 %d 단계 : ", size-i); 07 for(j=0; j<i; j++){ 08 if(a[j] > a[j+1]){ 09 temp = a[j]; 10 a[j] = a[j+1]; 11 a[j+1] = temp; 12 } 13 System.out.printf("\n\t"); 14 for(int k=0; k<size; k++) 15 System.out.printf("%3d ", a[k]); 16 } 17 } [ 예제 11-2] >> 계속 33

34 버블정렬 (12) 18 } 19 } class Ex11_2{ 22 public static void main(string args[]){ 23 int a[] = {69, 10, 30, 2, 16, 8, 31, 22}; 24 Sort S = new Sort(); 25 System.out.printf("\n정렬할원소 : "); 26 for(int i=0; i<a.length; i++) 27 System.out.printf(" %d", a[i]); 28 System.out.println(); 29 S.bubbleSort(a); 30 } 31 } [ 예제 11-2] 34

35 버블정렬 (13) 실행결과 35

36 퀵정렬 (1) 퀵정렬 (quick sort) 정렬할전체원소에대해서정렬을수행하지않고, 기준값을중심으로왼쪽부분집합과오른쪽부분집합으로분할하여정렬하는방법 왼쪽부분집합에는기준값보다작은원소들을이동시키고, 오른쪽부분집합에는기준값보다큰원소들을이동시킨다. 기준값 : 피봇 (pivot) 일반적으로전체원소중에서가운데에위치한원소를선택 퀵정렬은다음의두가지기본작업을반복수행하여완성한다. 분할 (divide) 정렬할자료들을기준값을중심으로 2 개의부분집합으로분할하기 정복 (conquer) 부분집합의원소들중에서기준값보다작은원소들은왼쪽부분집합으로, 기준값보다큰원소들은오른쪽부분집합으로정렬하기. 부분집합의크기가 1 이하로충분히작지않으면순환호출을이용하여다시분할. 36

37 퀵정렬 (2) 퀵정렬수행방법 부분집합으로분할하기위해서 L과 R을사용 1 왼쪽끝에서오른쪽으로움직이면서크기를비교하여피봇보다크거나같은원소를찾아 L로표시 2 오른쪽끝에서왼쪽으로움직이면서피봇보다작은원소를찾아 R로표시 3 L이가리키는원소와 R이가리키는원소를서로교환한다. L와 R이만나게되면피봇과 R의원소를서로교환하고, 교환한위치를피봇의위치로확정한다. 피봇의확정된위치를기준으로만들어진왼쪽부분집합과오른쪽부분집합에대해서퀵정렬을순환적으로반복수행하는데부분집합의크기가 1 이하가되면퀵정렬을종료한다. 37

38 퀵정렬 (3) 퀵정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을퀵정렬방법으로정렬하는과정을살펴보자. 1 원소의개수가 8개이므로네번째자리에있는원소 2를첫번째피봇으로선택하고퀵정렬시작. 38

39 퀵정렬 (4) L이오른쪽으로이동하면서피봇보다크거나같은원소를찾고, R은왼쪽으로이동하면서피봇보다작은원소를찾는다. L은원소69를찾았지만, R은피봇보다작은원소를찾지못한채로원소 69에서 L과만나게된다. L 과 R 이만났으므로, 원소 69 를피봇과교환하여피봇원소 2 의위치를확정한다. 39

40 퀵정렬 (5) 2 피봇 2의왼쪽부분집합은공집합이므로퀵정렬을수행하지않고, 오른쪽부분집합에대해서퀵정렬수행. 오른쪽부분집합의원소가 7개이므로가운데있는원소 16을피봇으로선택 L 이찾은 30 과 R 이찾은 8 을서로교환한다. 40

41 퀵정렬 (6) 현재위치에서 L과 R의작업을반복한다. L은원소69를찾았지만, R은피봇보다작은원소를찾지못한채로원소 69에서 L과만나게된다. L과 R이만났으므로, 원소 69를피봇과교환하여피봇원소 16의위치를확정한다. 41

42 퀵정렬 (7) 3 피봇 16 의왼쪽부분집합에서원소 10 을피봇으로선택하여퀵정렬수행. L의원소 10과 R의원소 8을교환하는데, L의원소가피봇이므로피봇원소 10의위치가확정된다. 42

43 퀵정렬 (8) 4 피봇 10 의왼쪽부분집합의원소가한개이므로퀵정렬을수행하지않고, 오른쪽부분집합은공집합이므로역시퀵정렬을수행하지않는다. 이제 1 단계의피봇이었던원소 16 의오른쪽부분집합에대해퀵정렬수행. 오른쪽부분집합의원소가 4 개이므로원소 30 을피봇으로선택. 피봇 L 이찾은 69 와 R 이찾은 22 를서로교환한다. 43

44 퀵정렬 (9) 현재위치에서 L과 R의작업을반복한다. L은오른쪽으로이동하면서피봇보다크거나같은원소인 30을찾고, R은왼쪽으로이동하면서피봇보다작은원소를찾다가못찾고원소 30에서 L과만난다. L과 R이만났으므로피봇과교환하는데 R의원소가피봇이므로결국제자리가확정된다. 44

45 퀵정렬 (10) 5 피봇 30의왼쪽부분집합의원소가한개이므로퀵정렬을수행하지않고, 오른쪽부분집합에대해서퀵정렬수행. 오른쪽부분집합의원소 2개중에서원소 31을피봇으로선택 L 은오른쪽으로이동하면서원소 31 을찾고, R 은왼쪽으로이동하면서피봇보다작은원소를찾다가못찾은채로원소 31 에서 L 과만난다. L 과 R 이만났으므로피봇과교환하는데 R 의원소가피봇이므로결국제자리가확정된다. 45

46 퀵정렬 (11) 피봇 31 의오른쪽부분집합의원소가한개이므로퀵정렬을수행하지않는다. 이로써전체퀵정렬이모두완성되었다. 46

47 퀵정렬 (12) 퀵정렬알고리즘 quicksort(a[], begin, end) if (m < n) then { p partition(a, begin, end); quicksort(a[], begin, p-1); quicksort(a[], p+1, end); } end quicksort() [ 알고리즘 11-3] 47

48 퀵정렬 (13) 퀵정렬알고리즘의분할연산알고리즘 partiton(a[], begin, end) pivot (begin + end)/2; L begin; R end; while(l<r) do { while(a[l]<a[pivot] and L<R) do L++; while(a[r] a[pivot] and L<R) do R--; if(l<r) then { // L 의원소와 R 의원소교환 temp a[l]; a[l] a[r]; a[r] temp; } } temp a[pivot]; // R 의원소와피봇원소교환 a[pivot] a[r]; a[r] temp; return L; end partition() [ 알고리즘 11-4] 48

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

50 퀵정렬 (14) 퀵정렬알고리즘분석 메모리사용공간 n 개의원소에대하여 n 개의메모리사용 연산시간 최선의경우 피봇에의해서원소들이왼쪽부분집합과오른쪽부분집합으로정확히 n/2 개씩이등분이되는경우가반복되어수행단계수가최소가되는경우 최악의경우 피봇에의해원소들을분할하였을때 1 개와 n-1 개로한쪽으로치우쳐분할되는경우가반복되어수행단계수가최대가되는경우 평균시간복잡도 : O(n log 2 n) 같은시간복잡도를가지는다른정렬방법에비해서자리교환횟수를줄임으로써더빨리실행되어실행시간성능이좋은정렬방법 50

51 퀵정렬 (15) 퀵정렬프로그램 01 class Sort{ [ 예제 11-3] 02 int i=0; 03 public int partition(int a[], int begin, int end){ 04 int pivot, temp, L, R, t; L = begin; 07 R = end; 08 pivot = (begin + end)/2; 09 System.out.printf("\n [ 퀵정렬 %d 단계 : pivot=%d ]\n", ++i, a[pivot]); 10 while(l<r){ 11 while((a[l]<a[pivot]) && (L<R)) L++; 12 while((a[r]>=a[pivot]) && (L<R)) R--; 13 if(l<r){ 14 temp = a[l]; 15 a[l] = a[r]; 16 a[r] = temp; 17 } >> 계속 51

52 퀵정렬 (16) 18 } 19 temp = a[pivot]; 20 a[pivot] = a[r]; 21 a[r] = temp; 22 for(t=0; t<a.length; t++) 23 System.out.printf("%3d ", a[t]); 24 System.out.println(); 25 return L; 26 } public void quicksort(int a[], int begin, int end){ 29 if(begin < end){ 30 int p; 31 p = partition(a, begin, end); 32 quicksort(a, begin, p-1); 33 quicksort(a, p+1, end); 34 } 35 } [ 예제 11-3] 52

53 퀵정렬 (17) 36 } class Ex11_3{ 39 public static void main(string args[]){ 40 int a[] = {69, 10, 30, 2, 16, 8, 31, 22}; 41 Sort S = new Sort(); 42 System.out.printf("\n정렬할원소 : "); 43 for(int i=0; i<a.length; i++) 44 System.out.printf(" %d", a[i]); 45 System.out.println(); 46 S.quickSort(a, 0, 7); 47 } 48 } [ 예제 11-3] 53

54 퀵정렬 (18) 실행결과 54

55 삽입정렬 (1) 삽입정렬 (insert sort) 정렬되어있는부분집합에정렬할새로운원소의위치를찾아삽입하는방법 정렬할자료를두개의부분집합 S와 U로가정 부분집합 S : 정렬된앞부분의원소들 부분집합 U : 아직정렬되지않은나머지원소들 정렬되지않은부분집합 U의원소를하나씩꺼내서이미정렬되어있는부분집합 S의마지막원소부터비교하면서위치를찾아삽입 삽입정렬을반복하면서부분집합 S의원소는하나씩늘리고부분집합 U 의원소는하나씩감소하게한다. 부분집합 U가공집합이되면삽입정렬이완성된다. 55

56 삽입정렬 (2) 삽입정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을삽입정렬방법으로정렬하는과정을살펴보자. 초기상태 : 첫번째원소는정렬되어있는부분집합 S로생각하고나머지원소들은정렬되지않은원소들의부분집합 U로생각한다. S={69}, U={10, 30, 2, 16, 8, 31, 22} 56

57 삽입정렬 (3) 1 U의첫번째원소 10을 S의마지막원소 69와비교하여 (10 < 69) 이므로원소 10은원소 69의앞자리가된다. 더이상비교할 S의원소가없으므로찾은위치에원소 10을삽입한다. S={10, 69}, U={30, 2, 16, 8, 31, 22} 57

58 삽입정렬 (4) 2 U의첫번째원소 30을 S의마지막원소 69와비교하여 (30 < 69) 이므로원소 69의앞자리원소 10과비교한다. (30 > 10) 이므로원소 10과 69 사이에삽입한다. S={10, 30, 69}, U={2, 16, 8, 31, 22} 58

59 삽입정렬 (5) 3 U의첫번째원소 2를 S의마지막원소 69와비교하여 (2 < 69) 이므로원소 69의앞자리원소 30과비교하고, (2 < 30) 이므로다시그앞자리원소 10과비교하는데, (2 < 10) 이면서더이상비교할 S의원소가없으므로원소 10의앞에삽입한다. S={2, 10, 30, 69}, U={16, 8, 31, 22} 59

60 삽입정렬 (6) 4 U의첫번째원소 16을 S의마지막원소 69와비교하여 (16 < 69) 이므로그앞자리원소 30과비교한다. (16 < 30) 이므로다시그앞자리원소 10과비교하여, (16 > 10) 이므로원소 10과 30 사이에삽입한다. S={2, 10, 16, 30, 69}, U={8, 31, 22} 60

61 삽입정렬 (7) 5 U의첫번째원소 8을 S의마지막원소 69와비교하여 (8 < 69) 이므로그앞자리원소 30과비교한다. (8 < 30) 이므로그앞자리원소 10과비교하여, (8 < 10) 이므로다시그앞자리원소 2와비교하는데, (8 > 2) 이므로원소 2와 10 사이에삽입한다. S={2, 8, 10, 16, 30, 69}, U={31, 22} 61

62 삽입정렬 (8) 6 U의첫번째원소 31을 S의마지막원소 69와비교하여 (31 < 69) 이므로그앞자리원소 30과비교한다. (31 > 30) 이므로원소 30과 69 사이에삽입한다. S={2, 8, 10, 16, 30, 31, 69}, U={22} 62

63 삽입정렬 (9) 7 U의첫번째원소 22를 S의마지막원소 69와비교하여 (22 < 69) 이므로그앞자리원소 31과비교한다. (22 < 31) 이므로그앞자리원소 30과비교하고, (22 < 30) 이므로다시그앞자리원소 16과비교하여, (22 > 16) 이므로원소 16과 30 사이에삽입한다. S={2, 8, 10, 16, 22, 30, 31, 69}, U={} U 가공집합이되었으므로실행을종료하고삽입정렬이완성된다. 63

64 삽입정렬 (10) 삽입정렬알고리즘 insertionsort(a[],n) for (i 1; i<n; i i+1) do { temp a[i]; j i; if (a[j-1]>temp) then move true; else move false; while (move) do { a[j] a[j-1]; j j-1; if (j>0 and a[j-1]>temp) then move true; else move false; } a[j] temp; } end insertionsort() [ 알고리즘 11-5] 64

65 삽입정렬 (11) 삽입정렬알고리즘분석 메모리사용공간 n 개의원소에대하여 n 개의메모리사용 연산시간 최선의경우 : 원소들이이미정렬되어있어서비교횟수가최소인경우 이미정렬되어있는경우에는바로앞자리원소와한번만비교한다. 전체비교횟수 = n-1 시간복잡도 : O(n) 최악의경우 : 모든원소가역순으로되어있어서비교횟수가최대인경우 전체비교횟수 = (n-1) = n(n-1)/2 시간복잡도 : O(n 2 ) 삽입정렬의평균비교횟수 = n(n-1)/4 평균시간복잡도 : O(n 2 ) 65

66 삽입정렬 (12) 최선의경우 : 이미정렬된상태에서의삽입 최악의경우 : 역순으로정렬된상태에서의삽입 66

67 삽입정렬 (13) 삽입정렬프로그램 01 class Sort{ 02 public void insertionsort(int a[], int size){ 03 int i, j, t, temp; 04 for(i=1; i<size; i++){ 05 temp = a[i]; 06 j = i; 07 while((j>0) && (a[j-1]>temp)){ 08 a[j] = a[j-1]; 09 j--; 10 } 11 a[j] = temp; 12 System.out.printf("\n삽입정렬 %d 단계 : ", i); 13 for(t=0; t<size; t++) 14 System.out.printf("%3d ", a[t]); 15 } 16 System.out.println(); 17 } [ 예제 11-4] >> 계속 67

68 삽입정렬 (14) 18 } class Ex11_4{ 21 public static void main(string args[]){ 22 int a[] = {69, 10, 30, 2, 16, 8, 31, 22}; 23 int size = a.length; 24 Sort S = new Sort(); 25 System.out.printf("\n정렬할원소 : "); 26 for(int i=0; i<a.length; i++) 27 System.out.printf(" %d", a[i]); 28 System.out.println(); 29 S.insertionSort(a, size); 30 } 31 } [ 예제 11-4] 68

69 삽입정렬 (15) 실행결과 69

70 셸정렬 (1) 셸정렬 (shell sort) 일정한간격 (interval) 으로떨어져있는자료들끼리부분집합을구성하고각부분집합에있는원소들에대해서삽입정렬을수행하는작업을반복하면서전체원소들을정렬하는방법 전체원소에대해서삽입정렬을수행하는것보다부분집합으로나누어정렬하게되면비교연산과교환연산감소 셸정렬의부분집합 부분집합의기준이되는간격을매개변수 h 에저장 한단계가수행될때마다 h의값을감소시키고셸정렬을순환호출 h가 1이될때까지반복 셸정렬의성능은매개변수 h 의값에따라달라진다. 정렬할자료의특성에따라매개변수생성함수를사용 일반적으로사용하는 h의값은원소개수의 1/2을사용하고한단계수행될때마다 h의값을반으로감소시키면서반복수행 70

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

72 셸정렬 (2) 셸정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을셸정렬방법으로정렬하는과정을살펴보자. 1 원소의개수가 8 개이므로매개변수 h 는 4 에서시작한다. h=4 이므로간격이 4인원소들을같은부분집합으로만들면 4개의부분집합이만들어진다

73 셸정렬 (3) 첫번째부분집합 {69, 16} 에대해서삽입정렬을수행하여정렬. 삽입정렬수행전 삽입정렬수행후 두번째부분집합 {10, 8} 에대해서삽입정렬수행. 삽입정렬수행전 삽입정렬수행후

74 셸정렬 (4) 세번째부분집합 {30, 31} 에대해서삽입정렬을수행하는데, (30<31) 이므로자리교환은이루어지지않는다 네번째부분집합 {2, 22} 에대해서삽입정렬을수행하는데, (2<22) 이므로자리교환은이루어지지않는다

75 셸정렬 (5) 2이제h를2로변경하고다시셸정렬시작. h=2 이므로간격이 2인원소들을같은부분집합으로만들면 2개의부분집합이만들어진다 첫번째부분집합 {16, 30, 69, 31} 에대해서삽입정렬을수행하여정렬 삽입정렬수행전 삽입정렬수행후

76 셸정렬 (6) 두번째부분집합 {8, 2, 10, 22} 에대해서삽입정렬을수행하여정렬. 삽입정렬수행전 삽입정렬수행후

77 셸정렬 (7) 3이제h를1로변경하고다시셸정렬시작. h=1 이므로간격이 1인원소들을같은부분집합으로만들면 1개의부분집합이만들어진다. 즉, 전체원소에대해서삽입정렬을수행하고셸정렬이완성된다. 삽입정렬수행전 삽입정렬수행후

78 셸정렬 (8) 셸정렬알고리즘 shellsort(a[],n) interval n; while (interval 1) do { interval interval/2; for (i 0; i<interval; i i+1) do { intervalsort(a[], i, n, interval); } } end shellsort() [ 알고리즘 11-6] 78

79 셸정렬 (9) 셸정렬알고리즘분석 메모리사용공간 n개의원소에대하여 n개의메모리와매개변수 h에대한저장공간사용 연산시간 비교횟수 처음원소의상태에상관없이매개변수 h 에의해결정 일반적인시간복잡도 : O(n 1.25 ) 셸정렬은삽입정렬의시간복잡도 O(n 2 ) 보다개선된정렬방법 79

80 셸정렬 (10) 셸정렬프로그램 01 class Sort{ 02 public void intervalsort(int a[], int begin, int end, int interval){ 03 int i, j, item; 04 for(i=begin+interval; i<=end; i=i+interval){ 05 item = a[i]; 06 for(j=i-interval; j>=begin && item<a[j]; j-=interval) 07 a[j+interval] = a[j]; 08 a[j+interval] = item; 09 } 10 } public void shellsort(int a[], int size){ 13 int i, j, interval, t=0; 14 interval = size/2; 15 while(interval >= 1){ 16 for(i=0; i<interval; i++) 17 intervalsort(a, i, size-1, interval); [ 예제 11-5] >> 계속 80

81 셸정렬 (11) 18 System.out.printf("\n셸정렬 %d 단계 : interval =%d >> ", ++t, [ 예제interval); 11-5] 19 for(j=0; j<size; j++) 20 System.out.printf("%d ", a[j]); 21 System.out.println(); 22 interval /= 2; 23 } 24 } 25 } class Ex11_5{ 28 public static void main(string args[]){ 29 int a[] = {69, 10, 30, 2, 16, 8, 31, 22}; 30 int size = a.length; 31 Sort S = new Sort(); 32 System.out.printf("\n정렬할원소 : "); 33 for(int i=0; i<a.length; i++) 34 System.out.printf(" %d", a[i]); 35 System.out.println(); 36 S.shellSort(a, size); 37 } 38 } 81

82 셸정렬 (12) 실행결과 82

83 병합정렬 (1) 병합정렬 (merge sort) 여러개의정렬된자료의집합을병합하여한개의정렬된집합으로만드는방법 부분집합으로분할 (divide) 하고, 각부분집합에대해서정렬작업을완성 (conquer) 한후에정렬된부분집합들을다시결합 (combine) 하는분할정복 (divide and conquer) 기법사용 병합정렬방법의종류 2-way 병합 : 2개의정렬된자료의집합을결합하여하나의집합으로만드는병합방법 n-way 병합 : n개의정렬된자료의집합을결합하여하나의집합으로만드는병합방법 83

84 병합정렬 (2) 2-way 병합정렬 : 세가지기본작업을반복수행하면서완성 ⑴ 분할 (divide) : 입력자료를같은크기의부분집합 2개로분할한다. ⑵ 정복 (conquer) : 부분집합의원소들을정렬한다. 부분집합의크기가충분히작지않으면순환호출을이용하여다시분할정복기법을적용한다. ⑶ 결합 (combine) : 정렬된부분집합들을하나의집합으로통합한다. 84

85 병합정렬 (3) 병합정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을병합정렬방법으로정렬하는과정을살펴보자. 1 분할단계 : 정렬할전체자료의집합에대해서최소원소의부분집합이될때까지분할작업을반복하여 1개의원소를가진부분집합 8개를만든다. 85

86 병합정렬 (4) 2 병합단계 : 2 개의부분집합을정렬하면서하나의집합으로병합한다. 8 개의부분집합이 1 개로병합될때까지반복한다. 86

87 병합정렬 (5) 병합정렬알고리즘 mergesort(a[],m,n) if (a[m:n] 의원소수 > 1) then { 전체집합을두개의부분집합으로분할 ; mergesort(a[],m,middle); mergesort(a[],middle+1,n); merge(a[m:middle],a[middle+1:n]); } end mergesort() [ 알고리즘 11-7] 87

88 병합정렬 (6) 병합정렬알고리즘분석 메모리사용공간 각단계에서새로병합하여만든부분집합을저장할공간이추가로필요 원소 n개에대해서 (2 x n) 개의메모리공간사용 연산시간 분할단계 : n개의원소를분할하기위해서 log 2 n번의단계수행 병합단계 : 부분집합의원소를비교하면서병합하는단계에서최대 n번의비교연산수행 전체병합정렬의시간복잡도 : O(n log 2 n) 88

89 병합정렬 (7) 병합정렬프로그램 01 class Sort{ 02 private int sorted[] = new int [30]; public void merge(int a[], int m, int middle, int n){ 05 int size = a.length; 06 int i, j, k, t; 07 i = m; 08 j = middle+1; 09 k = m; 10 while(i<=middle && j<=n){ 11 if(a[i] <= a[j]) sorted[k] = a[i++]; 12 else sorted[k] = a[j++]; 13 k++; 14 } 15 if(i>middle){ 16 for(t=j; t<=n; t++, k++) 17 sorted[k] = a[t]; [ 예제 11-8] >> 계속 89

90 병합정렬 (8) 18 } 19 else{ 20 for(t=i; t<=middle; t++, k++) 21 sorted[k] = a[t]; 22 } for(t=m; t<=n; t++) 25 a[t] = sorted[t]; 26 System.out.printf("\n 병합정렬 >> "); 27 for(t=0; t<size; t++) 28 System.out.printf("%3d ", a[t]); 29 } public void mergesort(int a[], int m, int n) { 32 int middle; 33 if(m<n){ 34 middle = (m+n)/2; 35 mergesort(a, m, middle); [ 예제 11-5] >> 계속 90

91 병합정렬 (9) 36 mergesort(a, middle+1, n); 37 merge(a, m, middle, n); 38 } 39 } 40 } class Ex11_6{ 43 public static void main(string args[]){ 44 int a[] = {69, 10, 30, 2, 16, 8, 31, 22}; 45 int size = a.length; 46 Sort S = new Sort(); 47 System.out.printf("\n정렬할원소 : "); 48 for(int i=0; i<a.length; i++) 49 System.out.printf(" %d", a[i]); 50 System.out.println(); 51 S.mergeSort(a, 0, size-1); 52 } 53 } [ 예제 11-5] >> 계속 91

92 병합정렬 (10) 실행결과 92

93 기수정렬 (1) 기수정렬 (radix sort) 원소의키값을나타내는기수를이용한정렬방법 정렬할원소의키값에해당하는버킷 (bucket) 에원소를분배하였다가버킷의순서대로원소를꺼내는방법을반복하면서정렬 원소의키를표현하는기수만큼의버킷사용 예 ) 10진수로표현된키값을가진원소들을정렬할때에는 0부터 9까지 10개의버킷사용 키값의자리수만큼기수정렬을반복 키값의일의자리에대해서기수정렬을수행하고, 다음단계에서는키값의십의자리에대해서, 그리고그다음단계에서는백의자리에대해서기수정렬수행 한단계가끝날때마다버킷에분배된원소들을버킷의순서대로꺼내서 다음단계의기수정렬을수행해야하므로큐를사용하여버킷을만든다. 93

94 기수정렬 (2) 기수정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을기수정렬방법으로정렬하는과정을살펴보자. 키값이두자리십진수이므로, 10개의버킷을사용하여기수정렬을두번반복한다. 94

95 기수정렬 (3) 초기상태 : 큐를사용하여 0 부터 9 까지 10 개의버킷을만든다. 95

96 기수정렬 (4) 1 키값의일의자리에대해서기수정렬수행 정렬할원소의일의자리값에따라서순서대로버킷에분배 96

97 기수정렬 (5) 버킷에분배된원소들을순서대로꺼내서저장하기 97

98 기수정렬 (6) 2 키값의십의자리에대해서기수정렬수행 정렬할원소의십의자리값에따라서순서대로버킷에분배 98

99 기수정렬 (7) 버킷에분배된원소들을순서대로꺼내서저장하기 99

100 기수정렬 (8) 기수정렬알고리즘 radixsort(a[], n) for (k 1; k n; k k+1) do { for (i 0; i < n; i i+1) do { k 번째자릿수값에따라서해당버킷에저장한다 ; enqueue(q[k], a[i]); } p -1; for (i 0; i 9; i i+1) do { while (Q[i] NULL) do { p p+1; a[p] dequeue(q[i]); } } } end radixsort() [ 알고리즘 11-8] 100

101 기수정렬 (9) 기수정렬알고리즘분석 메모리사용공간 원소 n개에대해서 n개의메모리공간사용 기수 r에따라버킷공간이추가로필요 연산시간 연산시간은정렬할원소의수 n과키값의자릿수 d와버킷의수를결정하는기수 r에따라서달라진다. 정렬할원소 n개를 r개의버킷에분배하는작업 : (n+r) 이작업을자릿수 d 만큼반복 수행할전체작업 : d(n+r) 시간복잡도 : O(d(n+r)) 101

102 힙정렬 (1) 힙정렬 (heap sort) 9장의힙자료구조를이용한정렬방법 힙에서는항상가장큰원소가루트노드가되고삭제연산을수행하면항상루트노드의원소를삭제하여반환 최대힙에대해서원소의개수만큼삭제연산을수행하여내림차순으로정렬수행 최소힙에대해서원소의개수만큼삭제연산을수행하여오름차순으로정렬수행 힙정렬수행방법 ⑴ 정렬할원소들을입력하여최대힙구성 ⑵ 힙에대해서삭제연산을수행하여얻은원소를마지막자리에배치 ⑶ 나머지원소에대해서다시최대힙으로재구성원소의개수만큼 ⑵~⑶ 을반복수행 102

103 힙정렬 (2) 힙정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을힙정렬방법으로정렬하는과정을살펴보자. 초기상태 : 정렬할원소가 8개이므로노드가 8개인완전이진트리를만들고, 최대힙으로구성한다. 103

104 힙정렬 (3) 1 힙에삭제연산을수행하여루트노드의원소 69를구해서배열의마지막자리에저장, 나머지원소들에대해서최대힙으로재구성 104

105 힙정렬 (4) 2 힙에삭제연산을수행하여루트노드의원소 31을구해서배열의비어있는마지막자리에저장, 나머지힙을최대힙으로재구성 105

106 힙정렬 (5) 3 힙에삭제연산을수행하여루트노드의원소 30을구해서배열의비어있는마지막자리에저장, 나머지원소들에대해서최대힙으로재구성 106

107 힙정렬 (6) 4 힙에삭제연산을수행하여루트노드의원소 22를구해서배열의비어있는마지막자리에저장, 나머지원소들에대해서최대힙으로재구성 107

108 힙정렬 (7) 5 힙에삭제연산을수행하여루트노드의원소 16을구해서배열의비어있는마지막자리에저장, 나머지원소들에대해서최대힙으로재구성 108

109 힙정렬 (8) 6 힙에삭제연산을수행하여루트노드의원소 10을구해서배열의비어있는마지막자리에저장, 나머지원소들에대해서최대힙으로재구성 109

110 힙정렬 (9) 7 힙에삭제연산을수행하여루트노드의원소 8을구해서배열의비어있는마지막자리에저장, 나머지원소들에대해서최대힙으로재구성 110

111 힙정렬 (10) 8 힙에삭제연산을수행하여루트노드의원소 2를구해서배열의비어있는마지막자리에저장, 나머지힙을최대힙으로재구성하는데공백힙이되었으므로힙정렬종료 111

112 힙정렬 (11) 힙정렬알고리즘 heapsort(a[]) n a.length-1; for (i n/2; i 1; i i-1) do // 배열 a[] 를히프로변환 makeheap(a, i, n); for (i n-1; i 1; i i-1) do { // 히프의루트노드원소를 temp a[1]; // 배열의비어있는 a[1] a[i+1]; // 마지막자리에저장 a[i+1] temp; makeheap(a, 1, i); } end heapsort() [ 알고리즘 11-9] 112

113 힙정렬 (12) 힙정렬알고리즘의힙재구성연산알고리즘 makeheap(a[], h, m) for (j 2*h; j m; j 2*j) do { if (j < m) then if (a[j] < a[j+1]) then j j+1; if (a[h] a[j]) then exit; else a[j/2] a[j]; } a[j/2] a[h]; end makeheap() [ 알고리즘 11-10] 113

114 힙정렬 (13) 힙알고리즘분석 메모리사용공간 원소 n개에대해서 n개의메모리공간사용 크기 n의힙저장공간 연산시간 힙재구성연산시간 n개의노드에대해서완전이진트리는 log 2 (n+1) 의레벨을가지므로완전이진트리를힙으로구성하는평균시간은 O(log 2 n) n개의노드에대해서 n번의힙재구성작업수행 평균시간복잡도 : O(n log 2 n) 114

115 트리정렬 (1) 트리정렬 (tree sort) 8장의이진탐색트리를이용하여정렬하는방법 트리정렬수행방법 ⑴ 정렬할원소들을이진탐색트리로구성 ⑵ 이진탐색트리를중위우선순회방법 중위순회경로가오름차순정렬이된다. 115

116 트리정렬 (2) 트리정렬수행과정 정렬되지않은 {69, 10, 30, 2, 16, 8, 31, 22} 의자료들을트리정렬방법으로정렬하는과정을살펴보자. 1 원소가 8개를차례대로트리에삽입하여이진탐색트리구성 2 이진탐색트리를중위우선순회방법으로순회하면서저장 116

117 트리정렬 (3) 117

118 트리정렬 (4) 트리정렬알고리즘 treesort(a[], n) for (i 0; i < n; i i+1) do insertbst(bst, a[i]); // 이진탐색트리의삽입연산 inorder(bst); // 중위순회연산 end treesort() [ 알고리즘 11-11] 118

119 트리정렬 (5) 트리알고리즘분석 메모리사용공간 원소 n개에대해서 n개의메모리공간사용 크기 n의이진탐색트리저장공간 연산시간 노드한개에대한이진탐색트리구성시간 : O(log 2 n) n개의노드에대한시간복잡도 : O(n log 2 n) 119

120 정렬알고리즘비교 120

121 자바로배우는쉬운자료구조