QuickSort ( 퀵정렬 )

#include <stdio.h>

int partition_quick_sort( int arr[] , start , end ){

int pivot = end ;            // 맨끝값을 피벗값으로 지정.

int right = end ;

int left = start ;

int temp = 0 ;

while ( left < right ){

while ( arr [ left ] < arr [ end ] && left < right ){        // 왼쪽에서부터 피벗값보다 큰값을 찾아낸다.

left++;

}

while ( arr[ right ] >= arr [ end ] && left < right ){     // 오른쪽에서부터 피벗값보다 작은 값을 찾아낸다.

right--;

}

temp = arr [ left ];                                               // 찾아낸 값들의 위치를 교환한다.

arr [ left ] = arr [ right ] ; 

arr [ right ] = temp ;

}                                                               

// while반복문이 종료되면 right의 값은 중간값이 들어갈 위치가 된다.

// right번 숫자를 기준으로 왼쪽에는 작은수 오른쪽에는 큰수가 위치한다.

temp = arr [ right ];

arr[ right ] = arr [ pivot ];

arr[ pivot ] = temp ;

return right ;

}

void quick_sort( int arr[] , int start , int end ){

int pivot = 0 ;

if ( start < end ) {                                                        // 배열이 2개 이상인경우 재귀함수.

pivot = partition_quick_sort( arr , start , end );

quick_sort ( arr , start , pivot -1 );            

quick_sort ( arr , pivot +1 , end );

}

}

int main( void ) { 

int i = 0 ;

int arr[] = { 15 , 26, 5 , 96 , 42 , 67 , 54 };

quick_sort( arr , 0 , 7 );

for ( i = 0 ; i < 8 ; i++) {

printf("%d " , arr[ i ] );

}

return 0 ;

}

=> 배열이 오름차순으로 정렬되어진다.

내림차순은 while 조건식을 반대로 주면 된다.