Quick Sort Visualization

What is Quick Sort Algorithm?

Quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than merge sort and about two or three times faster than heapsort.

Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.

Mathematical analysis of quicksort shows that, on average, the algorithm takes {\displaystyle O(n\log {n})}O(n\log {n}) comparisons to sort n items. In the worst case, it makes {\displaystyle O(n^{2})}O(n^{2}) comparisons.

JavaScript implementation

 function quickSort(arr, left, right) {
  var i = left;
  var j = right;
  var tmp;
  var pivotidx = (left + right) / 2;
  var pivot = parseInt(arr[pivotidx.toFixed()]);
  /* partition */
  while (i <= j)
  {
    while (parseInt(arr[i]) < pivot)
      i++;
    while (parseInt(arr[j]) > pivot)
      j--;
    if (i <= j)
    {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  }

  /* recursion */
  if (left < j)
    this.quickSort(arr, left, j);
  if (i < right)
    this.quickSort(arr, i, right);

  return arr;
} 

Go implementation

  func quicksort(arr []int) []int {
    if len(arr) <= 1 {
      return arr
    } else {
      pivot := arr[0]
      smaller := make([]int, 0)
      greater := make([]int, 0)
      for _, num := range arr[1:] {
        if num <= pivot {
          smaller = append(smaller, num)
        } else {
          greater = append(greater, num)
        }
      }
      smaller = quicksort(smaller)
      greater = quicksort(greater)
      return append(append(smaller, pivot), greater...)
    }
  }

Python implementation

  def partition(array, low, high):
    pivot = array[high]

    i = low - 1

    for j in range(low, high):
      if array[j] <= pivot:
        i = i + 1
        (array[i], array[j]) = (array[j], array[i])

    (array[i + 1], array[high]) = (array[high], array[i + 1])
  
    return i + 1

  def quickSort(array, low, high):
    if low < high:

      pi = partition(array, low, high)

      quickSort(array, low, pi - 1)

      quickSort(array, pi + 1, high)


  data = [8, 7, 2, 1, 0, 9, 6]
  print("Unsorted Array")
  print(data)

  size = len(data)

  quickSort(data, 0, size - 1)

  print('Sorted Array in Ascending Order:')
  print(data)

Source: Wikipedia