Merge Sort

Duplicate keys 일반적으로 대량의 데이터에 대해 정렬을 수행하는 것은 중복되는 key를 기준으로 정렬을 적용하는 경우가 많습니다. 위처럼 '도시 - 시간' 형태의 데이터라면 도시를 기준으로 정렬하게 되는 것이죠. 원래는 중복된 key를 포함하는 데이터에 대해 퀵정렬을 수행하는 경우 quadratic(2차) 시간이 걸린다는 문제점이 있었으나, 병합 정렬을 이용하여 그 시간을 획기적으로 줄일 수 있게 되었죠. Duplicate keys: the problem 하지만 일반적인 병합 정렬 방식을 적용하게 되면, key가 모두 동일한 경우에 대해서는 quadratic 시간이 소요될 것입니다. 이를 방지하기 위해 paritioning item(기준 아이템)과 동일한 것이 확인되는 순간 작업을 멈춰서 Nl..

comparator는 comparable과 비교되는 자바의 인터페이스로 제가 이해하기엔 좀 어렵네요. 당장 자바로 알고리즘을 풀이할 것도 아니라서 과감히 패스하겠습니다! Stability 때로는 정렬 기준(key)이 여러 개가 될 수도 있습니다. 예를 들어 이름을 기준으로 정렬한 다음, 2번째 열의 숫자를 기준으로 정렬하고 싶을 수도 있다는 것이죠. 하지만 두 번째 열을 기준으로 정렬하는 순간 이름 기준의 정렬이 깨지는 것을 원하지 않을 수도 있습니다. 즉, 두 번째 정렬을 수행하더라도 기존의 정렬이 유지되길 원하는 경우 어떻게 이를 구현할 수 있을까요? Stability: insertion sort 삽입 정렬은 정렬이 수행되는 매 스텝(i)에서 이전에 정렬된 것들은 건드리지 않습니다. 비교 대상이 더 ..

Complexity of sorting 정렬 알고리즘의 계산 복잡도를 정리하는 내용입니다. 상한선은 당연히 최대치/최악의 경우를 나타내고 있으므로 guarantee라는 표현이 쓰였습니다. 하한선은 이보다 더 좋을 수 없는 최선의 경우가 증명된 것을 뜻합니다. 최적 알고리즘은 X라는 문제에 대해 최선의 것으로 증명된 경우에 해당하며 상한선과 하한선 사이에 위치합니다. Decision tree (for 3 distinct a, b, and c) 의사 결정 나무를 통해 정렬에 대한 결정을 시각화할 수 있습니다. 여기서는 각 비교를 합쳐 맨 마지막에 세 개의 값을 비교한 결과물을 얻어낼 수 있음을 보여주고 있습니다. 트리의 높이는 비교를 가장 많이 해야 하는 최악의 경우를 뜻하게 됩니다. Compare-base..

Two classic sorting algorithms 지금까지 배웠던 정렬들과 달리, 앞으로 배울 두 정렬인 '병합 정렬'과 '퀵 정렬'은 엄청나게 효율적이고 지금까지도 널리 쓰이는 공신력 있는 알고리즘입니다. Mergesort 병합 정렬의 기본 아이디어는, 배열을 반으로 쪼개고 그 결과를 합치는 작업을 재귀적으로 반복하는 것입니다. Abstract in-place merge demo 캡쳐본이라 영상이 아니지만, 방법은 이렇습니다. 우선 맨 처음의 배열을 복사한 aux 배열을 생성합니다. 그리고 이를 반으로 쪼개어 왼쪽의 첫 번째, 오른쪽의 첫 번째 원소에 인덱스 i, j 를 부여합니다. 그리고 오리지날 배열의 첫 번째 인덱스는 k가 됩니다. i, j 를 비교하여 더 작은 것을 k 자리에 넣고 k는 1..