ALGORITMI FUNDAMENTALI DE SORTARE
Continutul lucrarii
Īn lucrare sunt prezentati algoritmii de sortare prin numarare, prin inserare (directa si shellsort), prin interschimbare (metoda bulelor si quicksort), prin selectie si interclasare.
Consideratii teoretice
Sortarea consta īn ordonarea crescatoare sau descrescatoare a elementelor unui vector A =(a0, a1, ..., an-1). Īn practica, problema se īntālneste sub forma sortarii unor articole dupa cheie, cheia fiind un cāmp din articol.
Sortarea prin numarare
Metoda sortarii prin numarare consta īn gasirea pentru fiecare element a[i], a numarului de elemente din vector, mai mici ca el. Numerele obtinute sunt memorate īnt 626e45g r-un vector c; elementele vectorului de sortat a, sunt initial atribuite vectorului b. Pe baza vectorului c, elementele lui b vor fi aranjate īn vectorul a.
Dezavantajul metodei consta īn utilizarea a doi vectori de lucru.
Timpul de prelucrare este de ordinul O(n2). Īn programul prezentat la paragraful 2.6., functia sort_numarare reda algoritmul de mai sus.
Sortarea prin inserare
Sortarea prin inserare consta īn urmatoarele:
Fie secventa a0 < a1 < a2 ... < aj-1.
Inserarea elementului aj īn aceasta secventa consta īn compararea lui aj cu aj-1, aj-2 ... pāna cānd se ajunge la ai < aj; se insereaza aj dupa ai, cu mentiunea ca īn prealabil elementele aj-1, aj-2, ..., ai+1 au fost deplasate spre dreapta cu o pozitie. Metoda care procedeaza īntocmai se numeste inserare directa.
Metoda inserarii binare consta īn cautarea binara a locului unde trebuie inserat elementul aj, avānd īn vedere ca secventa a0, a1, ..., aj-1 este ordonata crescator.
Tot din categoria inserarii face parte si metoda shell. Pentru a explica metoda se introduce notiunea de h-sortare. Numim h-sortare, sortarea prin inserare directa a urmatoarelor secvente:
a0, ah, a2h, ....
a1, a1+h, a1+2h, ....
ah, a2h, a3h, ....
h este numit increment.
Metoda shell consta īn alegerea unui numar de k incrementi
h1 > h2 > h3 > ... > hk = 1
si de a face o h1 - sortare, urmata de o h2 - sortare s. a. m. d., īn final o 1 - sortare.
Performatele metodei sunt strāns legate de alegerea incrementilor.
Īn exemplul din paragraful 2.6., functia sort_inserare_directa reda algoritmul de inserare directa, iar functia shell_sort reda algoritmul metodei shell.
Timpul de prelucrare īn cadrul metodei de inserare directa este de ordinul O(n2), iar al metodei shell de ordinul O(n *lnn). De asemenea timpul de prelucrare īn cadrul metodei de inserare prin cautare binara este de ordinul O(n *lnn).
Sortarea prin interschimbare
Sortarea prin interschimbare consta īn modificari succesive de forma ai aj, pāna cānd elementele vectorului apar īn ordine crescatoare.
Din aceasta categorie fac parte metoda bulelor si metoda quicksort.
Metoda bulelor consta īn compararea ai cu ai+1; daca ordinea e buna se compara ai+1 cu ai+2; daca ordinea nu e buna se interschimba ai cu ai+1 si apoi se compara ai+1 cu ai+2. Dupa prima parcurgere a vectorului, pe ultima pozitie ajunge elementul avānd valoarea cea mai mare, dupa a doua parcurgere ajunge urmatorul element s. a. m. d.
Timpul de prelucrare este de ordinul O(n2).
Sortarea rapida quicksort a fost creata de Hoare si foloseste metoda "Divide Et Impera".
Principiul metodei este urmatorul: se selecteaza un element din tablou numit pivot si se rearanjeaza vectorul īn doi subvectori, astfel īncāt cel din stānga are toate elementele mai mici decāt pivotul, iar cel din dreapta mai mare ca pivotul. Procedeul se reia īn subtabloul din stānga si apoi īn cel din dreapta s. a. m. d. Procedeul se termina cānd se ajunge cu pivotul īn extremitatea stānga si respectiv dreapta a tabloului initial.
Timpul de prelucrare a metodei quicksort este de ordinul O(n* lnn).
Īn exemplul de la paragraful 2.6., functia sort_metoda_bulelor reda algoritmul de sortari prin metoda bulelor, iar functiile quicksort si quick redau algoritmul sortarii prin metoda quicksort.
Sortarea prin selectie
Sortarea prin selectie directa consta īn urmatoarele: se afla minimul aj dintre a0, a1, ..., an-1 si se aduce pe pozitia zero īn vector prin interschimbarea a0 cu aj; apoi procedeul se repeta pentru a1, a2, ..., an-1 s. a. m. d.
Timpul de prelucrare este de ordinul O(n2).
In exemplul de la paragraful 2.6., functia sort_selectie reda algoritmul de sortare prin metoda selectiei directe.
Sortarea prin interclasare
Metoda sortarii prin interclasare a fost prezentata īn cadrul lucrarii nr. 10, drept exemplificare a metodei de elaborare a algoritmilor "Divide et Impera"
Exemplu
Īn programul de mai jos sunt implementati algoritmii de sortare prezentati īn paragrafele 2.1. -2.5.
#include <stdio.h>
#include <conio.h>
#define nmax 100
/* ALGORITMI DE SORTARE */
void citire_vector(int n,float a[nmax],float b[nmax])
/* CITIRE ELEMENTE VECTOR */
void reconstituire(int n,float a[nmax],float b[nmax])
/* RECONSTITUIREA INITIALA A VECTORULUI a */
void afisare(int n,float a[nmax])
/* AFISARE VECTOR */
void sort_numarare(int n,float a[nmax])
/* SORTAREA PRIN NUMARARE */
/* numarare */
for(j=1;j<n;j++)
for(i=0;i<=j-1;i++)
if(a[i]<a[j]) c[j]++;
else c[i]++;
/* rearanjare vector a */
for(i=0;i<n;i++)
a[c[i]]=b[i];
void sort_inserare_directa(int n,float a[nmax])
/* SORTARE PRIN INSERARE DIRECTA */
a[i+1]=x;
}
}
void shell_sort(int n,float a[nmax])
/* SORTAREA PRIN METODA SHELL */
;
a[j]=x;
}
}
}
void sort_metoda_bulelor(int n,float a[nmax])
/* SORTAREA PRIN INTERSCHIMBARE-METODA BULELOR */
;
}while(gata==0);
}
void quick(int prim,int ultim,float a[nmax])
;
}while(i<=j);
if(prim<j) quick(prim,j,a);
if(i<ultim) quick(i,ultim,a);
}
void quicksort(int n,float a[nmax])
/* SORTAREA RAPIDA QUICKSORT */
void sort_selectie(int n,float a[nmax])
/* SORTAREA PRIN SELECTIE */
a[poz]=a[i];a[i]=x;
}
void main(void)
Mersul lucrarii
Fie tabloul de īntregi:
Ordonati, fara program, acest sir īn ordinea crescatoare a elementelor, folosind cele trei metode 'elementare' de sortare: insertia, metoda bulelor si selectia, aratānd la fiecare pas al metodei care este noua configuratie a tabloului. Cāte comparatii si cāte mutari de elemente au avut loc pentru fiecare metoda? Care metoda este cea mai potrivita pentru acest tablou de īntregi? Care aranjare a tabloului ar fi fost cea mai defavorabila?
Descrieti algoritmul de sortare prin inserare, la care modificati cautarea liniara cu o cautare binara (īn cadrul subtabloului din stānga elementului curent). Calculati si pentru acest nou algoritm (numit sortare prin insertie cu cautare binara) numarul de pasi, numarul de comparatii si mutari ale elementelor din lista pentru exemplul de la problema 3.1. Devine acest algoritm mai performant?
Pentru tabloul de elemente reale:
aplicati metodele de ordonare shell-sort si quick-sort, pentru fiecare pas reprezentānd noua configuratie a tabloului. Numarati comparatiile si mutarile de elemente pe care le-ati efectuat. Care algoritm este mai eficient pentru acest tablou?
Analizati algoritmul de sortare quick-sort si īnlocuiti varianta prezentata ce foloseste recursivitatea, cu o varianta nerecursiva. Ce variabile trebuiesc initializate, cu ce valori si unde are loc saltul īn program pentru a se elimina apelul recursiv?
Care algoritm dintre cei prezentati are nevoie de spatiu de memorie cel mai mare?
Scrieti un algoritm care combina algoritmii de sortare quick-sort pentru obtinerea de partitii nesortate de lungime m, apoi utilizati insertia directa pentru terminarea sortarii.
Adaptati algoritmul quick-sort pentru a determina īntr-un sir de lungime n cu elemente īntregi, al m-lea mai mic element .
Sa se sorteze un numar de n elemente numerotate de la 1 la n caracterizate prin anumite relatii de precedenta notate (j, k), avānd semnificatia ca elementul j precede ca ordine elementul k. Sortarea trebuie sa aiba ca rezultat o lista īn care oricare element k este devansat de predecesorul sau (sortarea topologica).
Sa se descrie algoritmul care realizeaza urmatoarele actiuni specifice unui examen de admitere:
efectuarea calculului mediilor candidatilor la examenul de admitere
repartizarea celor admisi dupa optiuni (se considera ca exista m optiuni, fiecare cu un numar dat de candidati admisi) si afisarea listei.
afisarea īn ordinea descrescatoare a mediilor a tuturor candidatilor neadmisi.
Se considera ca examenul consta din doua probe, la medii egale (calculate cu doua zecimale, prin trunchiere), departajarea se face dupa nota la prima proba (daca egalitatea se mentine, se ia īn considerare a doua), admitāndu-se depasirea numarului de locuri īn caz de egalitate si dupa acest criteriu.
|
