I&C SCI 46 Lecture Notes - Lecture 8: Radix Sort, Bucket Sort, Radix

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

In this lecture, we will examine two sorting methods that do not use comparisons between values to sort the data. So, they are not constrained by the lower bound proved in the previous lecture. The algorithms are called bucket sort and radix sort. Both are a bit strange; they work well for integers (and radix sort for strings) but don"t work well for other kinds of data (e. g. , anything that is not. digital, in the same sense as a digital tree). Bucket sort allows us to sort n data values, where each lies in the range 0-m in time o(n+m). B-s), then sort these values, then scan it a final time (o(n)) adding s to every value. The scaling and unscaling processes are each o(n) (adding three o(n) passes to the data). We will analyze a few problems with various sizes of n and m below.