BucketSort

Sortarea fără comparaţii BucketSort (sortare cu găleţi)

Informaţii generale:

Această metodă este numită şi “sortare în recipiente (găleţi)”.

Ideea metodei este ilustrată de exemplul următor:

-să presupunem că vrem să sortăm un pachet de 52 de cărţi de joc, având ca relaţie de ordine binecunoscuta relaţie A<2<3<…<10<J<Q<K, iar pentru culori relaţia ♣<♦<♥<♠. Aşadar, o carte precede altă carte dacă, fie culoarea sa este mai mică decât culoarea celeilalte, fie culoarea este aceeaşi cu a celeilalte, însă valoarea este mai mică. Deci relaţia completă este:

A♣<2♣<…<K♣<A♦<…<K♦<A♥<… <K♥<A♠<… <K♠

-cărţile se pot sorta după oricare din metodele prezentate anterior, însă jucătorii folosesc în practică următoarea tehnică: mai întâi împart cărţile în patru teancuri, după culoare, pe care le ordonează după valoare. Apoi aşează în ordine, după culoare, cele patru teancuri. Există şi o metodă mai simplă: se împart cărţile în 13 teancuri, corespunzătoare celor 13 valori. Apoi se strâng la un loc cărţile, aşezând mai întâi aşii, apoi 2 , etc. Se prelucrează din nou teancul, începând cu capătul aşilor, împărţind cărţile în patru grupe, de data aceasta după culori. Adunând la sfârşit cărţile, luând grupele în ordinea cerută ♣,♦,♥,♠, se obţin cărţile în ordinea dorită.

Algoritmul este corect, deoarece se parcurg cele două etape distincte de aşezare a cărţilor la locul lor, după valoare, apoi după culoare.

Pentru a aplica acest algoritm numerelor, se consideră că mulţimea valorilor de sortat se află distribuită uniform pe intervalul de valori [0,1). Dacă, în practică, este necesară sortarea unor valori diferite A,B≥1, A≥B, atunci şi ,1. Deci se vor sorta inversele numerelor date, urmând ca pentru a regăsi ordinea cerută să se parcurgă descrescător inversele ordonate.

Prezentarea algoritmului:

Pentru a sorta un vector cu n elemente, având valori uniform distribuite în intervalul[0,1), se împarte intervalul de lucru [0,1) în n segmente (găleţi). Se distribuie în fiecare găleată valorile din vector corespunzătoare(găleţile se vor implementa sub formă de liste înlănţuite). Cum numerele de sortat sunt uniform distribuite, rezultă că în fiecare găleată se va regăsi aproximativ acelaşi volum de numere pentru sortat. Se sortează fiecare găleată, apoi se reunesc, în ordine, găleţile sortate. Deoarece cel mai mic număr dintr-o găleată superioară este mai mare decât oricare număr din găleata inferioară, reunirea găleţilor este suficientă pentru ordonarea totală a valorilor date.

Exemplu: Fie vectorul: 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68.

Se vor construi următoarele liste:

0	X
1	P1	→	0.12	P11	→	0.17	X
2	P2	→	0.21	P21	→	0.23	P22	→	0.26	X
3	P3	→	0.39	X
4	X
5	X
6	P4	→	0.68	X
7	P5	→	0.72	P51	→	0.78	X
8	X
9	P6	→	0.98	X

Observaţie:

Se va folosi un număr de găleţi egal cu numărul elementelor de sortat.
Acest algoritm de sortare este paralel, secvenţele de cod pot fi executate pe mai multe procesoare şi apoi sunt „reunite” pentru a obţine rezultatul corect.

Varianta pseudocod a algoritmului:

n←lungime(x);

pentru i ←1, n execută

inserează x[i] în lista GAL [parte întreagă(n*x[i])]

pentru i ←0, n - 1 executa
sortează lista GAL[i] folosind sortarea prin inserţie
concatenează în ordine listele GAL [0] , GAL[1] , …,GAL[n - 1]

Observaţie:Găleata i păstrează valorile din intervalul [i/n, (i+1)/n].

Pentru a analiza timpul de execuţie, să observam mai întâi că toate liniile algoritmului, cu excepţia liniei 5, necesită, în cel mai defavorabil caz, timpul O(n). Timpul total pentru a examina în linia 5 toate grupele este O(n) şi, astfel, singura parte interesantă a analizei este timpul consumat de sortările prin inserţie din linia 5.

Se presupune cunoscută complexitatea metodei de sortare prin inserţie: O(n²). Cum această sortare se aplică pentru fiecare găleată în parte, fie n_inumărul elementelor din găleata GAL[i]. Atunci, complexitatea sortării galeţii GAL[i] este C_i=O(n_i²). Dar elementele pentru aplicarea BucketSort sunt cât mai uniform distribuite în intervalul de lucru. Rezultă că probabilitatea p ca un element oarecare sa se afle în găleata GAL[i] este 1/n. Deci, probabilitatea că n_i=k are o distribuţie binomială şi deci variaţia lui ni este 1-1/n. Deci timpul aşteptat de sortare a tuturor elementelor din toate subintervalele (adică complexitatea sortării prin inserţie este în acest caz O(n). Rezultă astfel complexitatea întregului algoritm: O(n).

Implementare C++:

# include <conio.h>

#include <iostream.h>

float x[100];

struct nod {

float inf;

nod* urm;} *gal[100],*ultim[100], *nou, *p, *q;

int n,i,j,k;

void main(){

cout<<”Introduceti n:”; cin>>n;

for(i=0;i<n;i++){

cout<<”Introduceti x[”<<i<<”]=”; cin>>x[i];

cout<<endl;}

for(i=0;i<n;i++) gal[i]=null;

for (i=0;i<n;i++) {

nou=new nod; nou->inf=x[i];

j=(int)(x[i]*n); //adaug x[i] in gal[j]

if(gal[j]==null){gal[j]=nou;nou->urm=null;ultim[j]=nou}; //lista era goală

else

if (x[i]>ultim[j]->inf){ultim[j]->urm=nou;

nou->urm=null;ultim[j]=nou;};

//x[i] e cel mai mare din găleata j, e aşezat ultimul

else

//x[i] se inserează pe locul lui în găleata j

{p=gal[j];

while(p->inf<x[i]) {q=p;p=p->urm;};

//inserez nou între q şi p

q->urm=nou; nou->urm=p;};

k=0; //reconstruiesc vectorul x[n] ordonat

for(j=0;j<n;j++)

if(gal[j]!=null){

p=gal[j];

while(p!=null){x[k]=p->inf;k++;p=p->urm}

}

for(i=0;i<n;i++) cout<<x[i]<<” ”;

}

Implementare Pascal:

program bucketsort;

type nod=record

inf:real;

urm:^nod;

end;

var x:array[1..100] of real;

gal,ultim:array[1..100] of ^nod;

nou, p, q:^nod;

n,i,j,k:integer;

begin

write(’Introduceti n:’); readln(n);

for i:=1 to n do

begin

write(’Introduceti x[’, i, ’]= ’); readln(x[i]);

end;

for i:=1 to n do gal[i]:=nil;

for i:=1 to n do

begin

new (nou); nou^.inf:=x[i];

j:=int(x[i]*n); {adaug x[i] in gal[j]}

if gal[j]=nil then {lista era goală}

begin

gal[j]:=nou;nou^.urm:=nil;ultim[j]:=nou

end

else

if x[i]>ultim[j]^.inf then

{x[i] e cel mai mare din găleata j}

begin

ultim[j]^.urm:=nou; nou^.urm:=nil; ultim[j]:=nou

end;

else {x[i] se pune pe locul lui în găleata j}

begin

p:=gal[j];

while p^.inf<x[i] do

begin

q:=p;p:=p^.urm;

end; {inserez nou între q şi p}

q^.urm:=nou; nou^.urm:=p;

end;

k:=1; {reconstruiesc vectorul x[n] ordonat}

for j:=1 to n do

if gal[j]<>nil then

begin

p:=gal[j];

while p<>nil do

begin x[k]:=p^.inf;k++;p:=p^.urm end;

end;

for i:=1 to n do write(x[i], ’ ’);

end.

Mergi la pagina METODE DE SORTARE

Aplicaţii

Aplicaţie1: În fişierul înălţime.in sunt notate numele, prenumele şi înălţimea pacienţilor unui doctor (având valori cuprinse între 1,00m şi 1,99m). Să se afişeze pacienţii ordonaţi după înălţime.

Observaţie: Reamintesc că am considerat valorile de sortat uniform distribuite pe intervalul [0,1).

Program C++:

#include <conio.h>

#include <iostream.h>

#include <fstream.h>

ifstream f(”inaltime.in”);

struct nod {

char nume[20], prenume[20];

float inalt;

nod* urm;} *gal[100],*ultim[100], *nou, *p, *q;

float x[100];int n,i,j,k;

void main(){

f>>n;

for(i=0;i<n;i++)

cin>>x[i].nume>>x[i].prenume>>x[i].inalt;

for (i=0;i<n;i++) gal[i]=null;

for (i=0;i<n;i++) {

nou=new nod;

nou->nume=x[i].nume;

nou->prenume=x[i].prenume;

nou->inalt=x[i].inalt;

j=(int)((1-x[i].inalt)*n);//adaug x[i] in gal[j]

if(gal[j]==null){//lista era goală

gal[j]=nou;nou->urm=null;

ultim[j]=nou};

else

if (x[i].inalt>ultim[j]->inalt){//x[i] e aşezat ultimul

ultim[j]->urm=nou;nou->urm=null;ultim[j]=nou;};

else //x[i] se inserează pe locul lui în găleata j

{p=gal[j];

while(p->inalt<x[i].inalt){q=p;p=p->urm;}; //inserez nou între q şi p

q->urm=nou; nou->urm=p;};

k=0; //reconstruiesc vectorul x[n] ordonat

for(j=0;j<n;j++)

if(gal[j]!=null){

p=gal[j];

while(p!=null){

x[k].nume=p->nume;

x[k].prenume=p->prenume;

x[k].inalt=p->inalt;

k++;p=p->urm}

}

for(i=0;i<n;i++)

cout<<x[i].nume<<” ”<< x[i].prenume<<” ” x[i].inalt<<endl;

f.close();}

Program Pascal:

PROGRAM BucketSort1;

TYPE nod=RECORD

nume, prenume;STRING[20]; inalt:REAL;

urm:^nod;END;

VAR x:ARRAY[1..100] OF REAL;

gal,ultim:ARRAY[1..100] OF ^nod;

nou, p, q:^nod;

n,i,j,k:integer; f:TEXT;

BEGIN

ASSIGN (f, ’inaltime.txt’);

RESET(f); READ(f,n);

FOR i:= 1 TO n DO READ (f, x[i].nume, x[i].prenume, x[i].inalt);

FOR i:=1 TO n DO gal[i]:=NIL;

FOR i:=1 TO n DO

BEGIN

NEW (nou); nou^.nume:=x[i].nume;nou^.prenume:=x[i].prenume; nou^.inalt:=x[i].inalt;

j:=INT((1-x[i].inalt)*n); {adaug x[i] in gal[j]}

IF gal[j]=NIL THEN BEGIN {lista era goală}

gal[j]:=nou;nou^.urm:=nil;ultim[j]:=nou; END

ELSE

IF x[i].inalt>ultim[j]^.inalt THEN BEGIN {x[i] e cel mai mare din gal[j]}

ultim[j]^.urm:=nou;nou^.urm:=nil;ultim[j]:=nou; END;

ELSE BEGIN {x[i] se pune pe locul lui în găleata j}

p:=gal[j];

WHILE p^.inf<x[i] DO BEGIN

q:=p;p:=p^.urm;END; {inserez nou între q şi p}

q^.urm:=nou; nou^.urm:=p;END;

k:=1; {reconstruiesc vectorul x[n] ordonat}

FOR j:=1 TO n DO IF gal[j]<>nil THEN BEGIN

p:=gal[j];

WHILE p<>nil DO BEGIN x[k].nume:=p^.nume; x[k].prenume:=p^.prenume; x[k].inalt:=p^.inalt; k:=k+1; p:=p^.urm END;

END;

FOR i:=1 TO n DO WRITELN(x[i].nume, ’ ’, x[i].prenume, ’ ’ x[i].inalt);

END.

Mergi la pagina METODE DE SORTARE