Quick Sort

June 25, 2014 · algorithms

Quicksort, also known as partition-exchange sort, uses these steps.

Choose any element of the array to be the pivot.
Divide all other elements (except the pivot) into two partitions.
- All elements less than the pivot must be in the first partition.
- All elements greater than the pivot must be in the second partition.
Use recursion to sort both partitions.
Join the first sorted partition, the pivot, and the second sorted partition.

void swap(int *a, int *b) { 
  int t=*a; 
  *a=*b; 
  *b=t; 
}

void sort(int arr[], int beg, int end) {
  if (end > beg + 1) {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r) {
      if (arr[l] <= piv) 
        l++;
      else 
        swap(&arr[l], &arr[--r]);
    }
    // swapping elements within the array 
    // to avoid the memory allocation of more arrays.
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

function sort(array, less) {
 
  function swap(i, j) { 
    var t=array[i]; 
    array[i]=array[j]; 
    array[j]=t 
  }
 
  function quicksort(left, right) {
    if (left < right) {
      var pivot = array[(left + right) >> 1];
      var left_new = left, right_new = right;
      do {
        while (less(array[left_new], pivot)
          left_new++;
        while (less(pivot, array[right_new])
          right_new--;
        if (left_new  <= right_new)
          swap(left_new++, right_new--);
      } while (left_new  <= right_new);
      quicksort(left, right_new);
      quicksort(left_new, right);
    }
  }
 
  quicksort(0, array.length-1);
  return array;
}

Array.prototype.quick_sort = function ()
{
    if (this.length <= 1)
      return this;
 
    var pivot = this[Math.round(this.length / 2)];
 
    return this.filter(function (x) { return x <  pivot }).quick_sort().concat(
           this.filter(function (x) { return x == pivot })).concat(
           this.filter(function (x) { return x >  pivot }).quick_sort());
}

ruby

class Array
  def quick_sort
    return self if length <= 1
    pivot = sample
    group = group_by{ |x| x <=> pivot }
    group.default = []
    group[-1].quick_sort + group[0] + group[1].quick_sort
  end
end

ruby

class Array
  def quick_sort
    h, *t = self
    h ? t.partition { |e| e < h }.inject { |l, r| l.quick_sort + [h] + r.quick_sort } : []
  end
end