CSE 326 Sorting Henry Kautz Autumn Quarter 2002 1 Material to be Covered Sorting by comparision 1 2 3 4 Bubble Sort Selection Sort Merge Sort QuickSort Efficient list based implementations Formal analysis Theoretical limitations on sorting by comparison Sorting without comparing elements Sorting and the memory hierarchy 2 Bubble Sort Idea Move smallest element in range 1 n to position 1 by a series of swaps Move smallest element in range 2 n to position 2 by a series of swaps Move smallest element in range 3 n to position 3 by a series of swaps etc 3 Selection Sort Idea Rearranged version of Bubble Sort Are first 2 elements sorted If not swap Are the first 3 elements sorted If not move the 3rd element to the left by series of swaps Are the first 4 elements sorted If not move the 4th element to the left by series of swaps etc 4 Selection Sort procedure SelectionSort Array 1 N For i 2 to N j i while j 0 Array j Array j 1 swap Array j Array j 1 j 5 Why Selection or Bubble Sort is Slow Inversion a pair i j such that i j but Array i Array j Array of size N can have N2 inversions Selection Bubble Sort only swaps adjacent elements Only removes 1 inversion at a time Worst case running time is N2 6 Merge Sort MergeSort Table 1 n Split Table in half Recursively sort each half Merge two halves together Merge Merging Cars by key Aggressiveness of driver Most aggressive goes first Photo from http www nrma com au inside nrma m h m road rage html T1 1 n T2 1 n i1 1 i2 1 While i1 n i2 n If T1 i1 T2 i2 Next is T1 i1 i1 Else Next is T2 i2 i2 End If End While 7 Merge Sort Running Time T 1 b T n 2T n 2 cn Any difference best worse case for n 1 T n 2T n 2 cn T n 4T n 4 cn cn substitute T n 8T n 8 cn cn cn substitute T n 2kT n 2k kcn inductive leap T n nT 1 cn log n where k log n select value for k T n n log n simplify 8 QuickSort Picture from PhotoDisc com 15 28 47 1 Pick a pivot 2 Divide list into two lists One less than or equal to pivot value One greater than pivot 3 Sort each sub problem recursively 4 Answer is the concatenation of the two solutions 9 QuickSort Array Based Version Pick pivot 7 2 8 3 5 9 6 Partition with cursors 7 2 8 3 5 9 6 2 goes to less than 7 2 8 3 5 9 6 10 QuickSort Partition cont d 6 8 swap 7 less greater than 2 6 3 5 9 3 5 less than 9 greater than Partition done 8 7 2 6 3 5 9 8 7 2 6 3 5 9 8 11 QuickSort Partition cont d Put pivot into final position Recursively sort each side 5 2 2 3 6 5 3 6 7 7 9 8 8 9 12 QuickSort Complexity QuickSort is fast in practice but has N2 worst case complexity Tomorrow we will see why But before then 13 List Based Implementation All these algorithms can be implemented using linked lists rather than arrays while retaining the same asymptotic complexity Exercise Break into 6 groups 6 or 7 people each Select a leader 25 minutes to sketch out an efficient implementation Summarize on transparencies Report back at 3 00 pm 14 Notes Almost Java pseudo code is fine Don t worry about iterators hiding etc just directly work on ListNodes The head field can point directly to the first node in the list or to a dummy node as you prefer 15 List Class Declarations class LinkedList class ListNode Object element ListNode next ListNode head void Sort 16 My Implementations Probably no better or worse than yours Assumes no header nodes for lists Careless about creating garbage but asymptotically doesn t hurt For selection sort did the bubble sort variation but moving largest element to end rather than smallest to beginning each time Swapped elements rather than nodes themselves 17 My QuickSort void QuickSort sort self if is empty return Object val Pop choose pivot b new List c new List Split val b c split self into 2 lists b QuickSort c QuickSort c Push val insert pivot b Append c concatenate solutions head b head set self to solution 18 Split Append void Split Object val List b c if is empty return Object obj Pop if obj val b Push val else c Push val Split val b c void Append List c if head null head c head else Last next c head 19 Last Push Pop ListNode Last ListNode n head if n null return null while n next null n n next return n void Push Object val ListNode h new ListNode val h next head head h Object Pop if head null error Object val head element head head next return val 20 My Merge Sort void MergeSort sort self if is empty return b new List c new List SplitHalf b c split self into 2 lists b MergeSort c MergeSort head Merge b head c head set self to merged solutions 21 SplitHalf Merge void SplitHalf List b c if is empty return b Push Pop SplitHalf c b alternate b c ListNode Merge ListNode b c if b null return c if c null return b if b element c element Using Push would reverse lists this technique keeps lists in order b next Merge b next c return b else c next Merge b c next return c 22 My Bubble Sort void BubbleSort int n Length length of this list for i 2 i n i ListNode cur head ListNode prev null for j 1 j i j if cur element cur next element swap values alternative would be to change links instead Object tmp cur element cur element cur next element cur next element tmp prev cur cur cur next 23 Let s go to the Races 24 Analyzing QuickSort Picking pivot constant time Partitioning linear time Recursion time for sorting left partition say of size i time for right size N i 1 time to combine solutions T 1 b T N T i T N i 1 cN where i is the number of elements smaller than the pivot 25 QuickSort Worst case Pivot is always smallest element so i 0 T N T i T N i 1 cN T N T N 1 cN T N 2 c N 1 cN k 1 T N k c N i i 0 O N2 26 Dealing with Slow QuickSorts Randomly choose pivot Good theoretically and practically but call to random number generator can be expensive Pick pivot cleverly Median of 3 rule takes Median first middle last element elements Also works well 27 QuickSort Best Case Pivot is always middle …