Rezolvare completă PbInfo #2720 BucketSort

Metoda Bucket Sort constă în distribuirea elementelor în mai multe grupe, numite “bucket-uri”. Apoi fiecare bucket este sortat individual folosind un algoritm de sortare oarecare.

Cerința

Se dă un şir cu n numere naturale ce trebuie sortat în funcţie de d. Dacă d este 1, şirul se va sorta descrescător, iar dacă este 0, se va sorta crescător.

Date de intrare

Fișierul de intrare bucketsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, iar pe a treia linie se va afla d.

Date de ieșire

Fișierul de ieșire bucketsort.out va conține pe prima linie şirul sortat în funcţie de d.

Restricții și precizări

  • n ≤ 10.000
  • toate numerele ≤ 100.000.000
  • d=0 pentru 50% din teste
  • d=1 pentru 50% din teste

Exemplu 1:

bucketsort.in

5
10 90 5 6 101
0

bucketsort.out

5 6 10 90 101

Explicație

Deoarece d este 0, şirul se sortează crescător

Exemplu 2:

bucketsort.in

5
10 90 5 6 101
1

bucketsort.out

101 90 10 6 5

Explicație

Deoarece d este 1, şirul se sortează descrescător

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 BucketSort:

#include <fstream>
#include <vector>
#include <algorithm>
#define l int

using namespace std;

///Rezolvare cu bucket-uri

ifstream fin("bucketsort.in");
ofstream fout("bucketsort.out");

int n,x,c=0,maxi,d;
vector<l> v[100000];///Bucket-urile facute cu vector pentru eficienta

///Functie de sortare descrescatoare
inline bool desc(l a,l b){
    return a>b;
}

int main(){
     fin>>n;
     for(int i=1;i<=n;i++){
        fin>>x;
        v[x/1000].push_back(x);
        ///Maximul pentru eficienta
        maxi=max(maxi,x/1000);
     }
     fin>>d;
     ///Descrescator
     if(d){
        for(int i=maxi;i>=0;i--){
            if(!v[i].empty()){
                sort(v[i].begin(),v[i].end(),desc);
                for(l x:v[i]){
                    fout<<x<<" ";
                    c++;
                }
            }
            if(c==n){
                return 0;
            }
        }
     }
     ///Crescator
     else {
        for(int i=0;i<=maxi;i++){
            if(!v[i].empty()){
                sort(v[i].begin(),v[i].end());
                for(l x:v[i]){
                    fout<<x<<" ";
                    c++;
                }
            }
            if(c==n){
                return 0;
            }
        }
     }
     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 #2720 BucketSort

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2720 BucketSort 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!