[자료구조]퀵 정렬 구현

퀵 정렬도 병합 정렬을 기반으로 구현한다.

 

마찬가지로 left와 right가 있다.

left는 정렬대상의 가장 왼쪽

right는 정렬대상의 가장 오른쪽

 

pivot이라는 변수도 사용한다.

pivot 중심점, 기준이라 볼 수 있다. 가장 왼쪽에 위치한 변수를 피버로 둔다. 여기말고 다른 위치를 피벗으로 해도 상관없다.

 

pivot을 이용한 low와 high개념을 사용하자.

low는 pivot을 제외한 가장 왼쪽 

high는 피벗을 제외한 가장 오른쪽

결과적으로는 right와 high는 같은 위치에 있다. 하지만 가장 오른쪽을 피벗으로 두면 left와 low가 같은 위치에 있게된다.

 

low의 오른쪽 방향 이동은 피벗보다 큰 값을 만날 때까지 이동한다는 의미.

high의 왼쪽 방향 이동은 피벗보다 작은 값을 만날 때까지 이동.

 

이렇게 이동되어 위치한 두 값들을 바꾼다.

다시 low와 high는 각자의 방향으로 이동한다.

그렇게 둘 다 만나게되면 또 바꾼다. 결국 low와 high가 교차되는 상황이 발생한다.

이럴 때는 바꾸지 않고 피벗과 high가 가리키는 값을 바꾼다.

 

그렇게 되면 피벗 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값들이 위치해 있다.

다시 왼쪽과 오른쪽으로 나누어 각각 피벗을 설정한 후 low와 high를 이동시킨다.

 

그럼 이 과정은 언제 끝이 날까?

left > right인 상황, left와 right가 교차되는 상황이다.

 

 

//
//  QuickSort.c
//  Data-Structure
//
//  Created by 111 on 2021/02/09.
//

#include<stdio.h>

void Swap(int *arr,int idx1,int idx2){
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

int Partition(int *arr,int left,int right){
    int pivot = arr[left];
    int low = left+1;
    int high = right;
    
    while(low <= high){
        while(pivot > arr[low]){
            low++;
        }
        while(pivot < arr[high]){
            high--;
        }
        
        if(low<= high){
            Swap(arr, low, high);
        }
        
    }
    Swap(arr, left, high);  //left는 pivot의 위치이다.
    return high;
}

void QuickSort(int *arr,int left,int right){
    if(left <= right){
        int pivot = Partition(arr, left, right);
        QuickSort(arr, left, pivot-1);
        QuickSort(arr, pivot, right);
    }
}


int main(){
    int arr[7] = {3,2,4,1,7,6,5};
    //int arr[3] = {3,3,3};
    
    int len = sizeof(arr)/sizeof(int);
    int i;
    
    QuickSort(arr, sizeof(arr), sizeof(int) - 1);
    
    for(i=0;i<len;i++)
        printf("%d ",arr[i]);
    
}