퀵소트 c언어로 구현하기

오늘은 퀵소트에 대해서 공부해보았다.

구현 소스는 맨 아래에 두었다.

소스를 바로 보고 싶으신 분들은 맨 아래로 내려서 보길 바란다.

 

퀵소트는 배열의 맨 끝 요소를 pivot으로 삼고,  pivot보다 작은 수는 왼쪽에, pivot보다 큰 수는 오른쪽에 둔다.

pivot을 기준으로 pivot보다 작은구간과 큰 구간으로 다시 분할하여 pivot을 다시 설정하고, 이걸 반복하다 보면 정렬이된다

자세한 설명은 다른 블로그나 책에 잘 설명되어 있으니, 찾아보길 바란다.

구현은 재귀를 이용해서 하면 되는데 아주 간단하다.

아래에 소스코드를 적어두겠다.

 

#include<stdio.h>
#pragma warning(disable:4996)//이건 비쥬얼 스튜디오에서 scanf_s가 아니라 scanf를 쓰기 위해서 사용하는 명령어이다.

int Partition(int arr[], int start, int end);
void QuickSort(int arr[], int start, int end);

int main(){
	int arr[15];
	int n,i;
    scanf("%d", &n);//몇 개의 숫자를 배열에 받을지에 대한 입력이다.
    
    for(i = 0; i < n; i++){
    	scanf("%d", &arr[i]);
    }
    QuickSort(arr,0,n-1);
    for(int i = 0; i < n; i++)
    	printf("%d ", arr[i]);
}

void QuickSort(int arr[], int start, int end){
	if(start<end){
    	int idx;
        idx = Partition(arr,start,end);
        QuickSort(arr,start,idx-1);//idx보다 작은 부분으로 분할
        QuickSort(arr,idx+1,end);//idx값보다 큰 부분으로 분할
    }
}

int Partition(int arr[], int start, int end){
	int idx, i, pivot, tmp;
    pivot = arr[end];
    idx = start;
    
    for(i = start; i < end; i++){
    	if(arr[i] <= pivot){
        	tmp = arr[i];
            arr[i]=arr[idx];
            arr[idx++] = tmp;
        }
    }//pivot보다 크거나 같으면 i만 증가한다.
    //이렇게 i와 idx가 달라지고, i와 idx가 교환되면 i는 pivot보다 작은부분, idx는 큰 부분으로 간다.
    
    tmp = arr[end];
    arr[end]=arr[idx];
    arr[idx]=tmp;
    return idx;//idx의 최종 위치가 결정되었다. 이후로 변하지 않는다.
}