삽입정렬은 카드놀이와 같다. 하나의 카드가 들어오기 전에 손에 쥔 카드는 순서대로 정렬이 되고 새로운 카드는 자신의 위치를 바로 찾아간다. 즉, 정렬이 되어 있고 그 정렬된 상태에서 원소는 자신의 위치를 찾는 것이다. 평균적으로 O(n^2)의 성능을 보이며 다른 정렬 알고리즘의 일부로 사용되기도 한다. 단, 대입이 많고, 데이터의 상태, 단일 크기에 따라 성능의 편차가 심하다.
가장 유명하고, 정렬 알고리즘의 표준이다시피 한 방법이다. 이 알고리즘을 보면 정말 사기(-_-ㅋ)라는 생각이 드는데, 실제로 코딩을 해 보면, 퀵 정렬이 코드가 가장 긴데, 실행 시간은 퀵 정렬이 다른 알고리즘들보다 기막힐 정도로 짧다. 중간값이라는 뭔가 적당한(모호한) 값을 선택해야 하고, 최악의 경우 시간 복잡도가 O(n^2)에 메모리 복잡도가 O(n)이 될 가능성까지 있는 알고리즘이 어쩜 이럴 수 있을까? 하지만 반대로 말하면 퀵 정렬은 자료가 이미 정렬되어 있는 상태를 파악하는 그 민감도를 극대화했기 때문에 이만치 빠를 수 있다.
중간값을 기준으로 데이터를 반으로 갈라 놓고, 양측에 대해서 재귀적으로 또 중간값을 설정해 정렬을 또 수행한다는 발상은 대단히 깔끔하고 멋지다. 이런 걸 분할 정복법이라고 한다. 이게 '퀵 정렬'이 아니었으면 '이분 검색'을 따라 '이분 정렬'이라는 이름이 붙었을 것이다.
퀵 정렬은 본디 재귀적으로 정의되지만, 사용자 정의 스택을 구현해서 비재귀적으로 만들 수도 있다. 또한, 원소 개수가 한 자리 수로 떨어졌을 때는 또 재귀호출을 하는 게 아니라 삽입 정렬을 해서 능률을 극대화하기도 한다.
(용묵님의 설명을 빌려왔다.. 왜? -_-;; 묻지마셈!)
합병정렬 또는 병합정렬이라고도 하는데 말 그대로다. 쪼개어진 데이터 리스트들을 합치는 방법으로 합병, 반복 합병, 순환 합병, 자연 합병 등 다양한 방법이 존재하는 정렬 알고리즘으로 역시나 단점은 메모리 낭비 문제이다. 원판들이 있고 원판들을 합쳐야 하기 때문에 최종적인 리스트 크기만큼의 메모리 공간이 더 필요하게 된다. 뭐 굳이 메모리를 추가로 사용하지 않고 정렬하는 방법도 가능하지만... 그러면 속도가 문제가 되니... 싫어도 그냥 쓰는 수 밖에... 속도는 O(nlogn)으로 상당히 양호(최악과 평균이 동일한데 과연 이걸 양호하다고 해야하나... -_-ㅋ)하며 안정성 또한 어느정도 보장되어 있다.
합병 정렬에서 최악의 경우와 평균 연산 시간이 모두 O(nlogn)인 반면, 정렬되는 데이터 수에 비례하여 기억장소가 추가로 필요한 힙 정렬은 최대 또는 최소 힙 구조를 이용한다. 만일 이진 트리를 기반으로 한다면 이 알고리즘의 연산 시간은 O(Tree_Depth)이다.
※아래 두 정렬은 저도 아직 남들에게 설명할 만큼 이해하지도 못했고 아직 프로그램 짜보지도 못해서 용목님의 설명으로 대신합니다.
삽입 정렬을 일정한 간격으로 띄엄띄엄 수행한 뒤(예를 들어 d=40, 13, 4, ...점차 조밀하게), 전체적으로는 대부분 정렬되어 있는 그 결과 역시 삽입 정렬로 종합한다(d=1). 이 알고리즘은 삽입 정렬의 특성을 응용한 것뿐인데 삽입 정렬과는 비교할 수 없을 정도로, O(n log n) 알고리즘에 버금가는 성능을 자랑한다. 부가적인 메모리도 전혀 필요없어서 비용 대 성능도 대단히 뛰어나다.
하지만 이 알고리즘은 '띄엄띄엄'을 어떻게 설정하는게 가장 좋을지가 엄밀하게 알려져 있지 않아 시간 복잡도를 O(n^2)나 O(n log n)처럼 정확하게 계산하기 힘들다. 다만, 그 띄엄띄엄 수열이 서로 소가 되게 정의해야 성능이 좋아진다는 것이 알려져 있다.
기발함 그 자체이다. 네 자리 수가 있으면, 백 자리, 십 자리, 일 자리 순으로 차례차례 정렬을 한다는 게 기본 전략이다. 자릿수가 고정되어 있으니 각 자릿수별 정렬은 1 몇 개, 2 몇 개인지를 파악하는 식으로, 안정성이 있고(기수 정렬을 이해하는데 중요하다. 이미 정렬된 배열 원소들의 상대적 순서가 반드시 보존되어야 한다.) 시간 복잡도도 O(n)인 방법으로 한다.
이 정렬법은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 O(n)이어서 정수 같은 건 기가 막힐 정도로 정렬 속도가 빠르다. 물론 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에 부동소숫점처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 매우 특이하고 멋진 알고리즘임은 틀림없다.
이 프로그램에서 구현한 기수 정렬은 한 자릿수는 8비트, 즉 한 바이트로 매우 직관적이며 컴퓨터가 처리하기에도 좋은 형태이다. 링크드 리스트 대신 원소 크기가 256인 기수 테이블 배열을 써 성능을 극대화했다. 현재의 BITOF 매크로는 숫자의 작은 자리수가 왼쪽에 먼저 저장되는 리틀 엔디언 컴퓨터에 맞게 작성된 것이며, BITOF 매크로와 count, index 배열을 바꾸면 임의의 기수와 자릿수를 써서 정렬할 수도 있다.
invalid-file