본문 바로가기

Algorithm

(5)
Sorting Algorithm을 비판적으로 바라보자. Sorting Algorithm을 비판적으로 바라보자.#1. 첫번째 의문 quick sort가 가장 좋고 빠르다며, 그래서 이름도 quick sort라며! 그런데 heap sort, merge sort는 왜 존재하며 왜 필요하지?어디에 쓰이고 있길래 살아남은 거지? 세 sorting algorithm(Quick sort, Merge sort, Heap sort)의 expected-Time Complexity는 O(n log n)으로 모두 동일하다. 하지만 Space Complexity는 merge sort만 Sorting하고자 하는 데이터의 크기 만큼이다. 그러면 일단 heap sort는 그렇다치고, 어떻게 Merge Sort가 살아남았을까? 한정된 메모리 상황에서 ‘빅 데이터'를 Sorting 해야하는..
[Sorting] 5. Non-Comparison Sorting - Counting Sort, Radix Sort non - Comparisons Sorting AlgorithmCounting SortSpace Complexity : in-place 알고리즘이 아니다. buffer를 필요로 한다.Time Complexity : O(n + k)Radix Sort에 대해 알아보기 전에 Count Sort에 대해서 먼저 알아보자. Count Sort에서 사용된 알고리즘이 Radix Sort에서 사용된다. 즉 Radix Sort는 Count Sort의 확장판이라고 할 수 있다. Count Sort는 말 그대로 몇 개인지 개수를 세어 정렬하는 방식이다. 정렬하고자 하는 값 중 최대값에 해당하는 값을 size로 하는 임시 배열을 만든다. 만들어진 배열의 index 중 일부는 정렬하고자 하는 값들이 되므로 그 값에는 그 값들의 ..
[Sorting] 3. Quick Sort Quick SortSpace-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n log n) Sorting기법 중 가장 빠르다고 해서 quick이라는 이름이 붙여졌다. 하지만 Worst Case에서는 시간복잡도가 O(n^2)가 나올 수도 있다. 하지만 constant factor가 작아서 속도가 빠르다. 원리Quick Sort 역시 Divide and Conquer 전략을 사용하여 Sorting이 이루어진다. Divide 과정에서 pivot이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partit..
[Sorting] 2. Merge Sort 2. Merge SortSpace-Complexity = 입력 배열 크기의 보조 메모리를 사용한다. Time-Complexity = O(n log n) 원리기본적인 개념으로는 n개의 원소를 가진 배열을 정렬할 때, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. Divide and conquer라는, 분할하여 정복한다의 원리인 것이다. 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법이다. 단 분할(divide)해서 정복했으니 정복(conquer)한 후에는 결합(combine)의 과정을 거쳐야 한다. Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우에는 ( 원소 하나인..
[Sorting] 1. Insertion Sort (삽입 정렬) / Bubble Sort (버블 정렬) 1. Insertion Sort Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n^2) 원리n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬할 순서라고 가정하면, 0부터 i-1까지의 원소들은 정렬되어있다는 가정하에, i번째 원소와 i-1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서(i+1)의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다. c code>1234567891011121314151617//Insertion Sortvoid insertion_sort(int * arr,..