Cerința

Fiind dat un șir cu n elemente, nu neapărat distincte, se cere sortarea crescătoare a acestuia folosind metoda Radix Sort.

Date de intrare

Fișierul de intrare radixsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat.

Restricții și precizări

2 ≤ n ≤ 1.000.000;
numerele de pe a doua linie a fișierului de intrare vor avea maximum 9 cifre.

Exemplu

radixsort.in

8
170 20 45 75 90 802 24 2

radixsort.out

2 20 24 45 75 90 170 802

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema RadixSort :

#include<fstream> 
using namespace std; 

int arr[1000005]; 
int output[1000005];

// Calculeaza maximul din vectorul initial
int getMax(int n) 
{ 
    int maxX = arr[0]; 
    for (int i = 1; i < n; i++) 
        if (arr[i] > maxX) 
            maxX = arr[i]; 
    return maxX; 
} 

// Counting Sort - se afla la baza RadixSort
void countSort(int n, int exp) 
{ 
    int i, count[32] = {0}; 

    // Tinem minte numarul de aparitii in vectorul count
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%32 ]++; 

    // Modificam count[i] astfel incat count[i] sa contina
    // pozitia cifrei din output[]
    for (i = 1; i < 32; i++) 
        count[i] += count[i - 1]; 

    // Cream vectorul output
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%32 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%32 ]--; 
    } 

    // Copiem continutul vectorului output[] in arr[]
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
} 

// Radix Sort 
void radixsort(int n) 
{ 
    // Calculam cel mai mare element pentru a afla numarul
    // de cifre al acestuia
    int m = getMax(n); 


    // Folosim Counting Sort pentru fiecare cifra
    for (int exp = 1; m/exp > 0; exp *= 32) 
        countSort(n, exp); 
}

int main() 
{ 
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    int n, i; fin >> n;
    for(i = 0; i < n; ++i)
        fin >> arr[i];

    radixsort(n);

    for (i = 0; i < n; i++)
        (fout << arr[i]).put(' '); 
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2700 RadixSort

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2700 RadixSort de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2700 RadixSort