Quick Sort Algorithm (한국어)
Quick Sort는 다음과 같이 Divide and Conquer의 개념을 기반으로하는 다른 정렬 기법 중 하나입니다. 병합 정렬. 그러나 빠른 정렬에서는 모든 무거운 작업 (주요 작업)이 배열을 하위 배열로 나누면서 수행되고 병합 정렬의 경우 모든 실제 작업이 하위 배열을 병합하는 동안 발생합니다. 빠른 정렬의 경우 결합 단계는 아무것도하지 않습니다.
파티션-교환 정렬이라고도합니다. 이 알고리즘은 목록을 세 가지 주요 부분으로 나눕니다.
- Pivot 요소보다 작은 요소
- Pivot 요소 (Central 요소)
- 피벗 요소
피벗 요소는 배열의 모든 요소가 될 수 있으며 첫 번째 요소, 마지막 요소 또는 임의의 요소가 될 수 있습니다. 이 자습서에서는 맨 오른쪽 요소 또는 마지막 요소를 피벗으로 사용합니다.
예 : {52, 37, 63, 14, 17, 8, 6, 25} 배열에서 . 따라서 첫 번째 통과 후 목록이 다음과 같이 변경됩니다.
{6 8 17 14 25 63 37 52}
따라서 첫 번째 패스 후 피벗은 해당 위치에 설정되며 모든 요소는 왼쪽에 있고 모든 요소는 오른쪽보다 더 큽니다. 이제 6 8 17 14 및 63 37 52는 두 개의 개별 sunarray로 간주되며 동일한 재귀 논리가 적용됩니다. 전체 배열이 정렬됩니다.
빠른 정렬 작동 방식
다음은 빠른 정렬 알고리즘과 관련된 단계입니다.
- 우리의 경우 배열의 마지막 인덱스 인 pivot는 처음으로 배열을 나눕니다.
- 빠른 정렬에서는이 분할이라고합니다. 배열을 2 개의 하위 배열로 나누는 것은 간단하지 않지만 분할의 경우 배열 요소가 너무 배치되어 피벗보다 작은 모든 요소가 피벗의 왼쪽에 있고 피벗보다 큰 모든 요소가 배치됩니다. 오른쪽에 있습니다.
- 피벗 요소는 최종 정렬 위치에 있습니다.
- 왼쪽 및 오른쪽 요소는 정렬되지 않을 수 있습니다.
- 그런 다음 하위 배열, 피벗 왼쪽 요소 및 피벗 오른쪽 요소를 선택하고 하위 배열에서 피벗을 선택하여 분할을 수행합니다.
값이있는 배열을 생각해 봅시다. {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}
아래에는 주어진 배열을 얼마나 빨리 정렬하는지에 대한 그림 표현.
1 단계에서 마지막 요소를 피벗 (이 경우 6)이고 partitioning를 호출하므로 다시 정렬합니다. g 배열은 6가 최종 위치에 배치되고 왼쪽에는 그보다 작은 모든 요소가 있고 오른쪽에는 모든 요소가 있습니다. 그보다 큽니다.
그런 다음 왼쪽의 하위 배열과 오른쪽의 하위 배열을 선택하고 피벗을 선택합니다. 위의 다이어그램에서 3는 왼쪽 하위 배열의 피벗으로, 11는 오른쪽 하위 배열의 피벗으로 사용합니다.
그리고 다시 partitioning.
빠른 정렬 알고리즘 구현
아래에는 빠른 정렬 알고리즘을 구현하는 간단한 C 프로그램이 있습니다.
빠른 정렬의 복잡성 분석
파티셔닝이 불균형 하위 배열로 이어지는 배열의 경우 왼쪽에 요소가없고 모든 요소가있는 경우 피벗보다 크므로 오른쪽에 있습니다.
불균형 하위 배열을 계속 얻으면 실행이 ning time은 최악의 경우입니다. O(n2)
파티셔닝이 거의 동일한 하위 배열로 이어지는 것처럼 실행 시간이 가장 좋습니다. O (n * log n).
최악의 시간 복잡성 : O (n2)
최상의 시간 복잡성 : O (n * log n)
평균 시간 복잡도 : O (n * log n)
공간 복잡도 : O (n * log n)
지금 아시다시피, 분할 후에 생성 된 하위 배열이 분할되면 균형이 맞지 않으면 빠른 정렬을 완료하는 데 더 많은 시간이 걸립니다. 누군가가 마지막 인덱스를 항상 피벗으로 선택한다는 것을 알고 있다면 의도적으로 배열을 제공하여 빠른 정렬을위한 최악의 실행 시간을 초래할 수 있습니다.
이를 방지하려면 무작위로 선택할 수 있습니다. 피벗 요소도 있습니다. 알고리즘에 어떤 차이도 만들지 않을 것입니다. 배열에서 임의의 요소를 선택하고 마지막 인덱스의 요소와 교체하고 피벗으로 만들고 빠른 정렬을 수행하는 것입니다.
- 빠른 정렬에 필요한 공간은 매우 적으며
O(n*log n)추가 공간 만 필요합니다. - 빠른 정렬은 안정적인 정렬 기술이 아니므로 정렬하는 동안 목록에서 유사한 두 요소의 발생을 변경할 수 있습니다.
이제 빠른 정렬을 배웠습니다. 알고리즘을 사용하면 이러한 정렬 알고리즘과 해당 응용 프로그램을 확인할 수 있습니다.
- 삽입 정렬
- 선택 정렬
- 버블 정렬
- 병합 정렬
- 힙 정렬
- 카운팅 정렬