Page 233 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes At the first for loop, the variable m will store the highest number from the array.
At the while loop, the condition is to check if the number still has digits, and while this is true,
a bucket (an array) with maxim 10 storage places (the values from 0 to 9) will store the proper
numbers, just like in the example from above. At the end of the while loop the exp must increase
by a factor of 10 compared to the previous one, and at the next check of the while loop, the
condition will be tested to see if the number of digits is greater than 0.
The time complexity of the algorithm is as follows: Suppose that the n input numbers have
maximum k digits. Then the Counting Sort procedure is called a total of k times. Counting Sort
is a linear, or O(n) algorithm. So the entire Radix Sort procedure takes O(k*n) time. If the
numbers are of finite size, the algorithm runs in O(n) asymptotic time.

Advantages and Disadvantages of Radix Sort

The advantages of Radix Sort are:
if it’s implemented in Java, it would be faster than QuickSort or HeapSort;
is stable, meaning it preserves existing order of equal keys.

is quite good on small keys.
Disadvantages of Radix Sort are:
does not work well when you have very long keys, because the total sorting time is
proportional to key length and to the number of items to sort.

you have to write an unconventional compare routine.
It requires fixed size keys, and some standard way of breaking the keys into pieces.

Task Make distinction between Selection sort and Radix sort.

Self Assessment

Fill in the blanks:
7. ......................... is a non-comparative integer sorting algorithm that sorts data with integer
keys by grouping keys by the individual digits which share the same significant position
and value.
8. The ........................ sorting type begins from the least significant digit to the most significant
digit.

13.5 Hashing

Searching an element from a large collection of data is always an exhausting job. There are many
searching algorithms and techniques to perform searching operation but to search an element
from a large collection of data is a challenging task to complete in efficient time. Hashing is a
process of storing a large amount of data and retrieving elements from it in optimal time.
Hashing is the solution when we want to search an element from a large collection of data.
For example suppose we store the information of 10,000 students of a university using a structure
in C. Every student has a unique id. If we want to search the attributes of a particular student then
there are various approaches that can strike our mind for doing this searching operation.

226 LOVELY PROFESSIONAL UNIVERSITY