Question Name:Radix Sorting

#include<iostream> 
using namespace std; 
 
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; 
} 
  
void countSort(int arr[], int n, int exp) 
{ 
    int output[n]; 
    int i, count[10] = {0}; 
  
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%10 ]++; 
  
    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 
  
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%10 ]--; 
    } 
  
   
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
  for(i=0;i<n;i++) 
  { 
    cout<<arr[i]<<" ";
  }cout<<"\n";
} 
  

void radixsort(int arr[], int n) 
{ 
    int m = getMax(arr, n); 
  
    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(arr, n, exp); 

} 
  
void print(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
} 
  
int main() 
{ 
    int n,i,j; 
  int arr[n];
  cin>>n;
  j=n;
  for(i=0;i<n;i++) 
  { 
    cin>>arr[i];
  }
  radixsort(arr, n); 
//aviraj
    return 0; 
} 

Problem Description

Given an array of N integers, you need to print the array after each pass of radix sort. In each pass, you need to sort the array by digits starting from least significant digit to most significant digit.

Input:

The first line consists of an integer N denoting the size of array.
The next line consists of N space separated integers.

Output:

Print the array after each pass. See the output for clarity.

  • Test Case 1

    Input (stdin)

    8
    170 45 75 90 802 24 2 66
    

    Expected Output

    170 90 802 2 24 45 75 66 
    802 2 24 45 66 170 75 90 
    2 24 45 66 75 90 170 802
  • Test Case 2

    Input (stdin)

    10
    65 47 212 89 177 14 345 68 2 684 
    

    Expected Output

    212 2 14 684 65 345 47 177 68 89 
    2 212 14 345 47 65 68 177 684 89 
    2 14 47 65 68 89 177 212 345 684

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro