[Algoritmi] Selection sort + radix sort
Inviato: 19/07/2019, 18:21
Buonasera! Sto studiando il radix sort. Ho capito come funziona, ma non riesco a implementarlo. Per prima cosa ho trovato un modo per sapere quante volte un'algoritmo di ordinamento dovrà ordinare i numeri (unità, decine, centinaia ecc), ma non sò come implementare la parte che consiste nel prenderli, ordinarli e poi salvari per ripartire da quella configurazione per ordinare le cifre successive. Ho letto che bisogna farlo usando il counting sort, che io avevo implementato tempo fa in maniera semplice, ma ora ho trovato una soluzione che non conoscevo, vorrei capirla insieme a voi:
Vorrei che mi aiutaste a capire come funziona questo codice, poi devo riuscire a integrarlo nel radix sort. Grazie in anticipo!
- Codice:
#include <iostream>
using namespace std;
const int RANGE = 9;
void countingSort(int arr[],int n,int RANGE){
int count[9]={0};
int i;
int out[n];
for(i=0;i<n;i++)
++count[arr[i]];
for(i=1;i<RANGE;i++)
count[i]+=count[i-1];
for(i=n-1;i>=0;i--){
out[count[arr[i]]-1]=arr[i];
--count[arr[i]];
}
for(i=0;i<n;i++)
arr[i]=out[i];
}
void print(int arr[],int n)
{
cout<<"array : ";
for(int i=0;i<n;i++)
cout<<arr[i]<<' ';
cout<<endl;
}
int main() {
int arr[]={1, 4, 1, 2, 7, 5, 2};
int n=sizeof(arr)/sizeof(arr[0]);
print(arr,n);
countingSort(arr,n,RANGE);
print(arr,n);
return 0;
}
Vorrei che mi aiutaste a capire come funziona questo codice, poi devo riuscire a integrarlo nel radix sort. Grazie in anticipo!