• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

How Radix sort works

September 4, 2014 by Dhaval Dave

Radix sort is simple and unique sorting method.
It sorts number with LSD and MSD ( Lease Significant Digit to Most Significant Digit)

Radix Sort puts the elements in order by comparing the digits of the numbers. I will explain with an example.


Consider the following 9 numbers:

493   812   715   710   195   437   582   340   385

Step 1) We should start sorting by comparing and ordering the one’s digits:

Digit Sublist
0   340 710
1
2   812 582
3   493
4
5   715 195 385
6
7   437
8
9

Notice that the numbers were added onto the list in the order that they were found, which is why the numbers appear to be unsorted in each of the sublists above. Now, we gather the sublists (in order from the 0 sublist to the 9 sublist) into the main list again:

340   710   812   582   493   715   195   385   437
Step 2) Now, the sublists are created again, this time based on the ten’s digit:
Digit Sublist
0
1   710 812 715
2
3   437
4   340
5
6
7
8   582 385
9   493 195
Now the sublists are gathered in order from 0 to 9:
710   812   715   437   340   582   385   493   195
Step 3) the sublists are created according to the hundred’s digit:

Digit Sublist
0
1   195
2
3   340 385
4   437 493
5   582
6
7   710 715
8   812
9
At last, the list is gathered up again:
195   340   385   437   493   582   710   715   812
Code :

#include<iostream>
using namespace std;

// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}

// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
    int output[n]; // output array
    int i, count[10] = {0};

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%10 ]++;

    // Change count[i] so that count[i] now contains actual position of
    // this digit in output[]
    for (i = 1; i < 10; i++)
        count[i] += count[i – 1];

    // Build the output array
    for (i = n – 1; i >= 0; i–)
    {
        output[count[ (arr[i]/exp)%10 ] – 1] = arr[i];
        count[ (arr[i]/exp)%10 ]–;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to curent digit
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

// The main function to that sorts arr[] of size n using Radix Sort
void radixsort(int arr[], int n)
{
    // Find the maximum number to know number of digits
    int m = getMax(arr, n);

    // Do counting sort for every digit. Note that instead of passing digit
    // number, exp is passed. exp is 10^i where i is current digit number
    for (int exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

// A utility function to print an array
void print(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << ” “;
}

// Driver program to test above functions
int main()
{
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixsort(arr, n);
    print(arr, n);
    return 0;
}

Output:

2  24  45  66  75  90  170  802


References:
http://en.wikipedia.org/wiki/Radix_sort
Code : http://www.geeksforgeeks.org/radix-sort/

Similar Articles

Filed Under: Interview Questions, problem Tagged With: Sorting

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

SAP Interview Questions

Max Sum in circularly situated Values

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Templates in C++

Coin Collection Dynamic Programming

Find loop in Singly linked list

Binary Tree in Java

FizzBuzz Solution C C++

Printing Longest Common Subsequence

Flipkart Set 1 On Campus with Answers

Find the smallest window in a string containing all characters of another string

Maximum of all subarrays of size k

Calculate price of parking from parking start end time prices

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Amazon Interview Experience – SDE Chennai

Printing intermediate Integers between one element & next element of array

Find min element in Sorted Rotated Array (Without Duplicates)

Count Possible Decodings of a given Digit Sequence

Find the number ABCD such that when multipled by 4 gives DCBA.

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Serialise Deserialise N-ary Tree

Stock Buy Sell to Maximize Profit

How strtok() Works

Maximum path sum between two leaves

HackeEarth Flipkart’s Drone

TicTacToe Game As Asked in Flipkart

Find and print longest consecutive number sequence in a given sequence in O(n)

Interfaces in C++ (Abstract Classes in C++)

Binary Tree Isomorphic to each other

Copyright © 2025 · Genesis Framework · WordPress · Log in