Quick Sort

참고 : http://en.wikipedia.org/wiki/Quicksort
 

 function quicksort(array, left, right)
     var pivot, leftIdx = left, rightIdx = right
     if right > left // only sort if there are >= 2 elements
         pivot = (left + right) / 2
         while leftIdx <= pivot and rightIdx >= pivot
             while array[leftIdx] < array[pivot] and leftIdx <= pivot
                 leftIdx = leftIdx + 1
             while array[rightIdx] > array[pivot] and rightIdx >= pivot
                 rightIdx = rightIdx - 1;
             swap array[leftIdx] with array[rightIdx]
             leftIdx = leftIdx + 1
             rightIdx = rightIdx - 1
             if leftIdx - 1 == pivot
                 pivot = rightIdx = rightIdx + 1
             else if rightIdx + 1 == pivot
                 pivot = leftIdx = leftIdx - 1
         quicksort(array, left, pivot - 1)
         quicksort(array, pivot + 1, right)

void quick_sort(int arr[], int l, int r)
{
	if (l < r) {
		int i=l, j=r, pivot=l+(r-l)/2;
		while (i < j) {
			while (i < pivot && arr[i] <= arr[pivot]) 
				++i;
			while (j > pivot && arr[j] >= arr[pivot])
				--j;
			swap_arr(arr, i, j);
			++i, --j;
			if (i-1 == pivot)
				pivot = j = j+1;
			else if (j+1 == pivot)
				pivot = i = i-1;
		}
		qsort_2(arr, l, pivot-1);
		qsort_2(arr, pivot+1, r);
	}
}

---

  // left is the index of the leftmost element of the array
  // right is the index of the rightmost element of the array (inclusive)
  //   number of elements in subarray: right-left+1
  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left 
     for i  from  left to right - 1 // left ≤ i < right 
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

 procedure quicksort(array, left, right)
     if right > left // subarray of 0 or 1 elements already sorted
         select a pivot index //(e.g. pivotIndex := left + (right - left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         // element at pivotNewIndex is now at its final position and never moved again
         //   and guarantees termination: recursive calls will sort smaller array
         // recursively sort elements on the left of pivotNewIndex
         quicksort(array, left, pivotNewIndex - 1)
         // recursively sort elements on the right of pivotNewIndex
         quicksort(array, pivotNewIndex + 1, right)

int partition(int arr[], int l, int r, int pivot)

{
	int pivot_val = arr[pivot];
	int sorted_index = l, i;
	swap_arr(arr, pivot, r);

	for (i=l; i < r; ++i) {
		if (arr[i] <= pivot_val) {
			swap_arr(arr, i, sorted_index);
			sorted_index++;
		}
	}
	swap_arr(arr, sorted_index, r);
	return sorted_index;
}

void quick_sort(int arr[], int l, int r)
{
	if (l < r) {
		int pivot = partition(arr, l, r, (l+r)/2);
		qsort_1(arr, l, pivot-1);
		qsort_1(arr, pivot+1, r);;
	}
}