Sort Quickly With the Quicksort Algorithm
Algorithms 101
While studying computer science, the first and most important thing that I learned where algorithms. An algorithm is a set of instructions designed to perform a specific task. This can be a simple process or a complex operation.
What Is Sorting and Why Is It Important?
Sorting is the process of ordering a list of elements from an array in some kind of order. It can be done in ascending and descending order.
Sorting makes it possible to search the data elements in a collection quickly, for example, the binary search technique that we use every day while trying to find a contact number on our phones.
How Many Types of Sorting Techniques Are There?
There are two types of sorting techniques: integer sorts and comparison sorts. Comparison sorts compare elements at each step of the algorithm to determine if one element should be to the left or right of another element.
One of my favorite sorting algorithms is the quicksort algorithm.
How Does the Quicksort Algorithm Work and What Are the Steps?
Quicksort uses divide and conquer to sort an array. Divide and conquer is a technique used by breaking an array of elements into subarrays, solving the subarrays, and then combining the array back together to sort the whole array.
Here are the steps that quicksort uses:
Divide
- Pick a pivot element, A[y].
- Partition the array into two subarrays: A[x, …, y-1] such that all elements are less than A[y], and A[y+1,…, z] such that all elements are greater than or equal to A[y].
Conquer
Sort the subarrays A[x,…, y-1] and A[y+1,…, z] recursively with quicksort.
Combine
The subarrays are already sorted, nothing to do after this.
Time Complexity of Quicksort Algorithms
Best case
The best case happens when the partition process always picks the middle element as pivot. The algorithm, in this case, uses only O(n log n) time.
Average case
For the average case, we need to consider all possible permutations of the array and calculate the time taken by every permutation which is a lot for a large list of elements.
To sort an array of n elements, quicksort takes O(n log n) time in expectation, averaged over all n! permutations of n elements with equal probability.
Worst case
The worst-case happens when the partition process always picks the greatest or smallest element as pivot. The worst case would occur when the array is already sorted in ascending or descending order, in that case, quicksort takes O(n²) time.
Here you can find quicksort implemented in Java with a sample:
