Introduction
Sorting is the process of arranging data in ascending or descending order based on a linear relationship between the data pieces.
Names, numbers, and records can all be sorted. Sorting saves time; for example, looking for a friend’s phone number from a telephone dictionary is rather simple because the names in the phone book have been sorted into alphabetical order.
Theory
Here in Quick sort, a pivot element is found, and it is set in position by moving all the items less than it to the left and all the elements bigger than it to the right which results in sorted elements.
It’s a much more efficient and faster sorting method. The divide and conquer strategy is used in this method. Breaking down algorithms into subproblems, solving the subproblems, and then merging the results to solve the main problem is known as divide and conquer.
First, choose a pivot element in Divide. After that, divide or rearrange the array into two sub-arrays, with each element in the left sub-array being less than or equal to the pivot element, and each element in the right sub-array being greater.
Conquer: Sort two subarrays recursively with Quicksort.
Combine: Combine the previously sorted arrays.
Quicksort selects an element as the pivot and splits the specified array around that pivot element. In rapid sort, a huge array is split into two arrays, one containing value less than the specified value (Pivot) and the other containing values larger than the pivot.
Following that, the left and right sub-arrays are partitioned in the same way. It’ll keep going until only one element is left in the sub-array.
Choosing the pivot
Picking a good pivot is important for the quick implementation of quicksort. However, it’s typical to work out a good pivot. a number of ways in which a pivot of selected are as follows –
o Pivot will be random, i.e., choose the random pivot from the given array.
o Select median as the pivot component.
Diagrams
Pseudo code
- Step 1: Pick a pivotal element from the list (using a defined algorithm or at random). Consider pivot as the part that will break down a larger problem into smaller ones.
- Step 2: Divide the list into two parts. The elements in one list will have lower values than the pivot, whereas the elements in the other list will have higher values than the pivot.
At this stage, notice that the pivot is in the proper place, and the left elements are smaller than the pivot. The correct elements are those that are bigger than the pivot.
- Step 3: Apply the algorithm to all divisions in a recursive manner (left and right subparts)
Python code:
Output:
Time complexity
- Worst case time complexity of Quick Sort is Θ(N^2)
Assume we choose a pivot element to produce the most imbalanced partitions possible.
Consider an N-dimensional input array. The initial partition call executes the partition step on the input array N times.
Each division step is called in a recursive manner from the one before it. Given this, we can add up the complexity of each division call to find the Quicksort algorithm’s total complexity.
leading to
Similarly we get the same result w.r.t time
- Average case time complexity of Quick Sort is Θ (N log N)
In this case, when the worst-case and 3-to-1 splits alternate, we get average case time complexity.
- Quicksort best-case complexity is Θ (N log N)
The ideal case scenario for Quicksort is when the partitions are as evenly balanced as possible: their sizes are either equal or within one of each other. If the subarray has an odd number of items, the pivot is in the middle after dividing, and each partition has (n-1)/2 elements, the first case happens. If the subarray contains an even number of elements, n, and one partition has n/2 items and the other has n/2-1, the later scenario happens. In either instance, each partition has a maximum of n/2 elements.
Space complexity
Quicksort has a space complexity of Θ(N)
Applications
- commercial computing
- Numeric computation
- Information Search
