FOR FREE YEAR SOLVED

Radix sort is a sorting technique which is different from the concept of bubble, selection, merge or quick sort as radix sort is done by depending on the digits of the elements from the right most bit to the left most bit and by sorting the positional digits the sorting is performed. Unlike the other commonly used sorting algorithms, radix sort is a non-comparison based sorting algorithm. It depends on the place values of the numbers and grouped together according to the place values and thus sorting is performed.

PROCEDURE WITH EXAMPLE:

Suppose an array of 7 elements is taken to perform radix sort as follows:

Now, this array is to be sorted. Before sorting the array the number of digits in the maximum element is to be found out. In this case, the maximum element of this array is 654 and the number of digits if this element is 3. So the number of passes required to sort is 3.

Pass 1:

In the first pass the right most digits of the element is considered and will be sorted according to those digits and we will get the array as:

Pass 2:

After the first pass, the array is sorted according to the right most digit of the elements and the array is:

Now in the second pass the 2nd digit from the right side will be considered and will be sorted according to those digits underlined in the above array. Now the array will be sorted and the new array will be:

Now, the array is sorted according to the 2nd digit (from the right side) of each element of the array.

Pass 3:

This is the last pass to sort the elements of the array, so here the array will be sorted according to the most significant bit that is the left most bit of each element. The elements which are of 2 digits, for that elements the 3rd bit from the right side is not available, hence ‘0’ will be considered as the most significant bit of the elements as follows:

So the final sorted array will be:

INPUT:An unsorted array a[6,2,4,1,…………….,n]
OUTPUT:  An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

Step 1: Create a function “void radixsort(int a[],int n)”
	  Step 1.1: Set or initialise the all elements of an integer type array ‘d’ at 0 i.e
			Set  d[i] <- 0 [ i= 0 to 9]
      Step 1.2: Take the max number of digit in an integer type variable ‘max’ and this is the number          of required pass to do the sorting.
	  Step 1.3: While(pass ≤ max) then repeat  Step 1.4 to Step 1.22
	  Step 1.4: For i=0 to i<n  repeat  Step 1.5 to Step 1.13
	  Step 1.5:  Set  c <- 0
	  Step 1.6:  Set  p <- a[i]
	  Step 1.7: While(c<pass) then  repeat  Step  1.8 to Step 1.10
	  Step 1.8:  Set  r <- p mod 10
	  Step 1.9:  Set  p <- p/10
	  Step 1.10: Set  c <- c+1
		[End of Step 1.7 ‘While’ loop]
	 Step 1.11:  Set  j <- d[r]
	 Step 1.12:  Set  b[r][j] <- a[i]             
     Step 1.13:  Set  d[r] <- d[r]+1
		[End of Step 1.4 ‘For’ loop]
	 Step 1.14:  Set  pass <- pass+1
	 Step 1.15:  Set I <- 0
	 Step 1.16: For  j=0 to 9 repeat Step 1.17 to Step 1.20
	 Step 1.17: If(d[j]>0) then do
     Step 1.18: For  k=0 to k<d[j] repeat  Step 1.19 and Step 1.20
	 Step 1.19: Set  a[i] <- b[j][k]
	 Step 1.20: Set  I <- i+1
		[End of  Step 1.18 ‘For’ loop]
		[End of ‘If’]
		[End of Step 1.16 ‘For’ loop]
	 Step 1.21: For i=0 to 9 repeat Step 1.22
	 Step 1.22: Set d[i] <- 0
	[End of 1.3 ‘While’ loop]
[End of the function “void radixsort(int a[],int n)”]

Step 2: Create the function “void main()”

  Step 2.1 Take the number of elements from the user in an integer type variable ‘n’ .
  Step 2.2: Take the unsorted elements from the user in an array ‘a’.
  Step 2.3: Print the unsorted array.
  Step 2.4: Call the function ‘radixsort(a,n)’
  Step 2.5: Print the sorted array ‘a’.
  Step 2.6: Stop.
[End of the function “void main()”]

Step 3: Stop.