Data-Structures-Algorithms/Sorting/Radix Sort.cpp at master · FionaFR/Data-Structures-Algorithms · GitHub

History

executable file

72 lines (59 loc) · 1.09 KB

Raw

#include<bits/stdc++.h>

using namespace std;

void radixSort(int *arr, int &no_of_elmnts){

int min = INT_MAX;

int max = INT_MIN;

for(int i=0;i<no_of_elmnts;i++){

if(arr[i]>max){

max = arr[i];

continue;

}

if(arr[i]<min){

min=arr[i];

}

if(min<0){

for(int i=0;i<no_of_elmnts;i++){

arr[i]+=abs(min);

}

max+=abs(min);

}

int rounds=0;

while(max){

rounds++;

max/=10;

}

vector< list<int> > buckets;

int place_value=1;

for(int i=0;i<rounds;i++){

buckets.clear();

buckets.resize(10);

for(int j=0;j<no_of_elmnts;j++){

buckets[ (arr[j]/place_value) % 10 ].push_back(arr[j]);

}

int arr_index=0;

for(int j=0;j<10;j++){

list<int>::iterator it;

for(it=buckets[j].begin(); it!=buckets[j].end();it++){

arr[arr_index++]=*it;

}

place_value*=10;

}

if(min<0){

for(int i=0;i<no_of_elmnts;i++){

arr[i]+=min;

}

int main(){

// freopen("input.txt", "rd", stdin);

int no_of_elmnts;

cin>>no_of_elmnts;

int *arr = new int[no_of_elmnts];

for(int i=0;i<no_of_elmnts;i++){

cin>>arr[i];

}

radixSort(arr, no_of_elmnts);

return 0;

}

Data-Structures-Algorithms/Sorting/Radix Sort.cpp at master · FionaFR/Data-Structures-Algorithms · GitHub

Expand file tree

Breadcrumbs

Radix Sort.cpp

Latest commit

History

Breadcrumbs

Radix Sort.cpp

File metadata and controls