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:
- 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."
- Qsort. This is a common abbreviation for QuickSort.
- Hoare's Partition Sort. QuickSort was developed by Tony Hoare, so it's sometimes called Hoare's sort in honor of its creator.
- Partition-Exchange Sort. QuickSort is often categorized as a partition-exchange sort because it involves partitioning the array and exchanging elements.
- Partition Sort. Similar to Pivot Sort, this name emphasizes the partitioning step in the algorithm.
- Pivot Sort. QuickSort uses a pivot element for partitioning, so you might encounter the term "Pivot Sort."
- Quick Exchange Sort. This name emphasizes the quick exchange of elements that occurs during the algorithm.
- Quick Partition Sort. This name emphasizes the quick partitioning of the array that occurs during the algorithm.
- 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