kiirsorteerimine

Kiirsorteerimine, known in English as Quicksort, is an efficient comparison-based sorting algorithm. Developed by Tony Hoare in 1959, it was published in 1961. Quicksort is widely used for its good average-case performance, typically having a time complexity of O(n log n). Its worst-case time complexity is O(n^2), but this is relatively rare in practice with good pivot selection strategies.

The algorithm operates on the principle of divide and conquer. It partitions an array into two sub-arrays based on a chosen element called the pivot. Elements smaller than the pivot are placed in the left sub-array, and elements larger than the pivot are placed in the right sub-array. This partitioning step is performed recursively on the sub-arrays until the entire array is sorted.

The choice of pivot significantly impacts the algorithm's performance. Common strategies include selecting the first element, the last element, a random element, or the median of three elements. If the pivot is consistently chosen poorly, leading to unbalanced partitions, the algorithm can degrade to O(n^2) complexity.

Quicksort is an in-place sorting algorithm, meaning it requires only a constant amount of additional memory space, typically O(log n) for the recursion stack in the average case. While not stable, meaning the relative order of equal elements may not be preserved, its speed and in-place nature make it a popular choice for sorting large datasets.