CSE 116 Lecture Notes - Lecture 41: Radix Sort, Bucket Sort, Sorting Algorithm

• School: University at Buffalo
• Department: Computer Science & Engineering
• Course: CSE 116
• Professor: Matthew Hertz

Document Summary

Sorts collection, c, in two phases: remove each element v from c & add to b[v, move elements from each bucket back to c. //phase 1 for-each playingcard pc in c endfor. //phase 2 toc = 0 for-each list b in b endfor. Algorithm bucketsort(list c) return c for-each playingcard pc in b endfor. Clicker question: data type usable by bucket-sort: int, double, string, anything comparable, all of the above answer: a. int. For this to work, values must map to legal indices: non-negative integer values needed to access arrays. If elements easily matched to array index can sort without comparisons! Bucket-sort is stable (preserves relative ordering of equal elements) Use comparator for bucket-sort: get index for v using compare(v, null) Comparator to bucket-sort booleans returns: 0 when v is false, 1 when v is true. Comparator to bucket-sorts us states returns: rank in annual per capita consumption of jello, rank in overall consumption of jello, state"s ra(cid:374)ki(cid:374)g by populatio(cid:374)