Radix Sort

One of best sorting algorithms.

At the beginning, computer programs were written in FORTRAN and then entered into punch cards. A normal program would result in 1000 or more punch cards. These cards were needed to be entered into in the machine in a definite order. This order was maintained by numbering these cards which was done by punching the numbers onto these cards in a sequence. If however these cards were mixed together then they needed to be sorted before they can be used for further application. Hence special card sorters were used for sorting these cards.

These cards sorted were initial physical realization of radix sort algorithm. As they use to sort these cards by distributing them based on digit at the same significant position on each cards and slowly proceeding to the higher significant positions.

Herman Hollerith (February 29, 1860 – November 17, 1929) is first known to have generated an algorithm similar to Radix sort. A computer algorithm was invented for radix sort in 1954 at MIT by Harold H. Seward.

Radix refers to the base of the number system. Like the decimal number system has a radix of 10 and binary number system has a radix of 2. Radix sort is basically a multiple pass distribution sorting algorithm. This means that keys are distributed into buckets based on the significant part of the key. After the first pass all the keys in the buckets are collected in order. Then again they are redistributed into buckets based on the next significant part of the keys. This process is continued till the distribution based on most significant digit of the key is completed. The main idea of the radix sort is that each time the keys are collected from the bucket the ordering of the keys is maintained, this helps to sort the keys.

prepare by 

phurba sherpa

sandip sahini

Kathmandu University, Nepal

References:

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

Simon Harris and James Ross, Beginning Algorithms, Second edition, Wiley publication, ISBN-13: 978-0-7645- 9674-2 : Published 2006 by Wiley Publishing, Inc., Indianapolis, Indiana

E.Horowitz and Satraj Sahni, Fundamental of Data Structure.

comments powered by Disqus
Loading