Code two versions of Quicksort algorithms, one using the Lomuto method and one using the Hoare method. Clearly document your code so that it is clear how and why your algorithms are correct. For each of the two algorithms the output must be the following three items: the total numberof comparisons, the total number of swaps, and the total running time. Demonstrate your two Quicksort algorithms on the input array A= [2, 8, 7, 1, 3, 5, 6, 4].
In Python:
Code two versions of Quicksort
QuickSort is an algorithm that follows Divide and Conquer approach. It choose an element to be pivot and partitions the array around the chosen pivot.
Lumato takes the last element as a pivot, places the pivot element at its exact position in sorted array, and puts all smaller one to left of the pivot and all greater elements to the right
Hoare utilizes two indices that begin at the ends of the array being partitioned, then move approaching each other until they detect an inversion: a pair of elements, one smaller and one greater than the pivot, in the wrong order relative to each other. The inverted elements are then swapped. When the indices match, the algorithm ends and returns the terminal index.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
