Sorting Algorithms Fawzi Emad Chau Wen Tseng Department of Computer Science University of Maryland College Park Overview Comparison sort Bubble sort Selection sort Tree sort Heap sort Quick sort Merge sort O n2 O n log n Linear sort Counting sort Bucket bin sort Radix sort O n 1 Sorting Goal Arrange elements in predetermined order Based on key for each element Derived from ability to compare two keys by size Properties Stable relative order of equal keys unchanged In place uses only constant additional space External can efficiently sort large of keys Sorting Comparison sort Only uses pairwise key comparisons Proven lower bound of O n log n Linear sort Uses additional properties of keys 2 Bubble Sort Approach 1 Iteratively sweep through shrinking portions of list 2 Swap element x with its right neighbor if x is larger Performance O n2 average worst case Bubble Sort Example Sweep 1 Sweep 2 Sweep 3 Sweep 4 7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 5 7 4 8 2 4 5 7 8 2 7 5 8 4 2 5 4 7 8 2 7 5 4 8 3 Bubble Sort Code void bubbleSort int a int outer inner for outer a length 1 outer 0 outer for inner 0 inner outer inner if a inner a inner 1 Swap with int temp a inner Sweep right neighbor a inner a inner 1 through if larger array a inner 1 temp Selection Sort Approach 1 Iteratively sweep through shrinking portions of list 2 Select smallest element found in each sweep 3 Swap smallest element with front of current list Performance O n2 average worst case Example 7 2 8 5 4 2 7 8 5 4 2 4 8 5 7 2 4 5 8 7 2 4 5 7 8 4 Selection Sort Code void selectionSort int a int outer inner min for outer 0 outer a length 1 outer min outer for inner outer 1 inner a length inner if a inner a min Find smallest Sweep min inner element through array Swap with smallest int temp a outer element found a outer a min a min temp Tree Sort Approach 1 Insert elements in binary search tree 2 List elements using inorder traversal Performance Binary search tree O n log n average case O n2 worst case Balanced binary search tree O n log n average worst case Example Binary search tree 7 2 8 5 4 7 2 8 5 4 5 Heap Sort Approach Example 1 Insert elements in heap Heap 2 Remove smallest 2 element in heap repeat 3 List elements in order of removal from heap Performance O n log n average worst case 4 7 8 5 7 2 8 5 4 Quick Sort Approach 1 Select pivot value near median of list 2 Partition elements into 2 lists using pivot value 3 Recursively sort both resulting lists 4 Concatenate resulting lists For efficiency pivot needs to partition list evenly Performance O n log n average case O n2 worst case 6 Quick Sort Algorithm 1 If list below size K Sort w other algorithm x 2 Else pick pivot x and partition S into L elements x E elements x G elements x 3 Quicksort L G x L E 4 Concatenate L E G If not sorting in place G x Quick Sort Code void quickSort int a int x int y int pivotIndex if y x 0 pivotIndex partionList a x y quickSort a x pivotIndex 1 quickSort a pivotIndex 1 y Lower Upper end of end of array array region region to be to be sorted sorted int partionList int a int x int y partitions list and returns index of pivot 7 Quick Sort Example 7 2 8 5 4 2 5 4 2 4 7 2 4 5 7 8 8 2 4 5 5 4 2 5 7 8 4 5 4 5 Partition Sort Result Quick Sort Code int partitionList int a int x int y int pivot a x int left x int right y Use first element as pivot while left right while a left pivot left right left while a right pivot right if left right Partition elements in array relative to value of pivot swap a left right swap a x right return right Place pivot in middle of partitioned array return index of pivot 8 Merge Sort Approach 1 Partition list of elements into 2 lists 2 Recursively sort both lists 3 Given 2 sorted lists merge into 1 sorted list a Examine head of both lists b Move smaller to end of new list Performance O n log n average worst case Merge Example 2 4 5 2 7 4 5 8 4 5 8 2 4 7 8 2 4 5 7 2 7 7 8 2 4 5 7 8 5 8 9 Merge Sort Example 2 4 5 7 8 7 2 8 5 4 8 5 4 7 2 7 2 8 5 4 5 4 5 8 2 7 7 2 4 Split 8 4 5 5 4 Merge Merge Sort Code void mergeSort int a int x int y int mid x y 2 Lower if y x return end of mergeSort a x mid array mergeSort a mid 1 y region merge a x y mid to be sorted void merge int a int x int y int mid merges 2 adjacent sorted lists in array Upper end of array region to be sorted 10 Merge Sort Code Upper end of 1st array region void merge int a int x int y int mid int size y x Upper Lower int left x end of end of 2nd array int right mid 1 1st array region int tmp int j region for j 0 j size j if left mid tmp j a right else if right y a left a right tmp j a left Copy smaller of two else tmp j a right elements at head of 2 array regions to tmp for j 0 j size j buffer then move on a x j tmp j Copy merged array back Counting Sort Approach 1 Sorts keys with values over range 0 k 2 Count number of occurrences of each key 3 Calculate of keys each key 4 Place keys in sorted location using keys counted If there are x keys key y Put y in xth position Decrement x in case more instances of key y Properties O n k average worst case 11 Counting Sort Example Original list 7 2 8 5 4 0 1 2 3 4 Count 0 0 1 0 1 1 0 1 1 0 1 2 3 4 5 6 7 8 Calculate keys value 0 0 1 1 2 3 3 4 5 0 1 2 3 4 5 6 7 8 Counting Sort Example Assign locations 0 0 1 1 2 …
View Full Document
Unlocking...