Randomized Selection
Intuition 중복이 없는 n 개의 원소를 가진 배열에서 i 번째로 큰 원소를 얻고 싶다고 하자. 간단한 방법은 먼저 정렬을 한 뒤 거기서 i 번째 원소를 고르면 된다. 이...
quick sort
Divide and Conquer
Divide and Conquer (분할 정복) 을 배운다. merge, quick sort 를 배우고 이 과정에서 왜 combine 단계가 O(n) 이 되어야 하는지 알아본다. 뒷부분에서는 Big O 뿐만 아니라 master...
C++ 정렬 알고리즘, Merge, Quick, Selection, Insert, Bubble, Heap
Stability 우선 A에 대해 정렬을 하고, 그 정렬된 결과를 바탕으로 B에 대해 정렬했을때 정렬 순서가 그대로 유지되는 알고리즘을 stable 하다고 합니다. merge 가 대표적인 stable 정렬, quick 이...