QuickSort And Linear Time Sort

Problem 6) (10 points) QuickSort is not a stable sorting algorithm which means that repeated elements dont have to appear in the same order after the sort is completed. For example, if there are 3 values of x and you choose the first occurrence of x as a pivot then the other two x values end up to the left of the pivot. Modify quicksort in order to make it a stable sorting algorithm. Please note that the algorithm needs to work exactly the same but you are free to add pre-processing or post-processing as long as it takes no more than O(n).

Problem 7) (5 points) Show the execution of Radix sort on the following. It is sufficient to show the sorted list at each stage of the algorithm:

QUIZ, JACK, JUMP, JAMB, QURY, JURY, FLAK, NECK, CHIP, ZERO

Problem 8) (10 points) Show the execution of KMPs algorithm on the following Text and Pattern. Show the prefix function and then show each iteration of the algorithms loop (copy paste might help speed things along):

T = CGCCTAGCCGCTATACGAGC

P = CGAGCTCC