자료구조 알고리즘 퀵정렬(Quick Sort, 퀵정렬) C언어 구현

안녕하세요, 츄르 사려고 코딩하는 집사 코집사입니다.

고급 알고리즘 중에서 병합정렬(Merge Sort)에 이어 실무에서 가장 많이 사용한다고 알려진

퀵정렬(Quick Sort)입니다.

Quick Sort는 평균적으로 좋은 성능을 가졌습니다.

하나의 pivot을 정하여 pivot을 기준으로 pivot보다 작으면 왼쪽, 크면 오른쪽으로 partition 알고리즘을 사용하여 배치를 합니다.

<C언어 소스 코드>

#include<stdio.h>

int A[10000];

int swap(int *a, int *b);

int QuickSort(int A[], int p, int r);

int Partition(int A[], int p, int r);

int main()

{

int number;

printf("배열의 크기를 입력 : ");

scanf("%d",&number);

for(int i = 1;i<=number;i++)

{

printf("%d번째 배열값 입력",i);

scanf("%d",&A[i]);

}

QuickSort(A,1,number);

for(int j = 1;j<=number;j++)

{

printf("%d",A[j]);

}

}

int QuickSort(int A[], int p, int r)

{

if(p<r)

{

int q = Partition(A,p,r);

QuickSort(A,p,q-1);

QuickSort(A,q+1,r);

}

}

int Partition(int A[], int p, int r)

{

int pivot;

pivot = A[r];

int i = p-1;

for(int j = p;j<r;j++)

{

if(A[j]<=pivot)

{

i++;

swap(&A[i],&A[j]);

}

}

swap(&A[i+1],&A[r]);

return i+1;

}

int swap(int *a, int *b)

{

int temp;

temp = *a;

*a = *b;

*b = temp;

}