Quick Sort

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

  1. Choose any element of the array to be the pivot.
  2. 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.
  3. Use recursion to sort both partitions.
  4. Join the first sorted partition, the pivot, and the second sorted partition.
C Quick SortSource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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);
  }
}
JS Quick SortSource
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
27
28

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;
}
JS (Functional) Quick SortSource
1
2
3
4
5
6
7
8
9
10
11

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 Quick SortSource
1
2
3
4
5
6
7
8
9

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 (Functional) Quick SortSource
1
2
3
4
5
6

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
algorithms

Comments