- our high-level description of quick-sort describes partitioning the elements into three sets leand ghaving keys less thanequal toor greater than the pivotrespectively howeverour in-place quick-sort implementation of code fragment does not gather all elements equal to the pivot into set an alternative strategy for an in-placethreeway partition is as follows loop through the elements from left to right maintaining indices ijand and the invariant that all elements of slice [ :iare strictly less than the pivotall elements of slice [ :jare equal to the pivotand all elements of slice [ :kare strictly greater than the pivotelements of [ :nare yet unclassified in each pass of the loopclassify one additional elementperforming constant number of swaps as needed implement an in-place quick-sort using this strategy - suppose we are given an -element sequence such that each element in represents different vote for presidentwhere each vote is given as an integer representing particular candidateyet the integers may be arbitrarily large (even if the number of candidates is notdesign an ( log )time algorithm to see who wins the election representsassuming the candidate with the most votes wins - consider the voting problem from exercise - but now suppose that we know the number of candidates runningeven though the integer ids for those candidates can be arbitrarily large describe an ( log )time algorithm for determining who wins the election - consider the voting problem from exercise - but now suppose the integers to are used to identify candidates design an ( )-time algorithm to determine who wins the election - show that any comparison-based sorting algorithm can be made to be stable without affecting its asymptotic running time - suppose we are given two sequences and of elementspossibly containing duplicateson which total order relation is defined describe an efficient algorithm for determining if and contain the same set of elements what is the running time of this methodc- given an array of integers in the range [ ]describe simple method for sorting in (ntime - let sk be different sequences whose elements have integer keys in the range [ ]for some parameter > describe an algorithm that produces respective sorted sequences in ( ntimewere denotes the sum of the sizes of those sequences - given sequence of elementson which total order relation is defineddescribe an efficient method for determining whether there are two equal elements in what is the running time of your method