C++에서 가장 빠른 정렬 알고리즘

Muhammad Adnan Ashraf 2023년6월20일

C++ C++ Sorting

이 기사에서는 어떤 조건에서 어떤 정렬 알고리즘이 가장 잘 수행되는지 설명합니다. 조건에는 데이터 구조의 유형, 정렬되는 데이터의 크기, 데이터 배열 및 데이터 요소의 범위가 포함됩니다.

먼저 정렬 알고리즘을 설명하겠습니다. 그런 다음 다양한 데이터 구조에서 다양한 알고리즘의 성능을 설명합니다.

정렬 알고리즘은 임의의 데이터 구조에 저장된 요소를 정렬하는 방법입니다.

모든 정렬 알고리즘의 적합성은 입력 데이터 크기, 데이터 구조 유형, 데이터 배열, 시간 및 공간 복잡성, 데이터 범위에 따라 다릅니다.

일부 정렬 알고리즘은 배열 데이터 구조에서 더 잘 수행되는 반면 일부는 힙에서 더 잘 수행됩니다. 또한 일부 알고리즘은 레코드의 가장 중요한 정수 키가 레코드 수보다 훨씬 작은 경우(예: 카운팅 정렬) 속도가 빠릅니다.

그렇다면 가장 빠른 알고리즘은 무엇입니까? 대답은 간단해 보이지만 복잡도 표를 보고 시간 복잡도가 가장 낮은 것을 선택하십시오(즉, 점근적 증가).

그러나 실제로 기본 데이터의 구조적 속성을 보지 않고 주어진 데이터에서 알고리즘 A가 알고리즘 B보다 더 잘 수행하거나 그 반대라고 직접 말할 수는 없습니다.

따라서 주어진 기본 데이터 구조에 대해 다양한 시나리오에서 특정 적합성을 가진 정렬 알고리즘을 논의하여 답변을 제공하려고 합니다.

링크 목록은 노드에 데이터를 저장하는 선형 데이터 구조입니다. 노드는 데이터와 다음 노드에 대한 포인터를 포함하는 링크 목록의 기본 빌딩 블록입니다.

링크 목록을 정렬하는 가장 좋은 정렬 알고리즘은 병합 정렬입니다. 병합 정렬은 병합 작업의 출력을 저장하기 위한 보조 배열에 대한 요구 사항이 없기 때문에 배열보다 연결 목록에서 더 잘 수행됩니다.

배열과 달리 연결된 목록 노드는 메모리에서 연속적일 필요가 없습니다. 대신 노드를 다른 메모리 위치에 분산시킬 수 있습니다.

또한 배열과 달리 연결 리스트의 중앙에 O(1) 추가 공간과 O(1) 시간에 값을 넣을 수 있습니다.

결과적으로, 링크 리스트를 정렬하면서 병합 정렬의 병합 연산을 구현하기 위해 점근적으로 증가하는 추가적인 공간이 필요하지 않다. 따라서 병합 정렬은 (nlog n)의 링크 목록을 정렬합니다.

병합 정렬의 구현은 여기에서 찾을 수 있습니다.

배열은 연속적인 메모리 위치에 데이터를 저장하는 선형 데이터 구조입니다. 데이터 유형은 배열에서 동일해야 합니다.

다음은 다양한 정렬 알고리즘과 그 적합성에 대한 목록입니다.

배열의 정렬된 영역에 새로운 항목을 추가할 때 항목을 거의 이동하지 않기 때문에 삽입 정렬은 배열이 거의 정렬되었을 때 선택될 수 있습니다.

정렬된 배열에 대한 삽입 정렬의 시간 복잡도는 O(n)이지만 동일한 배열에 대한 빠른 정렬의 시간 복잡도는 O(n^2)입니다. 자세한 내용은 여기에서 확인할 수 있습니다.
Quick Sort는 In-Place Sorting을 하기 때문에 Array에 적합하다. 또한 퀵 정렬 알고리즘은 정렬 과정에서 추가 공간을 필요로 하지 않습니다.
병합 정렬의 경우 추가 공간을 확보하고 해제해야 합니다. 따라서 병합 정렬 알고리즘의 실행 시간이 늘어납니다.

평균적으로 병합 및 빠른 정렬은 O(nlogn) 시간 복잡도를 갖지만 병합 정렬은 추가 O(n) 공간을 차지합니다. 여기서 n은 정렬할 배열의 크기입니다. 여기에서 자세한 내용을 확인할 수 있습니다.
배열에 저장된 데이터(예: 정수, 단어 및 고정 크기 문자가 있는 문자열)를 사전순 순서로 정렬하려는 경우 기수 정렬을 사용합니다. 기수 정렬은 병렬 시스템을 사용할 때 수행됩니다.
카운팅 정렬은 레코드의 가장 큰 정수 키가 레코드 수보다 훨씬 작은 경우에 사용됩니다.
버킷 정렬은 배열에 저장된 데이터가 일정 범위 내에서 고르게 분포되어 있을 때 가장 효율적입니다.

트리는 노드에 데이터를 저장하는 비선형 데이터 구조입니다. 최상위 노드를 루트 노드라고 합니다. 루트 노드는 자식 노드에 추가로 연결됩니다.

많은 유형의 트리가 있지만 여기서는 이진 검색 트리(BST)에 대해서만 설명합니다.

트리 정렬은 BST에 가장 적합한 정렬 알고리즘으로 간주됩니다. 또한 BST의 순서 순회는 요소를 정렬된 순서로 제공합니다. 마찬가지로 힙 정렬은 힙에 저장된 요소를 정렬하는 데 가장 적합합니다.

해시 테이블, 레드-블랙 트리 등과 같은 다른 유형의 데이터 구조에서 모든 정렬 알고리즘을 분석할 수도 있습니다.

다음 섹션에서는 다양한 정렬 알고리즘의 복잡성과 안정성을 설명하는 치트 시트를 제공합니다.

알고리즘 복잡성 치트 시트

표를 살펴보기 전에 정렬 알고리즘과 관련된 일반적인 용어에 대해 논의해 보겠습니다.

키가 동점인 경우 키의 원래 순서를 유지하는 경우 알고리즘이 안정적입니다. 예를 들어 S 시퀀스에 다음 쌍이 있다고 가정합니다.

S = <(1,"Alex"), (3,"Bill"),(2,"Ananth"), (1, "Jack")>

이제 위의 시퀀스를 정수 키로 정렬한다고 가정합니다. 그러면 안정적인 정렬 알고리즘이 위의 시퀀스를 다음과 같이 정렬합니다.

Stably Sorted S = <(1,"Alex"),(1, "Jack"),(2,"Ananth"),(3,"Bill")>

안정적인 정렬은 (1, "Alex") 및 (1, "Jack") 쌍의 원래 순서를 보존합니다. 그러나 불안정한 정렬은 이를 보장하지 않습니다.

일정한 양의 보조 메모리를 사용하는 경우 정렬이 적절합니다. 이는 문제 크기가 커져도 추가 메모리 요구 사항이 증가하지 않음을 의미합니다.

예를 들어 O(1) 공간 복잡도가 있는 아래 치트 시트의 모든 정렬이 제자리에 있습니다.

기본 정렬 용어에 대한 배경 지식을 충분히 이해한 후 정렬 알고리즘의 복잡도 테이블을 살펴보겠습니다. 이 표는 특정 문제 상황에서 가장 적합한 정렬 알고리즘을 선택하는 데 도움이 될 수 있습니다.

이름	시간 복잡도(최고)	시간 복잡도(평균)	시간 복잡도(최악)	공간 복잡성	안정
버블 정렬	`Ω (n)`	`Θ (n^2)`	`O(n^2)`	`Ο (1)`	예
선택 정렬	`Ω (n^2)`	`Θ (n^2)`	`O(n^2)`	`Ο (1)`	아니요
삽입 정렬	`Ω (n)`	`Θ (n^2)`	`O(n^2)`	`Ο (1)`	예
병합 정렬	`Ω (n log(n))`	`Θ (n log(n))`	`Ο (n log(n))`	`Ο (n)`	예
빠른 정렬	`Ω (n log(n))`	`Θ (n log(n))`	`O(n^2)`	`Ο (log(n))`	아니요
힙 정렬	`Ω (n log(n))`	`Θ (n log(n))`	`Ο (n log(n))`	`Ο (1)`	아니요
카운팅 정렬	`Ω (n + k)`	`Θ (n + k)`	`Ο (n + k)`	`Ο (K)`	예
기수 정렬	`Ω (nk)`	`Θ (nk)`	`Ο (nk)`	`Ο (nk)`	예