자료구조 & 알고리즘 정렬과탐색알고리즘 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com
목 차 기초적인정렬알고리즘 고급정렬알고리즘 탐색알고리즘 2
정 렬 (Sort) 정렬 (sort) 의개념 순서없이배열되어있는자료들을재배열하는것 정렬의대상 : 레코드 정렬의기준 : 정렬키 (sort key) 필드 정렬방법의분류 실행방법에따른분류 : 비교식정렬, 분산식정렬 정렬장소에따른분류 내부정렬 : 컴퓨터메모리내부에서정렬 정렬속도는빠르지만자료의양이메인메모리의용량에따라제한된다. 교환방식, 삽입방식, 병합방식, 분배방식, 선택방식 외부정렬 : 메모리의외부인보조기억장치에서정렬 내부정렬로처리할수없는대용량의자료를정렬 병합방식 : 2-way 병합, n-way 병합 3
기초적인정렬알고리즘 기초적인정렬알고리즘 선택정렬 버블정렬 삽입정렬 쉘정렬 고급정렬알고리즘 탐색알고리즘 4
선택정렬 선택정렬 1. 먼저정렬되지않은리스트에서가장작은원소의위치를탐색 2. 정렬되지않은리스트의시작위치에있는원소와교환 3. 각각의비교및교환후에, 리스트의경계를한개의원소만큼이동 10 20 30 70 100 90 60 50 80 40 1 i j n 5
선택정렬 (cont d) 초기배열 30 40 10 50 20 선택정렬동작과정 원소교환 #1 이후 10 40 30 50 20 원소교환 #2 이후 10 20 30 50 40 원소교환 #3 이후 10 20 30 50 40 원소교환 #4 이후 10 20 30 40 50 수행시간 : (n-1) + (n-2) +... + 2 + 1 = O (n 2 ) Worst case Average case 6
선택정렬알고리즘 선택정렬 (cont d) Selection_Sort(A[], n) // 배열 A[1,..., n] 을정렬 for i 1 to n - 1 1 smallest i; for j i+1to n A[i] A[smallest]; if (A[j] < A[smallest]) then smallest j; 수행시간 : 1 + 2 +... + (n 1) + n = O (n 2 ) 2 3 1 의 for 루프는 n-1번반복 2 에서가장큰수를찾기위한비교횟수 : 1, 2,..., n - 1 3 의교환은상수시간작업 7
선택정렬알고리즘분석 메모리사용공간 선택정렬 (cont d) n 개의원소에대하여 n 개의메모리사용 비교횟수 1 단계 : 첫번째원소를기준으로 n 개의원소비교 2 단계 : 두번째원소를기준으로마지막원소까지 n - 1 개의원소비교 3 단계 : 세번째원소를기준으로마지막원소까지 n - 2 개의원소비교 i 단계 : i 번째원소를기준으로 n - i 개의원소비교 어떤경우에서나비교횟수가같으므로시간복잡도는 O (n 2 ) 8
버블정렬 버블정렬 1. 가장작은원소가정렬되지않은리스트로부터버블되어정렬된서브리스트로이동 2. 각각의비교및교환후에, 리스트의경계를한개의원소만큼이동 10 20 30 70 100 90 60 50 80 40 1 i j n 9
버블정렬 (cont d) 버블정렬동작과정 초기배열 30 40 10 50 20 30 40 10 20 50 30 40 10 20 50 30 10 40 20 50 1 단계완료이후 10 30 40 20 50 수행시간 : 1 + 2 +... + (n-1) + n = O (n 2 ) Worst case Average case 10
버블정렬알고리즘 버블정렬 (cont d) Bubble_Sort (A[], n) // A[1... n] 을정렬 for i 1 downto n-1 for j n downto i-1 if (A[j] < A[j-1]) then A[j] A[j-1]; 1 2 3 수행시간 : (n - 1) + (n - 2) + +2+1 = O(n 2 ) 1 의 for 루프는 n-1 번반복 2 에서가장큰수를찾기위한비교횟수 : n - 1, n - 2,, 2, 1 3 의교환은상수시간작업 11
버블정렬 (cont d) 버블정렬알고리즘 (cont d) Bubble_Sort (A[], n) //A[1,...,n] 을정렬 변형된버블정렬알고리즘 for i 1 downto n - 1 state TRUE; for j n downto i 1 if (A[j] < A[j-1]) then A[j] A[j-1]; state FALSE; if (state = TRUE) then return; 12
버블정렬 (cont d) 버블정렬알고리즘의분석 메모리사용공간 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 ) 이된다. 13
삽입정렬 삽입정렬의개념 1. 각단계에서, 정렬되지않은리스트의첫번째원소를선택 2. 선택된원소를소가정렬된리스트의적절한위치로삽입 10 50 80 30 70 20 60 100 90 40 1 i j n 14
삽입정렬 (cont d) 삽입정렬동작과정 초기배열 30 10 20 40 50 10 temp 데이터 30 이동 30 30 20 40 50 10 temp 데이터 10 삽입 10 30 20 40 50 20 temp 데이터 30 이동 10 30 30 40 50 20 temp 데이터 20 삽입 10 20 30 40 50 40 temp 데이터 40 삽입 10 20 30 40 50 50 temp 데이터 50 삽입 10 20 30 40 50 40 temp 수행시간 : O (n 2 ) Worst case : 1 + 2 + + (n-2) + (n-1) Average case : ½ (1 + 2 + + (n-2) + (n-1)) 15
삽입정렬알고리즘 Insertion_Sort (A[], n) for i 2 to n j i-1; temp A[i]; 삽입정렬 (cont d) //A[1,...,n] 을정렬 1 while (j 1 and temp < A[j]) A[j + 1] A[j]; j--; A[j + 1] temp; 배열이거의정렬되어있는상태로입력되는경우에가장매력적인알고리즘 수행시간 : 1 의 for 루프는 n-1 번반복 2 의삽입은최악의경우 i - 1 회비교 Worst case : 1 + 2 +... + (n - 2) + (n - 1) = O(n 2 ) 2 Average case : ½ (1 + 2 +... + (n - 2) + (n - 1)) = O(n 2 ) 16
삽입정렬 (cont d) 삽입정렬알고리즘의분석 메모리사용공간 n 개의원소에대하여 n 개의메모리사용 연산시간 최선의경우 : 원소들이이미정렬되어있을때비교횟수가최소 이미정렬되어있는경우에는바로앞자리원소와한번만비교 전체비교횟수 = n - 1 시간복잡도 : O(n) 최악의경우 : 모든원소가역순으로되어있을경우비교횟수가최대 전체비교횟수 = 1 + 2 + 3 + + (n - 1) = n(n - 1)/2 시간복잡도 : O(n 2 ) 삽입정렬의평균비교횟수 = n(n - 1) / 4 평균시간복잡도 : O(n 2 ) 17
쉘정렬 쉘정렬의개념 일정한간격 (interval) 으로떨어져있는데이터들끼리부분집합을구성하고, 각부분집합에있는원소들에대해서삽입정렬을수행 전체원소에대해서삽입정렬을수행하는것보다부분집합으로나누어정렬 --> 비교와교환연산감소 쉘정렬에서는 7- 정렬, 4- 정렬등의용어를주로사용 4- 정렬의예 30 75 15 40 10 65 35 20 90 55 95 25 18
쉘정렬알고리즘 쉘정렬 (cont d) Shell_Sort (A[], n) // A[1,..., n] 을정렬 interval n; while (interval 1) do interval interval / 2; for (i 0; i < interval; i i + 1) do // interval 간격만큼의원소들끼리쉘정렬수행 Interval_Sort(A[], i, n, interval); end Shell_Sort() Sort() 19
쉘정렬알고리즘의분석 메모리사용공간 쉘정렬 (cont d) n 개의원소에대하여 n 개의메모리와매개변수 h 에대한저장공간사용 연산시간 비교횟수 : 처음원소의상태에상관없이매개변수 h 에의해결정 일반적인시간복잡도 : O(n 1.25 ) 쉘정렬은삽입정렬의시간복잡도 O(n 2 ) 보다개선된정렬방법 20
고급정렬알고리즘 기초적인정렬알고리즘 고급정렬알고리즘 퀵정렬 병합정렬 탐색알고리즘 21
퀵정렬 (quick sort) 의개념 퀵정렬 정렬할전체원소에대해서정렬을수행하지않고, 기준값을 중심으로왼쪽부분집합과오른쪽부분집합으로분할하여정렬 기준값 : 피봇 (pivot) 왼쪽부분집합 : 기준값보다작은원소들을이동 오른쪽부분집합 : 기준값보다큰원소들을이동 퀵정렬은다음의두가지기본작업을반복수행 분할 (divide) : 정렬할자료들을기준값을중심으로두개의부분집합으로분할 정복 (conquer) 부분집합의원소들중에서기준값보다작은원소들은왼쪽부분집합으로, 기준값보다 큰원소들은오른쪽부분집합으로정렬 부분집합의크기가 1 이하로충분히작지않으면순환호출을이용하여다시분할 22
퀵정렬의동작과정 퀵정렬 (cont d) first last 기준값설정 31 8 48 73 11 3 20 29 65 15 first mid last 부분집합으로분할 8 11 3 73 31 48 20 29 65 15 first mid last 각각독립적으로정렬 3 8 11 15 20 29 31 48 65 73 평균수행시간 : O(nlogn) 최악의경우수행시간 : O(n2) 23
퀵정렬알고리즘 Quick_Sort(A[], first, last) if (first < last) then 퀵정렬 (cont d) mid = Partition(A, first, last); Quick_Sort(A, first, mid-1); Quick_Sort(A, mid+1, last); Partition(A[], first, last) // A[first,..., last] 을정렬 // 분할, 분할후기준값의위치값을반환 // 왼쪽부분배열정렬 // 오른쪽부분배열정렬 배열 A[first,..., last] 의원소들을 A[last] 을기준으로양쪽으로재배치하고, 기준값 (A[last]) 이자리한위치를반환한다 ; 24
퀵정렬알고리즘 (cont d) 분할알고리즘 퀵정렬 (cont d) Partition(A[], first, last) pivot A[last]; // 마지막원소를기준값으로선택 i first - 1; for j first to last -1 if (A[j] pivot) then A[++i] A[j]; A[i+1] A[last]; // 기준값을가운데로위치시킨다. return i+1; // 기준값의위치값을반환 25
퀵정렬알고리즘분석 메모리사용공간 퀵정렬 (cont d) n 개의원소에대하여 n 개의메모리사용 연산시간 최선의경우 기준값에의해서원소들이왼쪽부분집합과오른쪽부분집합으로정확히n / 2 개씩이등이되는경우가반복되어수행단계수가최소가되는경우 최악의경우 기준값에의해원소들을분할하였을때 1 개와 n - 1 개로한쪽으로치우쳐분할되는경우가반복되어수행단계수가최대가되는경우 평균시간복잡도 : O(n log 2 n) ) 같은시간복잡도를가지는다른정렬방법에비해서자리교환횟수를줄임으로써더빨리실행되어실행시간성능이좋은정렬방법 26
병합정렬 병합정렬 (merge sort) 의개념 여러개의정렬된자료의집합을병합하여한개의정렬된집합으로만드는방법 병합정렬방법의종류 2-way 병합 : 2 개의정렬된자료의집합을결합하여하나의집합으로만드는방법 n-way 병합 : n 개의정렬된자료의집합을결합하여하나의집합으로만드는방법 // 2-way 병합정렬 : 세가지기본작업을반복수행 ⑴ 분할 (divide) : 입력자료를같은크기의부분집합 2개로분할한다. ⑵ 정복 (conquer) : 부분집합의원소들을정렬한다. 부분집합의크기가충분히작지않으면순환호출을이용하여다시분할정복기법을적용한다. ⑶ 결합 (combine) : 정렬된부분집합들을하나의집합으로통합한다. 27
병합정렬의동작과정 병합정렬 (cont d) 부분집합으로분할 31 8 48 73 11 3 20 29 65 15 first mid last 각부분집합을 독립적으로정렬 8 11 31 48 73 3 15 20 29 65 정렬된두부분집합을병합 3 8 11 15 20 29 31 48 65 73 28
병합정렬알고리즘 Merge_Sort(A[],first,last) if (first < last) then 병합정렬 (cont d) mid (first+last)/2 ; mergesort(a, first, mid); mergesort(a, mid+1, last); merge(a, first, mid, last); // A[first,..., last] 을정렬 // first 와 last 사이의중간원소의위치 // 왼쪽부분집합정렬 // 오른쪽부분집합정렬 // 정렬된두부분집합병합 Merge(A[ ], first, mid, last) 정렬되어있는두부분집합 A[first,..., mid] 와 A[mid+1,...,r] 을병합하여정렬된하나의배열 A[first... last] 을만든다. 29
병합정렬 (cont d) 병합정렬알고리즘 : 병합알고리즘 merge(a[],first,mid,last) // A[first... mid] 와 A[mid+1... last] 를병합하여 A[first... last] 을정렬된상태로재구성 // 단, A[first... mid] 와 A[mid+1... last] 는이미정렬부분집합이다. i first; j mid+1; t 1; while (i mid and j last) if (A[i] A[j]) then temp[t++] A[i++]; else temp[t++] A[j++]; while (i mid) temp[t++] A[i++]; while (j last) temp[t++] A[j++]; // 정렬된상태로재구성된 temp 배열을원본배열 A 에복사 i p; t 1; while (i last) A[i++] temp[t++]; 30
병합정렬알고리즘분석 메모리사용공간 병합정렬 (cont d) 각단계에서새로병합하여만든부분집합을저장할공간이추가로필요 원소 n 개에대해서 (2 * n) 개의메모리공간사용 연산시간 분할단계 : n 개의원소를분할하기위해서 log 2 n 번의단계수행 병합단계 : 부분집합의원소를비교하면서병합하는단계에서최대 n 번의 비교연산수행 전체병합정렬의시간복잡도 : O(n log 2 n) 31
탐 색 기초적인정렬알고리즘 고급정렬알고리즘 탐색알고리즘 순차탐색 이진탐색 32
탐 색 (search) 탐색 (search) 의개념 레코드의집합에서주어진키를지닌레코드를찾는작업탐색 주어진키값 : 목표키 (Target Key), 또는탐색키 (Search Key) 탐색의분류 수행되는위치에따른분류 : 내부탐색, 외부탐색 검색방법에따른분류 비교탐색 : 검색대상의키를비교하여탐색 ( 예 : 순차탐색, 이진탐색, 트리탐색 ) 계산탐색 : 계수적인성질을이용한계산으로탐색 ( 예 : 해싱 ) 33
순차탐색 순차탐색의개념 순차탐색알고리즘 목표치를찾기위해리스트의처음부터탐색을시작해서목표치를찾거나리스트에목표치가없다는것이밝혀질때까지탐색을계속한다. 순차탐색은순서가없는리스트일때사용 순차탐색은리스트가작거나, 가끔한번씩탐색할경우에만사용 Sequential_Search(A[ ], n, key) i 0; while (i < n) if (A[i]=key)then return i; i i + 1; return -1; 34
순차탐색의동작과정 순차탐색 (cont d) 0 순서없는리스트에위치한데이터 index a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 1 31!= 73 index a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 2 8!= 73 index a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 3 index a[0] a[1] 48!= 73 a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 73 == 73 35
순차탐색 (cont d) 순차탐색의동작과정 (cont d) 순서없는리스트에탐색실패 0 index a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 1 31!= 90 index a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 4 8!= 90 index a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 10 index a[0] a[1] a[2] a[3] 11!= 90 a[4] a[5] a[6] a[7] a[8] a[9] 31 8 48 73 11 3 20 29 65 15 36
이진탐색알고리즘 이진탐색 이진탐색은배열이정렬되어있을때효율적인알고리즘 순차탐색은매우느리다. 이진탐색알고리즘의조건 탐색할데이터들은정렬된상태이다. 주어진데이터들은유일한키값을가지고있다. Binary_Search(A[ ], first, last, key) mid (first + last)/2; // 검색범위의중간위치값계산 if (key = A[mid]) return mid; else ese if (key < A[mid]) then binarysearch(a[], ayseac first, s, mid-1, key); else if (key > A[mid]) then binarysearch(a[], mid+1, last, key); return -1; 37
이진탐색 (cont d) 이진탐색의동작과정검색데이터 : 21 first mid last 0 4 9 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 4 7 8 10 14 21 22 36 62 77 21 > 14 first 5 mid 7 last 9 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 4 7 8 10 14 21 22 36 62 77 21 < 36 first 5 mid 5 last 6 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 4 7 8 10 14 21 22 36 62 77 21 == 21 38
이진탐색 (cont d) 이진탐색의동작과정 : 탐색실패검색데이터 : 11 first 0 mid 4 last 9 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 4 7 8 10 14 21 22 36 62 77 11 < 14 first mid last 0 1 3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 4 7 8 10 14 21 22 36 62 77 11 > 7 first 2 mid 2 last 3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 4 7 8 10 14 21 22 36 62 77 11 > 8 first mid last a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 3 3 4 7 8 10 14 21 22 36 62 77 11 > 10 first mid last 4 3 3 39
참고문헌 [1] 이지영, C 로배우는쉬운자료구조, 한빛미디어, 2005. [2] 주우석, CᆞC++ 로배우는자료구조론, 한빛미디어, 2005. [3] 천인국, C C 언어로쉽게풀어쓴자료구조, 생능출판사, 2005. [4] 이재규, C 로배우는알고리즘 : 개념과기본알고리즘, 도서출판세화, 2007. [5] 문병로, 쉽게배우는알고리즘 : 관계중심의사고법, 한빛미디어, 2007. [6] 카사이아사오, 진명조역, C 언어로배우는알고리즘입문, 한빛미디어, 2006. [7] Kyle Loudon, 허욱역, Algorithms with C : C 로구현한알고리즘, 한빛미디어, 2006 [8] Wikipedia, http://www.wikipedia.org/. 이강의자료는저작권법에따라보호받는저작물이므로무단전제와무단복제를금지하며, 내용의전부또는일부를이용하려면반드시저작권자의서면동의를받아야합니다. Copyright Clickseo.com. All rights reserved. 40