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.

Quick sort algorithm name

The QuickSort algorithm is well-known and generally referred to by that name. However, it's worth noting that different variations or implementations of the algorithm might be named differently, especially in specific contexts. Here are a few other names that might be associated with similar sorting algorithms:

1. QuickSort. This is the most common name for the algorithm, but it's worth noting that it's sometimes spelled as "Quick Sort" or "Quick-Sort."
2. Qsort. This is a common abbreviation for QuickSort.
3. Hoare's Partition Sort. QuickSort was developed by Tony Hoare, so it's sometimes called Hoare's sort in honor of its creator.
4. Partition-Exchange Sort. QuickSort is often categorized as a partition-exchange sort because it involves partitioning the array and exchanging elements.
5. Partition Sort. Similar to Pivot Sort, this name emphasizes the partitioning step in the algorithm.
6. Pivot Sort. QuickSort uses a pivot element for partitioning, so you might encounter the term "Pivot Sort."
7. Quick Exchange Sort. This name emphasizes the quick exchange of elements that occurs during the algorithm.
8. Quick Partition Sort. This name emphasizes the quick partitioning of the array that occurs during the algorithm.
9. Sorting by Partitioning This name emphasizes the partitioning step in the algorithm.

Implementations

JavaScript

 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 / Golang

  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

  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