X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 14 / 28

65 views

0 shares

0 downloads

0 comments

14 / 28

Comp 122

linsort - 14

Lin / Devi

Comp 122

Radix Sort

It was used by the card-sorting machines.

Card sorters worked on one column at a time.

It is the algorithm for using the machine that extends the technique to multi-column sorting.

The human operator was part of the algorithm!

Key idea: sort on the “least significant digit” first and on the remaining digits in sequential order.  The sorting method used to sort each digit must be “stable”.

»

If we start with the “most significant digit”, we’ll need extra storage.

Document info
Document views65
Page views65
Page last viewedSun Dec 04 21:43:09 UTC 2016
Pages28
Paragraphs427
Words1924

Comments