빠른 정렬 분할 정복 전략을 기반으로 하는 내부 알고리즘입니다. 이것에서:

• 요소 배열은 더 이상 분할할 수 없을 때까지 여러 부분으로 반복적으로 분할됩니다.
• 그것은 또한로 알려져 있습니다 파티션 교환 정렬 .
• 요소를 분할하기 위해 핵심 요소(피벗)를 사용합니다.
• 왼쪽 파티션 하나에는 피벗보다 작은 요소가 모두 포함되고 오른쪽 파티션 하나에는 키 요소보다 큰 요소가 모두 포함됩니다.

병합 정렬 외부 알고리즘이며 분할 및 정복 전략을 기반으로 합니다. 이것에서:

• 요소는 하나의 요소만 남을 때까지 계속해서 두 개의 하위 배열(n/2)로 분할됩니다.
• 병합 정렬은 보조 배열을 정렬하기 위해 추가 스토리지를 사용합니다.
• 병합 정렬은 세 개의 배열을 사용합니다. 여기서 두 개는 각각의 절반을 저장하는 데 사용되고 세 번째 외부 배열은 다른 두 개를 병합하여 최종 정렬 목록을 저장하는 데 사용되며 각 배열은 재귀적으로 정렬됩니다.
• 마지막으로 모든 하위 배열이 병합되어 배열의 'n' 요소 크기가 됩니다.

빠른 정렬과 병합 정렬

배열의 요소 분할: 병합 정렬에서는 배열이 2개의 절반(예: n/2)으로 분할됩니다. 반면 빠른 정렬의 경우 배열은 임의의 비율로 분할됩니다. 퀵 정렬에서는 요소 배열을 동일한 부분으로 나누도록 강요되지 않습니다. 최악의 복잡도 : 퀵 정렬의 최악의 복잡도는 최악의 조건에서 많은 비교가 필요하기 때문에 O(n^2)입니다. 병합 정렬에서는 최악의 경우와 평균적인 경우의 복잡성이 O(n log n)입니다. 데이터 세트 사용: 병합 정렬은 크기(크거나 작음)에 관계없이 모든 유형의 데이터 세트에서 잘 작동할 수 있습니다. 반면 빠른 정렬은 대규모 데이터세트에서는 제대로 작동하지 않습니다. 추가 저장 공간 요구 사항 : 보조 배열을 저장하기 위해 추가 메모리 공간이 필요하므로 병합 정렬이 적용되지 않습니다. 추가 저장 공간이 필요하지 않으므로 빠른 정렬이 적용됩니다. 효율성 : 병합 정렬은 배열 크기나 데이터 세트가 더 큰 경우 빠른 정렬보다 더 효율적이고 빠르게 작동합니다. 빠른 정렬은 배열 크기나 데이터 세트가 더 작은 경우 병합 정렬보다 더 효율적이고 빠르게 작동합니다. 정렬 방식 : 퀵 정렬은 데이터를 메인 메모리에 정렬하는 내부 정렬 방식입니다. 병합 정렬은 정렬하려는 데이터를 메모리에 수용할 수 없고 정렬을 위해 보조 메모리가 필요한 외부 정렬 방법입니다. 안정성 : 병합 정렬은 정렬되지 않은 입력 배열에서와 마찬가지로 정렬된 출력에서도 동일한 값을 갖는 두 요소가 동일한 순서로 나타나므로 안정적입니다. 이 시나리오에서는 빠른 정렬이 불안정합니다. 그러나 코드를 약간 변경하면 안정적으로 만들 수 있습니다. 선호되는 항목: 배열에는 빠른 정렬이 선호됩니다. 연결된 목록에는 병합 정렬이 선호됩니다. 참조 지역성 : Quicksort는 좋은 캐시 지역성을 나타내므로 병합 정렬보다 빠른 정렬이 가능합니다(가상 메모리 환경과 같은 많은 경우).