TAILIEUCHUNG - Bucket Sort and Radix Sort - CS 105
Bucket Sort and Radix Sort - CS 105 includes Time complexity of Sorting, Restrictions on the problem, Bucket sort, Bucket sort algorithm, Values versus entries, Time complexity, Sorting integers, Radix sort. | Bucket Sort and Radix Sort CS 105 Time complexity of Sorting Several sorting algorithms have been discussed and the best ones, so far: Can we do better than O( n log n )? 10/02/05 Heap sort and Merge sort: O( n log n ) Quick sort (best one in practice): O( n log n ) on average, O( n2 ) worst case No. It can be proven that any comparison-based sorting algorithm will need to carry out at least O( n log n ) operations Copyright 2005, by the authors of these slides, and Ateneo de Manila University. All rights reserved BucketSort Slide 2 Restrictions on the problem Suppose the values in the list to be sorted can repeat but the values have a limit (., values are digits from 0 to 9) Sorting, in this case, appears easier Is it possible to come up with an algorithm better than O( n log n )? 10/02/05 Yes Strategy will not involve comparisons Copyright 2005, by the authors of these slides, and Ateneo de Manila University. All rights reserved BucketSort Slide 3 Bucket sort Idea: suppose the values are in the range 0m-1; start with m empty buckets numbered 0 to m-1, scan the list and place element s[i] in bucket s[i], and then output the buckets in order Will need an array of buckets, and the values in the list to be sorted will be the indexes to the buckets 10/02/05 No comparisons will be necessary Copyright 2005, by the authors of these slides, and Ateneo de Manila University. All rights reserved BucketSort Slide 4 Example 4 2 1 2 0 3 2 1 0 0 0 0 0 0 1 10/02/05 1 1 1 2 2 2 2 4 0 2 3 0 3 3 4 4 2 2 2 2 3 3 4 4 Copyright 2005, by the authors of these slides, and Ateneo de Manila University. All rights reserved BucketSort Slide .
đang nạp các trang xem trước
