전체 글 (55) 썸네일형 리스트형 정렬(Sorting) - 합병 정렬 (Merge Sort) 합병 정렬 (Merge Sort) 이미 정렬된 리스트 2개 → 1개의 정렬된 리스트 시간 복잡도 : O(n-l+1) . [ n-l+1 = 원소 수] init List 3 4 8 10 2 6 8 9 ↑ l ↑ m ↑ m+1 ↑ n i1 i2 merged List 2 3 4 6 8 8 9 10 반복 합병 정렬 입력 열의 길이가 1인 n개의 정렬된 List를 합병하여 길이가 2인 List 생성 길이가 2인 n/2개의 List를 합병하여 길이가 4인 List 생성 길이가 n인 List로 최종 합병될 때까지 계속 정렬(Sorting) - 퀵 정렬 (Quick Sort) pivot, i, j를 이용하여 i는 왼쪽에서 오른쪽으로 이동하며 pivot보다 큰 값을 찾고 j는 오른쪽에서 왼쪽으로 이동하며 pivot보다 작은 값을 찾은 후 a[i] a[j]를 swap i를 기준으로 분할 (Partition) 후 단계 반복 평균 수행시간 최소 순환호출 사용 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] left right (26 5 37 1 61 11 59 15 48 19) 1 10 ↑ pivot ↑ i ↑ j 19 37 ↑ i ↑ j 15 61 pivot i j (11 5 19 1 15) 26 (59 61 48 37) (11 5 19 1 15) 1 5 (1 5) 11 (19 15) 1 5 1 2 15 19 4 5 (59 61 48 37) 7 10 (48.. 정렬(Sorting) - 삽입 정렬 (Insertion Sort) 단계 삽입 원소를 기존의 정렬된 부분 리스트 속에 끼워 넣기 삽입 원소의 위치를 옮기면서 처음 단계의 insert 반복 적용 분석 $\sum_{i=1}^{n-1}(i+1)=n^2$ → O($n^2$) 최선 : 오름차순으로 정렬된 상태 최악 : 내림차순으로 정렬된 상태 data 양이 적을 때 사용하면 빠름 dyeoma.tistory.com/40 삽입 정렬 (Insertion Sort) 기본 단계 insert 함수 template void Insert (const T& e, T* a, int i) { // 정렬된 리스트에 e 삽입 // a[0] = -∞; while (e < a[i]){ a[i+1] = a[i]; i--; } a[i+1] = e; } 최악 : i+1 삽입 정렬 함수 templa.. dyeom.. 퀵 정렬 (Quick Sort) WorkHorse void QuickSort (T* a, const int left, const int right) { // Workhorse // pivot = a[left] // a[left] pivot );// j : right→left. pivot보다 큰 값 찾기 if (i 삽입 정렬 (Insertion Sort) 기본 단계 insert 함수 template void Insert (const T& e, T* a, int i) { // 정렬된 리스트에 e 삽입 // e = 끼워넣을 값 // a = 배열 // i = 현재까지 정렬된 index // a[0] = -∞; while (e < a[i]){ a[i+1] = a[i]; i--; } a[i+1] = e; } 최악 : i+1 삽입 정렬 함수 template void InsertionSort (T* a, const int n) { // a[1:n] 오름차순 정렬 for (int j=2; j 이진 탐색 (Binary Search) 알고리즘 template int BinarySearch (T* a, const T& k, const int n) { // 정렬된 array에서 k 탐색 for (int left=0; right=n-1; ) { int middle = (left + right) / 2; if ( k > a[middle] ) left = middle + 1; else if ( k < a[middle] ) right = middle - 1; else// k==a[middle] return middle; } return -1;// 미발견 } 최선 : 1 최악 : log n 시간복잡도 = O(log n) 순차 탐색 (Sequential Search) 알고리즘 Template int SeqSearch (T* a, const int n, const T& k) { // a[0] → a[n-1]까지 왼쪽에서 오른쪽으로 탐색 // k와 같은 키 값을 가진 a[i] 중 가장 작은 index 반환 // 미존재시 -1 반환 int i; for (i=0; i=n)// 미존재 return -1; return i; } 최선 : 1 최악 : n 평균 : (n+1)/2 ∴ 시간복잡도 = O(n) 탐색 (Search) - 순차탐색, 이진탐색 1. 순차 탐색(Sequential Search) 리스트를 왼쪽→오른쪽, 또는 오른쪽→왼쪽으로 record를 검사 key들은 순서 X ex) [0] [1] [2] [3] [4] 8 5 15 7 12 k=5 (존재) : return 1 k=11 (미존재) : return -1 dyeoma.tistory.com/35 순차 탐색 (Sequential Search) 알고리즘 Template int SeqSearch (T* a, const int n, const T& k) { // a[0] → a[n-1]까지 왼쪽에서 오른쪽으로 탐색 // k와 같은 키 값을 가진 a[i] 중 가장 작은 index 반환 // 미존재시 -1 반환 int i; for (i=0; i =.. dyeoma.tistory.com 2. 이진 .. 이전 1 2 3 4 5 6 7 다음
