QuickSort Algorithm Assignment Help
Quicksort even known as partition-exchange sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.
Quicksort will be well-known due to the fact it isn't difficult to implement, works well for a number of different types of input data, and is substantially faster compared to every other sorting method within typical applications.
The Pseudo Code
Quickest recognized sorting algorithm in practice:
- Average case: O(N log N)
- Worst case: O(N2)
n But, the actual worst case seldom happens. An additional divide-and-conquer recursive algorithm, such as merge sort
Analysis:
- Assumptions
- n A random pivot
- n No cutoff for small arrays
- Running time:
- n pivot selection: constant time, i.e. O(1)
- n partitioning: linear time, i.e. O(N)
- n running time of the two recursive calls
- T(N) = T(i) + T( N - i -1 ) + cN where c is a constant
- n i : number of elements in S1
- n i : number of elements in S1
Worst-Case Analysis:
- What would be the worst case?
- n The pivot may be the smallest element, constantly
- n The pivot may be the smallest element, constantly
- n Partition is always unbalanced
Best-case Analysis:
- What would be the best case?
- n Partition is perfectly balanced
- n Pivot is always in the middle
Average-Case Analysis:
- Assume : Each of the sizes with regard to S1 is similarly most likely
- This assumption is valid for our pivoting (median-of-three) strategy
- On average, the running time is O(N log N)
Quick sort for small Arrays:
- For very small arrays (N 20), quick sort doesn't perform as well as insertion sort
- A beneficial cutoff range is usually N=10