여기서 우리는 몇 가지 정렬 방법을 볼 것입니다. 200개 이상의 정렬 기술이 있습니다. 우리는 그들 중 몇 가지를 볼 것입니다. 일부 정렬 기술은 비교 기반 정렬이고 일부는 비비교 기반 정렬입니다.
비교 기반 정렬 기술에는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등이 있습니다. 이러한 기술에서 값이 비교되고 서로 다른 단계에서 정렬된 위치에 배치되기 때문에 이러한 기술은 비교 기반 정렬로 간주됩니다. 여기에서 이러한 기술의 시간 복잡도를 볼 수 있습니다.
| 분석 유형 | 거품 정렬 | 선택 정렬 | 삽입 정렬 | 병합 정렬 | 빠른 정렬 | 힙 정렬 |
|---|---|---|---|---|---|---|
| 최상의 사례 | O(n 2 ) | O(n 2 ) | O(n) | O(로그 n) | O(로그 n) | O(로그인) |
| 평균 사례 | O(n 2 ) | O(n 2 ) | O(n 2 ) | O(로그 n) | O(로그 n) | O(로그 n) |
| 최악의 경우 | O(n 2) | O(n 2 ) | O(n 2 ) | O(로그 n) | O(n 2 ) | O(로그 n) |
일부 정렬 알고리즘은 비비교 기반 알고리즘입니다. 그 중 일부는 기수 정렬, 버킷 정렬, 개수 정렬입니다. 여기에서는 정렬하는 동안 두 요소가 비교되지 않기 때문에 비비교 기반 정렬입니다. 기술이 약간 다릅니다. 이제 다양한 유형의 분석을 기반으로 이들 간의 차이점을 살펴보겠습니다.
| 분석 유형 | 기수 정렬(k는 최대 자릿수) | 카운팅 정렬(k는 카운트 배열의 크기) | 버킷 정렬(k는 버킷 수) |
|---|---|---|---|
| 최상의 사례 | 오(nk) | O(n + k) | O(n + k) |
| 평균 사례 | 오(nk) | O(n + k) | O(n + k) |
| 최악의 경우 | 오(nk) | O(n + k) | O(n 2 ) |
정렬 기술은 다른 매개변수를 사용하여 비교할 수도 있습니다. 일부 정렬 알고리즘은 내부 정렬 알고리즘이고 일부는 외부 정렬 알고리즘입니다. 추가 공간이 필요하지 않은 이러한 알고리즘을 내부 정렬 알고리즘이라고 합니다. 퀵 정렬, 힙 정렬 알고리즘이 제자리에 있습니다. 그러나 병합 정렬은 out-place 정렬 기술입니다.
일부 알고리즘은 온라인이고 일부는 오프라인입니다. 정렬 프로세스가 진행되는 동안 알고리즘이 새 요소를 수락하는 경우 이를 온라인 정렬 알고리즘이라고 합니다. 위에서 언급한 기술 중 삽입 정렬은 온라인 정렬 기술입니다.