퀵소트 알고리즘 설명 [예제 포함]

빠른 정렬은 병합 정렬에서도 사용되는 개념인 분할 및 정복 알고리즘의 개념을 기반으로 합니다. 차이점은 빠른 정렬에서는 배열을 하위 배열로 분할(또는 분할) 하는 동안 가장 중요하거나 중요한 작업이 수행되는 반면 병합 정렬의 경우 모든 주요 작업 은 하위 배열 을 병합 하는 동안 발생한다는 것입니다. 빠른 정렬의 경우 결합 단계는 중요하지 않습니다.

빠른 정렬은 파티션 교환 정렬 이라고도 합니다 . 이 알고리즘은 주어진 숫자 배열을 세 가지 주요 부분으로 나눕니다.

1. 피벗 요소보다 작은 요소
2. 피벗 요소
3. 피벗 요소보다 큰 요소

피벗 요소는 다양한 방법으로 주어진 숫자에서 선택할 수 있습니다.

1. 첫 번째 요소 선택
2. 마지막 요소 선택(표시된 예)
3. 임의의 요소 선택
4. 중앙값 선택

예: 배열 {51, 36, 62, 13, 16, 7, 5, 24} 에서 24 를 피벗 (마지막 요소)으로 사용합니다. 따라서 첫 번째 패스 후에 목록이 다음과 같이 변경됩니다.

{5 7 16 13 24 62 36 51}

따라서 첫 번째 패스 후에 배열은 선택된 피벗보다 작은 모든 요소가 왼쪽에 있고 모든 큰 요소가 오른쪽에 있도록 정렬됩니다. 피벗은 마침내 배열의 정렬된 버전에 있어야 하는 위치에 있습니다. 이제 하위 배열 {5 7 16 13} 및 {62 36 51} 은 두 개의 개별 배열로 간주되며 동일한 재귀 논리가 여기에 적용되며 전체 배열이 정렬될 때까지 계속 이 작업을 수행합니다.

더 읽어보기: 데이터 구조의 힙 정렬

어떻게 작동합니까?

다음은 빠른 정렬 알고리즘에서 따라야 하는 단계입니다.

1. 피벗을 마지막 요소로 선택하고 처음으로 배열을 분할(또는 분할)하기 시작합니다.
2. 이 분할 알고리즘에서 배열은 피벗보다 작은 모든 요소가 피벗의 왼쪽에 있고 피벗보다 큰 모든 요소가 오른쪽에 있도록 2개의 하위 배열로 나뉩니다.
3. 그리고 피벗 요소는 최종 정렬 위치에 있습니다.
4. 왼쪽 및 오른쪽 부분배열의 요소는 정렬할 필요가 없습니다.
5. 그런 다음 재귀적으로 왼쪽 및 오른쪽 하위 배열을 선택하고 하위 배열에서 피벗을 선택하여 각각에 대해 분할을 수행하고 동일한 단계를 반복합니다.

아래에는 예제 배열을 사용하여 C++ 코드에서 알고리즘이 작동하는 방식이 나와 있습니다.

무효 QuickSort(int a[], int low, int high)

{

if(높음<낮음)

반품;

int p= 파티션(a,낮음,높음);

QuickSort(a,low,p-1);

QuickSort(a,p+1,high);

}

int 파티션(int a[], int low, int high)

{

int 피벗=a[높음];

정수 i = 낮음;

for(int j=낮음; j<높음; j++)

{

if(a[j]<=피벗)

{

스왑(&a[j],&a[i]);

나는 ++;

}

}

스왑(&a[i],&a[높음]);

반환 나;

}

정수 메인()

{

정수 arr[]={6,1,5,2,4,3};

퀵정렬(arr,0,5);

cout<<"정렬된 배열은 ";

for(int i=0; i<6; i++)

cout<<arr[i]<<" ";

반환 0;

}

다음은 주어진 배열을 정렬하는 빠른 정렬을 그림으로 나타낸 것입니다.

초기 입력 배열이 다음과 같다고 가정합니다.

따라서 첫 번째 분할 후 피벗 요소는 정렬된 배열의 올바른 위치에 있으며 모든 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 갑니다.

이제 QuickSort() 는 하위 배열 {1,2} 및 {6,4,5}에 대해 재귀적으로 호출되고 배열이 정렬될 때까지 계속됩니다.

반드시 읽어야 할 것: 알아야 할 AI 알고리즘의 유형

복잡성 분석

Ω 최상의 시간 복잡도: Ω Θ 평균 시간 복잡도: Θ O(n 최악의 시간 복잡도: O(n 분할이 거의 동일한 하위 배열로 이어지는 경우 실행 시간이 가장 좋으며 시간 복잡도는 O(n*log n)입니다.

최악의 경우는 요소가 이미 정렬되어 있고 피벗이 마지막 요소로 선택되는 경우가 있는 배열에서 발생합니다. 여기에서 분할은 불균형 하위 배열을 제공합니다. 여기서 모든 요소는 이미 피벗보다 작아서 왼쪽에 있고 오른쪽에는 요소가 없습니다.

O(n*log n) O(n*log n)

결론

Quicksort는 비교 기반 알고리즘이며 안정적 이지 않습니다 . 수행할 수 있는 작은 최적화는 먼저 더 작은 하위 배열에 대해 재귀적 QuickSort() 함수를 호출한 다음 더 큰 하위 배열에 대해 호출하는 것입니다.

전반적으로 빠른 정렬은 배열이 작은 경우 병합 정렬보다 더 나은 성능을 제공할 수 있는 고효율 정렬 기술입니다.

더 배우고 싶다면 upGrad & IIIT-B의 기계 학습 및 AI 프로그램 PG 디플로마를 확인하십시오.