지금까지 우리가 배워왔던 비교 기반 sorting 알고리즘의 시간 복잡도는 비교 횟수에 따라 달라졌다.아무리 빠르게 정렬해봤자 n log n 보다 빠른 알고리즘은 없었는데, 우리가 과연 O(n)의 시간 안에 정렬할 수 있을까? 선형시간 안에 정렬을 마치기 위해선 비교 기반의 정렬방법으론 불가능한 것을 알았다.그래서 우리는 비교하지 않고 정렬하는 방법을 고안할 수 있는데그 중 하나가 Counting Sort이다. counting sort는 각 요소의 빈도 수를 계산하여 정렬하는 non- comparison 알고리즘이다.이 알고리즘의 핵심 아이디어는 배열에 요소 x가 주어졌을 때, x보다 작은 요소의 개수는 몇개인지 생각하는 것에서부터 시작한다.counting sort가 작동하는 방식은 다음과 같다.배열 ..
Priority Queue는 각각 배열들의 우선순위에 의해 정렬된 큐를 말한다. 사실 Queue도 자료구조시간에 배웠는데, 일반적인 큐가 선입선출 구조를 갖는 반면에 Priority Queue는 먼저 입력했다고 해서 먼저 수행되지는 않다는 차이가 있다. 이런 우선순위 큐는 주로 CPU Scheduling 이나 Huffman coding algorithm을 사용하는 Data Compression, 짧은 길찾기 문제에서 Dijkstra’s algorithm을 사용할 때, Minimum spanning tree 에서 Prim’s algorithm 등등 사용된다. 그럼 Priority Queue는 어떻게 구현할 수 있을까? 이것을 구현하기 위해선 배열과 linked list, 그리고 저번에 배웠던 Heap이 필..
자료구조 시간에 Heap에 대해 이미 들어봤다. 마지막 level의 노드를 제외한 모든 노드가 채워진 완전 이진 트리이고, 모든 노드는 왼쪽부터 순서대로 채워진다. 또한 Max heap의 경우 부모 노드는 자식보다 크거나 같고, Min heap의 부모 노드는 자식 노드보다 작거나 같다. 이런 특징을 갖는 힙은 배열로 구현 가능하다. (자료구조에서 배웠듯이 완전 이진 트리이기 때문에..) 그림의 배열을 보면 왜 배열로 구현할 수 있는지 알기 쉽다. 예를 들어 트리의 4번째 노드를 보자. 트리의 4번째 노드의 왼쪽 노드엔 8번째 노드, 오른쪽 노드에는 9번째 노드가 들어있다. 이제 트리 말고 배열을 봐보자. 아까 말했던 4번째 노드의 Left는 return 2i 이므로 배열의 8번째 공간에 값 2가 들어가있..
In Place In - Place 정렬 알고리즘이란, input data를 정렬하기 위해 각 요소들을 옮기는 과정에서 output을 내기 위해서 추가적인 공간이 필요하지 않은 알고리즘을 말한다. 이것을 설명하기 위한 딱 맞는 알고리즘이 있다. Merge sort를 생각해보자. 우리는 아주 잘게 배열들을 나눠서 merge하는 정렬을 사용했었다. 그런데 이 과정에서 왼쪽 공간의 배열과 오른쪽 공간의 배열을 합치며 정렬할 때, 추가적인 메모리를 갖는 temp array를 선언해서 그 장소에 따로 저장을 했었다. 그렇게 두 배열을 temp array에 합치고 나서 원래의 배열에 다시 복사하여 할당했지만.. 아무튼 Merge sort의 경우 정렬을 할 때 extra space가 필요하므로 In - Place 알..
Quick sort도 divide and conquer 방식을 따르는 알고리즘 중 하나이다. (Divide) 우선 배열 중 하나의 요소를 pivot으로 두고, pivot을 기준으로 배열을 두 개의 subarrays로 나눈다. 여기서 pivot보다 작거나 같은 요소는 왼쪽 subarray로, pivot보다 큰 요소는 오른쪽 subarray에 둔다. (Conquer) Quick sort의 재귀 호출로 두 개의 subarray를 정렬한다. (Combine) 이제 합칠 때, subarray는 이미 정렬되어 있으므로, 합치기 위해 더 필요한 작업은 없다. 이 과정을 슈도 코드로 확인해보자. Quicksort(A,p,r) // A는 배열, p는 start index, r은 end index if p
앞에서 Merge sort와 Insert sort 각각을 알아봤었다. merge sort는 original array에서 left half array와 right half array로 나눠서 각각 정렬하고, 임시로 만든 temp array에 정렬된 값들을 할당하는 것으로 두 array를 합치며 정렬했다. insertion sort는 하나의 element를 선택하고 앞의 정렬된 부분에 삽입하는 방식이었다. https://guhonga.tistory.com/71 Insertion sort, merge sort 소개와 시간복잡도 구하기 (c구현) Insertion sort 삽입정렬은 아직 정렬되지 않은 부분에서, 정렬된 부분에 순서를 유지하면서 반복적으로 삽입하는 알고리즘이다. 우선 첫 번째 인덱스를 선택후 ..