COMPSCI 61B Lecture Notes - Lecture 36: Radix Sort, Counting Sort, Natural Number
28 Aug 2017
School
Department
Course
Professor
Document Summary
Key idea: sorting requires (n log n) compares (worst case input) Simplest case: keys are unique integers from 0 to n-1. Iterate through list, using count array to decide where to put everything. Total runtime on n keys with alphabet of size r: (n+r) Create an array of size r to store counts: (r) Creating an array of size n to store ordered data: (n) Copying items from original array to ordered array: do n times: Copying items from ordered array back to original array: (n) If n is r, then we expect reasonable performance. Is better than quick sort if n is really big. Quick sort is better if the keys are not consecutive but have a big range (and you"re not using a map) Strings consist of characters from a nite alphabet. Sort each digit independently from rightmost digit towards left (using counting sort) Handle non-equal key lengths by considering empty spots as the smallest value.
