Quicksort High level illustration of Quicksort High level illustration of Quicksort Select pivot 25 High level illustration of Quicksort 25 age 25 25 age 25 Partition High level illustration of Quicksort 25 age 25 25 age 25 Quicksort left High level illustration of Quicksort 25 age 25 25 age 25 Quicksort left Quicksort right The Algorithm Quicksort A p r 1 if p r 3 q Partition A p r 4 Quicksort A p q 1 5 Quicksort A q 1 r Partition A p r 1 x A r 2 i p 1 3 for j p to r 1 do 4 If A j x then 5 6 7 8 9 temp A i 1 10 A i 1 A r 11 A r temp 12 return i 1 i i 1 temp A i A i A j A j temp How Is partition Implemented Ideally we can rearrange the list so that half elements go to left and half elements go to right of k In practice 1 Choose A r as the pivot element to go to the correct place in the list 2 If p i q 1 then A i pivot 3 If q 1 j r then A j pivot 4 Scan from left to right and do O 1 work at each position Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 8 7 1 3 5 6 4 i j x 4 Example p r 2 1 7 8 3 5 6 4 i j x 4 Example p r 2 1 7 8 3 5 6 4 i j x 4 Example p r 2 1 7 8 3 5 6 4 i j x 4 Example p r 2 1 3 8 7 5 6 4 i j x 4 Example p r 2 1 3 8 7 5 6 4 i j x 4 Example p r 2 1 3 8 7 5 6 4 i j x 4 Example p r 2 1 3 8 7 5 6 4 i j x 4 Example p r 2 1 3 8 7 5 6 4 i j x 4 Example p r 2 1 3 8 7 5 6 4 i j x 4 Example p r 2 1 3 4 7 5 6 8 i j x 4 x 4 Example 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 4 7 5 6 8 Example 2 8 7 1 3 5 6 4 x 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 1 2 3 4 7 5 6 8 Example 2 8 7 1 3 5 6 4 x 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 1 2 3 4 7 5 6 8 Summary We have presented the quicksort algorithm We have illustrated the steps in partition We will study the time complexity of quicksort next Time Complexity of Partition The best case worst case time complexity of partition is n where n is the number of elements in the array to be partitioned We are scanning the array from left to right spending O 1 time at each position Time Complexity of Quick Sort The complexity depends on the partition Best case partitioning divide into 2 equal sublists nT 2 nT 1 2 n 1 nif otherwise T n nlgn Worst case partitioning if the list is already sorted The right sublist 0 and left sublist n 1 elements nT nT 1 n nT 2 1 n n k k n k 1 1 nn 2 2 n n k 1 Average Time Complexity of Quicksort The pivot A r partitions the array A 1 n into a left part of q 1 elements and a right part of n q elements We call this a q 1 to n q split The number q can take any of the integers between 1 and n Since all permutations are equally likely the probability for q to be equal to k is 1 n for k 1 2 n Average Time Complexity of Quicksort T n n 1 2 T 0 T 1 T n 1 n nT n n n 1 2 T 0 T 1 T n 1 n 1 T n 1 n 1 n 2 T 0 T 1 T n 2 nT n n 1 T n 1 2n 2T n 1 nT n 2n n 1 T n 1 T n n 1 2 n 1 T n 1 n T n n 1 2 1 1 2 1 3 1 n 1 n log n Stable Sorting and Non Stable Sorting A sorting algorithm is stable if A i A j implies the relative order of the two elements will not change during the sorting process Insertion sort is stable MergeSort is stable Quicksort is NOT stable Tony Hoare and Quicksort Invented by Tony Hoare in 1959 Divide and Conquer algorithm Selecting the pivot Using the pivot to partition Wiki page Tony Hoare
View Full Document
Unlocking...