Shell Sort

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

Shellsort overview 정렬을 공부하면서 여러 종류들을 접해봤는데 이건 또 신선하네요.. i 번째 이전의 모든 원소를 살피는 삽입 정렬과 달리 일정 간격(h)만큼과 비교하는 정렬입니다. 그래서 h 간격에 따라 부분 정렬되어 있습니다. 물론 간격이 1인 경우는 모든 원소가 오름차순으로 정렬되어 있다는 것을 의미하게 됩니다. h-soring 당연한 얘기지만 간격이 크면 부분 정렬된 배열의 크기 자체는 작습니다. 반대로 간격이 작으면 작을수록 배열 전체가 정렬된 상태에 가까워집니다. Shellsort example: increments 7, 3, 1 Shellsort: intuition 그렇다면 이 논리가 어떻게 적용 가능한 것일까요? 바로 작은 간격으로 h 정렬을 수행했을 때도 큰 간격의 h 정렬..