[Algorithm] Quick Sort

Quick Sort는 보편적으로 가장 빠른 정렬 알고리즘으로 pivot값을 정할때 전체 값중 한쪽에 편중된 pivot이 정해지면 효율이 최악이 될 수도 있어, 경우에 따라서는 Counting Sort가 빠른 경우도 있다.

또한 정렬할 배열이 100개 이하라면 선택 정렬을 사용하는게 속도에 유리할 수가 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

void quicksort(int arr[], int left, int right){     int i = left, j = right;     int tmp;     int pivot = arr[(left + right) / 2];     while (i <= j){         while (arr[i] < pivot)             i++;         while (arr[j] > pivot)             j--;         if (i <= j){             tmp = arr[i];             arr[i] = arr[j];             arr[j] = tmp;             i++;             j--;         }     }     if (left < j)         quicksort(arr, left, j);     if (i < right)         quicksort(arr, i, right); } Colored by Color Scripter

cs