QuickSort Example full Unsorted List 5 7 25 17 19 36 56 Quick Sort Quick Sort The idea is as follows 1 If the number of elements to be sorted is 0 or 1 then return 2 Pick any element v this is called the pivot 3 Partition the other elements into two disjoint sets S1 of elements v and S2 of elements v 4 Return QuickSort S1 followed by v followed by QuickSort S2 QuickSort As its name implies QuickSort is the fastest known sorting algorithm in practice It was devised by C A R Hoare in 1962 Its average running time is O n log n and it is very fast It has worst case performance of O n2 QuickSort example 5 1 4 2 10 3 9 15 12 Pick the Random element as the pivot Say 10 Partition into the two subsets below 5 1 4 2 3 9 4 5 9 15 12 Sort the subsets 1 2 3 12 15 Recombine with the pivot 1 2 3 4 5 9 10 12 15 QuickSort Example full Unsorted List 5 1 4 2 10 3 9 Partition1 5 1 4 2 3 9 10 15 12 Partition2 1 2 3 4 5 9 12 15 Partition3 1 2 3 Sorted List 1 2 3 5 4 5 15 12 9 9 10 12 15 QuickSort Example full Unsorted List 5 11 4 12 10 3 9 15 12 QuickSort Example full Pivot 10 index 4 start 0 last 8 rightArrow 8 leftArrow 0 Start from right and search for pivot Index 6 Swap 4 and 6 Unsorted List 5 11 4 12 10 3 9 15 12 QuickSort Example full Pivot 10 index 6 start 0 last 8 rightArrow 6 leftArrow 0 5 11 4 12 9 3 10 15 12 QuickSort Example full Pivot 10 index 6 start 0 last 8 rightArrow 6 leftArrow 0 Search from left for pivot Index 1 Swap 1 and 6 5 11 4 12 9 3 10 15 12 QuickSort Example full Pivot 10 index 1 start 0 last 8 rightArrow 6 leftArrow 1 5 10 4 12 9 3 11 15 12 QuickSort Example full Pivot 10 index 1 start 0 last 8 rightArrow 6 leftArrow 1 Search from right for number pivot Index 5 Swap 1 and 5 rightArrow 5 5 10 4 12 9 3 11 15 12 QuickSort Example full Pivot 10 index 5 start 0 last 8 rightArrow 5 leftArrow 1 5 3 4 12 9 10 11 15 12 QuickSort Example full Pivot 10 index 1 start 0 last 8 rightArrow 5 leftArrow 1 Search from left for number pivot Index 3 leftArrow 3 Swap 3 5 5 3 4 12 9 10 11 15 12 QuickSort Example full Pivot 10 index 3 start 0 last 8 rightArrow 5 leftArrow 3 5 3 4 10 9 12 11 15 12 QuickSort Example full Pivot 10 index 3 start 0 last 8 rightArrow 5 leftArrow 3 Search from right for number pivot Index 4 rightArrow 4 Swap 3 4 5 3 4 10 9 12 11 15 12 QuickSort Example full Pivot 10 index 4 start 0 last 8 rightArrow 4 leftArrow 3 Search from left for number pivot leftArrow right Arrow 5 done Split at pivot index 4 QuickSort arr 0 3 start 4 1 3 QuickSort arr 5 8 4 1 5 last 5 3 4 9 10 12 11 15 12 QuickSort Example full QuickSort arr 0 3 Pivot 4 index 2 start 0 last 3 5 3 4 9 10 12 11 15 12 QuickSort Example full Pivot 4 index 2 start 0 last 3 leftArrow 0 rightArrow 3 Start from right search for number pivot Index 2 rightArrow 2 No swap 5 3 4 9 10 12 11 15 12 QuickSort Example full Pivot 4 index 2 start 0 last 3 leftArrow 0 rightArrow 2 Start from left search for number pivot Index 0 leftArrow 0 Swap 0 2 5 3 4 9 10 12 11 15 12 QuickSort Example full Pivot 4 index 0 start 0 last 3 leftArrow 0 rightArrow 2 4 3 5 9 10 12 11 15 12 QuickSort Example full Pivot 4 index 0 start 0 last 3 leftArrow 0 rightArrow 2 Start from left search for number pivot Index 1 leftArrow 1 Swap 0 1 4 3 5 9 10 12 11 15 12 QuickSort Example full Pivot 4 index 1 start 0 last 3 leftArrow 1 rightArrow 2 Start from right search for number pivot rightArrow leftArrow 1 done Pivot index 1 quickSort arr 0 0 quickSort arr 2 3 3 4 5 9 10 12 11 15 12 QuickSort Example full quickSort arr 0 0 Pivot 3 indx 1 start 0 last 0 leftArrow 0 rightArrow 0 leftArrow rightArrow done 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 4 index 1 start 0 last 3 leftArrow 1 rightArrow 2 Start from right search for number pivot rightArrow leftArrow 1 done Pivot index 1 quickSort arr 0 0 quickSort arr 2 3 3 4 5 9 10 12 11 15 12 QuickSort Example full quickSort arr 2 3 Pivot 5 indx 2 start 2 last 3 leftArrow 2 rightArrow 3 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 5 indx 2 start 2 leftArrow 2 rightArrow 3 Start from right find number rightArrow leftArrow 2 Done quickSort arr 2 1 last quickSort arr 3 3 start 3 4 5 9 10 12 11 15 12 last 3 pivot indx 1 indx 1 QuickSort Example full quickSort arr 2 1 start 2 last 3 Start last done 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 5 indx 2 start 2 leftArrow 2 rightArrow 3 Start from right find number rightArrow leftArrow 2 Done quickSort arr 2 1 last quickSort arr 3 3 start 3 4 5 9 10 12 11 15 12 last 3 pivot indx 1 indx 1 QuickSort Example full quickSort arr 3 3 start 3 last 3 Start last done 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 10 index 4 start 0 last 8 rightArrow 4 leftArrow 3 Search from left for number pivot leftArrow right Arrow 5 done Split at pivot index 4 QuickSort arr 0 3 start 4 1 3 QuickSort arr 5 8 4 1 5 last 5 3 4 9 10 12 11 15 12 QuickSort Example full QuickSort arr 5 8 Pivot 11 indx 6 start 5 last 8 leftArrow 5 rightArrow 8 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 11 indx 6 start 5 last 8 leftArrow 5 rightArrow 8 Start from right find number pivot rightArrow 6 indx noswap 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 11 indx 6 start 5 last 8 leftArrow 5 rightArrow 6 Start from left find number pivot leftArrow 5 Swap 5 6 3 4 5 9 10 12 11 15 12 QuickSort Example full Pivot 11 indx 5 start 5 last 8 leftArrow …
View Full Document
Unlocking...