Table of contentsClick link to navigate to the desired location
This content has been automatically translated from Ukrainian.
QuickSort is a sorting algorithm that uses the "divide and conquer" strategy. It quickly and efficiently sorts arrays by comparing elements and moving them to the correct positions.
When and by whom was QuickSort created?
QuickSort was developed by British engineer and computer scientist Tony Hoare in 1959. Tony Hoare became well-known in the field of computer science for his significant contributions, and QuickSort became one of his most famous inventions. Tony Hoare received the Turing Award in 1980 for his work in sorting and algorithm analysis.
How does QuickSort sorting work?
- A pivot element is chosen. This can be any element of the array, such as the first, last, or middle element.
- The elements of the array are arranged such that all elements less than the pivot are placed before it, and all greater elements are placed after it. The pivot element reaches its final position.
- QuickSort is recursively applied to the sub-array that is before the pivot (the smaller elements) and the sub-array that is after the pivot (the larger elements).
- Steps 1-3 are repeated for each sub-array until the entire array is sorted.
Since QuickSort applies the "divide and conquer" strategy, it demonstrates good performance. On average, its complexity is O(n log n), where n is the number of elements in the array. However, the worst-case scenario can have a complexity of O(n^2) when the pivot element is always chosen as the largest or smallest element of the array. To avoid the worst-case scenario, various strategies for choosing the pivot element can be used, such as random selection or the median of three elements.
Example of QuickSort algorithm (JavaScript).
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const less = [];
const greater = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
less.push(arr[i]);
} else if (arr[i] > pivot) {
greater.push(arr[i]);
}
}
return [...quickSort(less), pivot, ...quickSort(greater)];
}
// Example usage:
const array = [5, 3, 1, 6, 2, 4];
const sortedArray = quickSort(array);
console.log(sortedArray);
The function quickSort takes an array arr as an input parameter and returns a sorted array.
The QuickSort algorithm recursively divides the input array into smaller and larger sub-arrays relative to the chosen pivot element (pivot). Elements smaller than pivot are stored in less, and larger ones in greater. Then a recursive call to quickSort is made for the less and greater sub-arrays, and the results are combined with the pivot element pivot to form the final sorted array.
Result:
[1, 2, 3, 4, 5, 6]
Example of QuickSort algorithm (Ruby).
def quick_sort(arr)
return arr if arr.length <= 1
pivot = arr[arr.length / 2]
less = []
greater = []
arr.each do |element|
if element < pivot
less << element
elsif element > pivot
greater << element
end
end
return [*quick_sort(less), pivot, *quick_sort(greater)]
end
# Example usage:
array = [5, 3, 1, 6, 2, 4]
sorted_array = quick_sort(array)
puts sorted_array
Just like in the JavaScript example - the function quick_sort takes an array arr as an input parameter and returns a sorted array.
The QuickSort algorithm recursively divides the input array into smaller and larger sub-arrays relative to the chosen pivot element (pivot). Elements smaller than pivot are stored in the less array, and larger ones in the greater array. Then quick_sort is recursively called for the less and greater sub-arrays, and the results are combined with the pivot element pivot using the splat operator * to form the final sorted array.
Result:
[1, 2, 3, 4, 5, 6]
Is the QuickSort algorithm used in the standard methods of JavaScript or Ruby?
In the standard methods of the Ruby and JavaScript languages that are responsible for sorting, the exact QuickSort algorithm is usually not used. This can vary depending on the specific implementation of the language and its version, as well as the unique requirements and optimizations that are employed.
In Ruby, the algorithm used for sorting arrays by default combines QuickSort, InsertionSort, and HeapSort methods. This algorithm is called Timsort, which was developed for optimal sorting of various types of data.
In JavaScript, sorting arrays is typically done using the Array.prototype.sort() method. The implementation of this method can vary between different JavaScript implementations (for example, the V8 engine in Node.js or Chrome and SpiderMonkey in Firefox). In most cases, a fast and optimized algorithm that combines QuickSort with InsertionSort or MergeSort is used, depending on the implementation.
Therefore, while QuickSort may be used as one of the components or foundational algorithms in the array sorting methods of Ruby and JavaScript, QuickSort itself is not the only algorithm used in these languages for sorting by default. More complex algorithms, such as Timsort or its variations, which combine different sorting algorithms to ensure optimality and a wide range of use cases, are typically employed.
This post doesn't have any additions from the author yet.
