추천, 2022

에디터의 선택

빠른 정렬과 병합 정렬의 차이점

빠른 정렬 및 병합 정렬 알고리즘은 상당히 비슷한 방식으로 작동하는 나누기 및 정복 알고리즘을 기반으로합니다. 빠른 정렬과 병합 정렬 간의 이전 차이점은 빠른 정렬에서 피벗 요소가 정렬에 사용된다는 것입니다. 반면에 병합 정렬에서는 정렬을 수행 할 때 피벗 요소를 사용하지 않습니다.

두 가지 정렬 기법, 빠른 정렬 및 병합 정렬은 요소 세트가 분리 된 다음 다시 정렬 된 후 분할 및 정복 방법을 기반으로합니다. 빠른 정렬은 일반적으로 큰 요소 집합을 정렬하기 위해 병합 정렬보다 더 많은 비교를 요구합니다.

비교 차트

비교 근거빠른 정렬Merge sort
배열 요소의 파티셔닝요소 목록의 분할은 반드시 반으로 분할되지는 않습니다.배열은 항상 절반 (n / 2)으로 나뉩니다.
최악의 경우의 복잡성O (n2)O (n log n)
잘 작동합니다.더 작은 배열모든 유형의 어레이에서 정상적으로 작동합니다.
속도작은 데이터 세트를위한 다른 정렬 알고리즘보다 빠릅니다.모든 유형의 데이터 세트에서 일관된 속도.
추가 저장 공간 요구 사항적게
능률큰 배열의 경우 비효율적입니다.보다 효율적입니다.
정렬 방법내부의외부

빠른 정렬의 정의

빠른 정렬 은 짧은 배열에 대해 빠르기 때문에 널리 사용되는 정렬 알고리즘입니다. 요소 집합은 더 이상 나눌 수 없을 때까지 반복적으로 여러 부분으로 나뉩니다. 빠른 정렬은 파티션 교환 정렬 이라고도 합니다 . 요소를 분할 할 때 핵심 요소 (피벗이라고 함)를 사용합니다. 하나의 파티션에는 핵심 요소보다 작은 요소가 들어 있습니다. 다른 파티션에는 핵심 요소보다 큰 요소가 포함되어 있습니다. 요소는 재귀 적으로 정렬됩니다.

A가 정렬되어야하는 n 개의 숫자의 배열 A [1], A [2], A [3], ..., A [n]이라고하자. 빠른 정렬 알고리즘은 다음 단계로 구성됩니다.

  1. 첫 번째 요소 또는 임의의 요소를 키로 선택하면 키 = A (1)로 가정합니다.
  2. "낮은"포인터는 두 번째 포인터에 배치되고 "위"포인터는 배열의 마지막 요소, 즉 low = 2 및 up = n에 위치합니다.
  3. 지속적으로 "낮음"포인터를 한 위치만큼 증가시킵니다 (A [낮음]> 키).
  4. 끊임없이 (A [위로] <= 키까지) "위"포인터를 한 위치 씩 감소시킵니다.
  5. 업이 낮은 인터체인지보다 큰 경우 A [낮음]과 A [위로].
  6. 5 단계의 조건이 실패 할 때까지 3, 4, 5 번 단계를 반복합니다 (예 : 위로 <= 낮음). 그런 다음 A [위로] 키를 교환합니다.
  7. 키의 왼쪽에있는 요소가 키보다 작고 키 오른쪽의 요소가 키보다 크면 배열은 두 개의 하위 배열로 분할됩니다.
  8. 위의 절차는 전체 배열이 정렬 될 때까지 반복적으로 하위 배열에 적용됩니다.

장점과 단점

좋은 평균적인 행동을합니다. 빠른 정렬의 실행 시간 복잡성은 버블 정렬, 삽입 정렬 및 선택 정렬과 같은 알고리즘보다 빠릅니다. 그러나, 그것은 복잡하고 매우 재귀 적이기 때문에 큰 배열에 적합하지 않습니다.

병합 정렬 정의

병합 정렬 은 분할 및 정복 전략을 기반으로하는 외부 알고리즘입니다. 요소는 하나의 요소가 남을 때까지 하위 배열 (n / 2)로 다시 나누어지며 정렬 시간이 현저하게 줄어 듭니다. 보조 어레이를 저장하기 위해 추가 스토리지를 사용합니다. Merge sort는 세 개의 배열을 사용하는데 두 개는 각 반을 저장하는 데 사용되고 세 번째 배열은 최종 정렬 된 목록을 저장하는 데 사용됩니다. 각 배열은 재귀 적으로 정렬됩니다. 마지막으로 배열의 요소 크기를 만들기 위해 하위 배열을 병합합니다. 목록은 항상 빠른 정렬과 다른 절반 (n / 2)으로 나뉩니다.

A를 A [1], A [2], ........., A [n]으로 정렬되는 n 개의 요소 수의 배열이라고하자. 병합 정렬은 주어진 단계를 따릅니다.

  1. (A [1], A [2]), (A [3], A [4]), (A [3], A [4])에있는 요소가 2로 정렬 된 약 n / 2 정렬 된 하위 배열로 배열 A를 나눕니다. k], A [k + 1]), (A [n-1], A [n]) 서브 어레이는 정렬 된 순서로 존재해야한다.
  2. 각 쌍의 쌍을 결합하여 크기가 4 인 정렬 된 하위 배열 목록을 얻습니다. (A [1], A [2], A [3], A [4]), ..., (A [k-1], A [k], A A [n-3], A [n-2], A [n-1], A [n])을 생성한다.
  3. 단계 2는 크기 n의 정렬 된 배열이 하나만있을 때까지 반복적으로 수행됩니다.

장점과 단점

병합 정렬 알고리즘은 정렬에 관련된 요소의 수에 관계없이 정확히 동일하고 정확하게 수행합니다. 큰 데이터 세트로도 잘 작동합니다. 그러나 메모리의 많은 부분을 소모합니다.

빠른 정렬과 병합 정렬 간의 주요 차이점

  1. 병합 정렬에서 배열은 두 개의 반쪽 (예 : n / 2)으로 분리되어야합니다. 반대로, 빠른 정렬에서는 목록을 동등한 요소로 나눌 필요가 없습니다.
  2. 빠른 정렬의 최악의 경우의 복잡도는 최악의 조건에서 훨씬 더 많은 비교가 필요하므로 O (n2)입니다. 대조적으로, 병합 정렬은 동일한 최악의 경우와 평균 사례 복잡성, 즉 O (n log n)을 갖습니다.
  3. 병합 정렬은 크거나 작은 모든 유형의 데이터 세트에서 잘 작동 할 수 있습니다. 반대로, 빠른 정렬은 대형 데이터 세트에서 제대로 작동하지 않습니다.
  4. 작은 데이터 세트와 같은 경우에는 빠른 정렬이 병합 정렬보다 빠릅니다.
  5. Merge sort는 보조 배열을 저장하기 위해 추가 메모리 공간이 필요합니다. 반면에 빠른 정렬은 추가 저장 공간을 필요로하지 않습니다.
  6. 병합 정렬은 빠른 정렬보다 효율적입니다.
  7. 빠른 정렬은 정렬 할 데이터가 주 메모리에서 한 번에 조정되는 내부 정렬 방법입니다. 반대로 병합 정렬은 정렬 할 데이터를 동시에 메모리에 저장할 수없고 일부는 보조 메모리에 보관해야하는 외부 정렬 방법입니다.

결론

빠른 정렬은 더 빠른 경우이지만 일부 상황에서는 비효율적이며 병합 정렬과 비교할 때 많은 비교를 수행합니다. 병합 정렬은 비교가 덜 필요하지만 빠른 정렬에는 O (log n)의 공간이 필요하지만 추가 배열을 저장하는 데는 0 (n)의 추가 메모리 공간이 필요합니다.

Top