c언어 퀵정렬 함수

퀵정렬(quick sort)의 시간복잡도는 nlogn으로 동작 원리는 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.

c언어로 구현하면 다음과 같다.

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 <= right)

low++;

while(pivot <= arr[high] && high >= left+1)

high--;

if(low <=high)

swap(arr,low,high);

}

swap(arr,left,high);

return high;

}

void QuickSort(int arr[], int left, int right){

if(left <=left){

int pivot = partition(arr,left,right);

QuickSort(arr,left,pivot-1);

QuictSort(arr,pivot+1,right);

}

}