퀵소트 알고리즘 구현

퀵정렬에 대한 자세한 설명은

Algorithm #1. Sort algorithm. - 1.4 Quick Sort algorithm.

축값은 가장 오른쪽의 값을 이용합니다.

#include <stdio.h> #include <string.h> char str[256]; void print(char *a, int n) { int i, off; for(off=a-str; off>0; off--) { printf(" "); } for(i=0; i<n; i++) { printf("%c ",a[i]); } printf("\n"); } void quick(char *a,int n) { char mid,tmp; //mid는 축값(기준값) int i,j; if(n > 1) { mid=a[n-1]; i=-1; //앞부터 j=n-1; //뒤부터 탐색 while(1) //분할 { while(a[++i] < mid); //왼쪽부터 축값보다 큰 값을 찾음 while(a[--j] > mid); //오른쪽부터 축값보다 작은 값을 찾음 if(i >= j) //분할이 끝나면 종료 break; tmp=a[i]; //위에서 찾은 값을 바꿈 a[i]=a[j]; a[j]=tmp; } tmp=a[i]; //축값을 바꿈 a[i]=a[n-1]; a[n-1]=tmp; print(a,n); //정렬과정 출력 quick(a, i); //왼쪽구간 정렬 quick(a+i+1,n-i-1); //오른쪽구간 정렬 } } main() { strcpy(str,"Hellologicalworld"); print(str,strlen(str)); quick(str,strlen(str)); print(str,strlen(str)); }

정렬과정

H e l l o l o g i c a l w o r l d

H a c d o l o g i l e l w o r l l

H a c

H a

        l l e g i l o l w o r o l

        g e i l l

        e g

              l l

                    l l w o r o o

                        o o r w o

                            o w r

                              r w

H a c d e g i l l l l l o o o r w