×

Courses

Chapters

>
<

Aptitude

Radix sort

Radix sort

It is a sorting algorithm that is used to sort element. Radix sort is the method that many people begin to use when alphabetizing a large list of name or numeric number.Specifically ,

The list of names is first sorted according to the first letter of each name. That is, the names are arranged in 26 classes,where the first class consist of those name that begin with “A�, the second class consists of those name that begin with “B�,and so on.During the second pass, each class is alphabetized according to the second letter of the name.And so on.

The time complexity of Radix sort is O(kn) and space complexity of Radix sort is O(k+n).the running time of Radix appears to be better than Quick Sort for a wide range of input numbers.

Implementation of Radix sort

Let us take an example of radix sort

Given to a list ,the numbers would be sorted in three phases. the list is (248,140,261,323,438,120,221,443,266).

(A)- In the first phase, the once digits are sorted into list.. The number are collected box by box ,from pocket 8 to 0.(Note 261 will now be at the bottom of the pile and 438 at the top of the pile.) The cards are now rein put to the sorter.

Implementation of Radix sort

(B)- In the second phase, the tens digits are sorted into pockets,Again the card are collected pocket by pocket and rein put to the sorter.

Implementation of Radix sort

(C) - In the last phase and third phase, we will notify that the hundred digit are sorted into pockets.

Implementation of Radix sort

So the final list is by ascending order to sorted digits or number is (120,140, 221,248,261,266,323,438,443).

Code
  
// Radix Sort in C Programming

#include<stdio.h>

// Function to get the largest element from an array
int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}

// Using counting sort to sort the elements in the basis of significant places
void countingSort(int array[], int size, int place) {
  int output[size + 1];
  int max = (array[0] / place) % 10;

  for (int i = 1; i < size; i++) {
    if (((array[i] / place) % 10) > max)
      max = array[i];
  }
  int count[max + 1];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  // Calculate count of elements
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;
    
  // Calculate cumulative count
  for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];

  // Place the elements in sorted order
  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

// Main function to implement radix sort
void radixsort(int array[], int size) {
  // Get maximum element
  int max = getMax(array, size);

  // Apply counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

// Print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int array[] = {121, 432, 564, 23, 1, 45, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);

  printf("Sorted Array in Ascending Order: \n");
  printArray(array, n);
}  
  

  
#include<iostream>
using namespace std;

// Function to get the largest element from an array
int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}

// Using counting sort to sort the elements in the basis of significant places
void countingSort(int array[], int size, int place) {
  const int max = 10;
  int output[size];
  int count[max];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  // Calculate count of elements
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;

  // Calculate cumulative count
  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  // Place the elements in sorted order
  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

// Main function to implement radix sort
void radixsort(int array[], int size) {
  // Get maximum element
  int max = getMax(array, size);

  // Apply counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

// Print an array
void printArray(int array[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}

// Driver code
int main() {
  int array[] = {121, 432, 564, 23, 1, 45, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);
  cout << "Sorted Array in Ascending Order:"<< endl;
  printArray(array, n);
}
  
  

  
class RadixSort {

  // Using counting sort to sort the elements in the basis of significant places
  void countingSort(int array[], int size, int place) {
    int[] output = new int[size + 1];
    int max = array[0];
    for (int i = 1; i < size; i++) {
      if (array[i] > max)
        max = array[i];
    }
    int[] count = new int[max + 1];

    for (int i = 0; i < max; ++i)
      count[i] = 0;

    // Calculate count of elements
    for (int i = 0; i < size; i++)
      count[(array[i] / place) % 10]++;

    // Calculate cumulative count
    for (int i = 1; i < 10; i++)
      count[i] += count[i - 1];

    // Place the elements in sorted order
    for (int i = size - 1; i >= 0; i--) {
      output[count[(array[i] / place) % 10] - 1] = array[i];
      count[(array[i] / place) % 10]--;
    }

    for (int i = 0; i < size; i++)
      array[i] = output[i];
  }

  // Function to get the largest element from an array
  int getMax(int array[], int n) {
    int max = array[0];
    for (int i = 1; i < n; i++)
      if (array[i] > max)
        max = array[i];
    return max;
  }

  // Main function to implement radix sort
  void radixSort(int array[], int size) {
    // Get maximum element
    int max = getMax(array, size);

    // Apply counting sort to sort elements based on place value.
    for (int place = 1; max / place > 0; place *= 10)
      countingSort(array, size, place);
  }
  
  // Print an array
    static void printArray(int array[], int size) {
      for (int i = 0; i < size; ++i) {
        System.out.print(array[i] + " ");
      }
      System.out.print("\n");
    }

  // Driver code
  public static void main(String args[]) {
    int[] data = { 121, 432, 564, 23, 1, 45, 788 };
    int size = data.length;
    RadixSort rs = new RadixSort();
    rs.radixSort(data, size);
    System.out.print("Sorted Array in Ascending Order: \n");
    printArray(data,size);
  }
}
	
	

	
Sorted Array in Ascending Order: 
1, 23, 45, 121, 432, 564, 788
Time Complexity for Linear Search
BestAverageWorstSpace ComplexityAverage Comparision
O(d(n + k))O(d(n + k))O(d(n + k))
→
←