2018/03

[정렬 알고리즘] Merge Sort(병합 정렬)

§Merge Sort 배열을 절반으로 두개의 서브 배열로 나누는걸 서브 배열의 원소가 한개가 될때까지 반복한 후 정렬 하며 다시 병합하는 알고리즘 mergeSort(arr[], 1, r) If r > 1: 배열을 나눌 중간점을 구한다 : middle m = (1+r)/2 mergeSort(arr, 1, m)을 호출한다. mergeSort(arr, m+1, r)을 호출한다. 두개의 정렬되어 반으로 나누어진 배열을 합병한다 : merge(arr, 1, m, r) Time Complexity : O(n*logn) //T(n) = 2T(n/2) +O(n) Auxiliary Space: O(n) 언어 ( C ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

[정렬 알고리즘] Recursive Insertion Sort(재귀 삽입 정렬)

§Revursive Insertion Sort 삽입 정렬을 재귀로 표현한 것 만약 배열 사이즈가 1이거나 더 작을 경우 return 한다. 재귀 함수에 n-1 배열 사이즈를 인수로 넘겨준다. 부분 배열의 마지막 원소를 올바른 위치로 정렬한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 //////////////////////////////// // Recursive Insertion Sort // 재귀 삽입 정렬 //////////////////////////////// #include void insertSortRecursive(int *arr,int n) { if..

[정렬 알고리즘] Insertion Sort(삽입정렬)

§Insertion Sort 손에 카드를 정렬 하는 것처럼 하나의 카드씩 제자리로 정렬하는 알고리즘이다. 현재 위치 k원소를 (k-1)부터 1까지 원소와 비교하며 자리를 바꾸어 나간다. 1 부터 n-1까지 위 행위를 반복한다. &example Time Complexity: O(n2) as there are two nested loops. 코드( C ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 //////////////////////////////// // Insertion Sort // 삽입 정렬 ////////////////////////////////..

[정렬 알고리즘] Recursive Bubble Sort(재귀 버블 정렬)

§Recursive Bubble Sort 버블 정렬보다 성능/구현 상으로는 이점이 없지만 자신이 버블정렬에 대해 이해하는지 확인하는 좋은 질문이 될 수 있다. 배열 size가 1이면 return 한다. 현재 부분배열의 마지막 원소를 결정한다. 마지막 원소를 제외한 부분 배열에 대해 반복한다. 코드 ( C ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 //////////////////////////////// // Recursive Bubble Sort // 재귀 버블 정렬 //////////////////////////////// #include void swap(i..

[정렬 알고리즘] Bubble Sort(버블정렬, 거품정렬)

§버블 정렬 잘못된 순서로 정렬된 인접한 원소를 반복적으로 교체하는 정렬 알고리즘이다. Example: First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second P..

[정렬 알고리즘] Seletion Sort (선택 정렬)

§선택 정렬 정렬 되지 않은 부분에서 최소 요소(오름차순 일때)를 반복적으로 찾아 시작 부분에 배치하여 배열을 정렬한다. 주어지는 배열은 두가지 경우를 생각 해볼 수 있다. 부분 배열이 이미 정렬 되었을때 부분 배열이 정렬 되지 않은 상태일때 Following example explains the above steps: arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find t..