[알고리즘] 퀵정렬이란 ?

퀵정렬이란 ?

Divide-and-Conquer paradigm을 사용     - 풀기어려운 큰문제를 풀기쉬운 여러개의 작은문제로 바꾸어 해결 Partitioning 이용     - Pivot을 이용하여 왼쪽에는 Pivot보다 작은것들 오른쪽에는 Pivot보다 큰거를 정렬     - 1번하고 끝나는것이 아니라 정렬이 완료될때까지 재귀적으로 호출     - Pivot을 어떤방법으로 잡는지가 성능에 큰 영향을 끼친다.       시간복잡도  - 최악의경우 : O(n²)  - 평균의경우 : O(nlogn)

 

수도코드

QuickSort(A[], p, r) {
    if(p<r) then{
        q = partition(A, p, r); 
        QuickSort(A, p, q-1);    
        QuickSort(A, q+1, r);    
    }
}

partition(A[], p, r) {
    배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
    A[r]이 자리한 위치를 return
}

 

 

소스

1. 처음 퀵소트는 1차적으로 중간지점을 선택

2. 처음 정렬이 끝나면 PIVOT의 위치를 리턴 

3. PIVOT의 위치를 기점으로 좌, 우로 재귀적호출

   - PIVOT의 위치를 기점으로 왼쪽에는 PIVOT보다 작은값, 오른쪽에는 PIVOT보다 큰값들이 정렬 되어있기때문

 

실행예시

1. 피봇을 설정(2)

2. 왼쪽부터 차례대로 피봇보다 큰수가 있는지 탐색 ( 2보다 큰 9를 찾음)

3. 오른쪽부터 차례대로 피봇보다 작거나 같은값이 있는지 탐색 (2와 같은 2를 찾음)

4. 찾았다면 위치를 바꾸어준다. ( 2와 9 교환)

5. left가 right보다 작은동안 2~4번작업을 반복

6. 정렬이 완료될때까지 1~5 반복