Quicksort is an efficient sorting algorithm, developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is a comparison-based algorithm, which means it measures the differences between elements that are to be sorted. It operates by utilising a divide and conquer approach, which divides the elements into two subgroups, which are then sorted recursively.
Quicksort uses a combination of selection sorting and partitioning to sort an array. In selection sorting, the algorithm looks for the smallest element in the array and swaps it with the first element in the array. This swapping ensures that the smallest element is always in the beginning of the array. The partitioning stage then moves the current element’s value to a place between elements with lesser and greater than values than it. This is done by first picking an element of the array, known as the “pivot”. All elements that are smaller than the pivot are put before the pivot, and all elements larger than the pivot are put after it. This process is repeated with the two freshly created subgroups until the array is sorted.
The time complexity of quicksort depends on the pivot chosen, but in most cases, the time complexity of quicksort is O(n log n). This makes quicksort a preferred sorting algorithm, for its relatively fast speed. It is also preferred because of its low memory requirement.
Quicksort is widely used in many areas of computer science, such as operating systems, databases, and graphics. It is also often used as part of the standard library in many programming languages such as C, Java, and Python.
