Algoritmi fundamentali de sortare

ALGORITMI FUNDAMENTALI DE SORTARE

Continutul lucrarii

In 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 in ordonarea crescatoare sau descrescatoare a elementelor unui vector A =(a₀, a₁, , a_n-1). In practica, problema se intalneste sub forma sortarii unor articole dupa cheie, cheia fiind un camp din articol.

Sortarea prin numarare

Metoda sortarii prin numarare consta in gasirea pentru fiecare element a[i], a numarului de elemente din vector, mai mici ca el. Numerele obtinute sunt memorate intr-un vector c; elementele vectorului de sortat a, sunt initial atribuite vectorului b. Pe baza vectorului c, elementele lui b vor fi aranjate in vectorul a.

Dezavantajul metodei consta in utilizarea a doi vectori de lucru.

Timpul de prelucrare este de ordinul O(n²). In programul prezentat la paragraful 2.6., functia sort_numarare reda algoritmul de mai sus.

Sortarea prin inserare

Sortarea prin inserare consta in urmatoarele:

Fie secventa a₀ < a₁ < a₂ < a_j-1.

Inserarea elementului a_j in aceasta secventa consta in compararea lui a_j cu a_j-1, a_j-2 pana cand se ajunge la a_i < a_j; se insereaza a_j dupa a_i, cu mentiunea ca in prealabil elementele a_j-1, a_j-2, , a_i+1 au fost deplasate spre dreapta cu o pozitie. Metoda care procedeaza intocmai se numeste inserare directa.

Metoda inserarii binare consta in cautarea binara a locului unde trebuie inserat elementul a_j, avand in vedere ca secventa a₀, a₁, , a_j-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:

a₀, a_h, a_2h, .

a₁, a_1+h, a_1+2h, .

a_h, a_2h, a_3h, .

h este numit increment.

Metoda shell consta in alegerea unui numar de k incrementi

h₁ > h₂ > h₃ > > h_k = 1

si de a face o h₁ - sortare, urmata de o h₂ - sortare s. a. m. d., in final o 1 - sortare.

Performatele metodei sunt strans legate de alegerea incrementilor.

In 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 in cadrul metodei de inserare directa este de ordinul O(n²), iar al metodei shell de ordinul O(n *lnn). De asemenea timpul de prelucrare in cadrul metodei de inserare prin cautare binara este de ordinul O(n *lnn).

Sortarea prin interschimbare

Sortarea prin interschimbare consta in modificari succesive de forma a_i  a_j, pana cand elementele vectorului apar in ordine crescatoare.

Din aceasta categorie fac parte metoda bulelor si metoda quicksort.

Metoda bulelor consta in compararea a_i cu a_i+1; daca ordinea e buna se compara a_i+1 cu a_i+2; daca ordinea nu e buna se interschimba a_i cu a_i+1 si apoi se compara a_i+1 cu a_i+2. Dupa prima parcurgere a vectorului, pe ultima pozitie ajunge elementul avand valoarea cea mai mare, dupa a doua parcurgere ajunge urmatorul element s. a. m. d.

Timpul de prelucrare este de ordinul O(n²).

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 in doi subvectori, astfel incat cel din stanga are toate elementele mai mici decat pivotul, iar cel din dreapta mai mare ca pivotul. Procedeul se reia in subtabloul din stanga si apoi in cel din dreapta s. a. m. d. Procedeul se termina cand se ajunge cu pivotul in extremitatea stanga si respectiv dreapta a tabloului initial.

Timpul de prelucrare a metodei quicksort este de ordinul O(n* lnn).

In 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 in urmatoarele: se afla minimul a_j dintre a₀, a₁, , a_n-1 si se aduce pe pozitia zero in vector prin interschimbarea a₀ cu a_j; apoi procedeul se repeta pentru a₁, a₂, , a_n-1 s. a. m. d.

Timpul de prelucrare este de ordinul O(n²).

In exemplul de la paragraful 2.6., functia sort_selectie reda algoritmul de sortare prin metoda selectiei directe.

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

Sortarea prin interclasare

Metoda sortarii prin interclasare a fost prezentata in cadrul lucrarii nr. 10, drept exemplificare a metodei de elaborare a algoritmilor "Divide et Impera"

Exemplu

In programul de mai jos sunt implementati algoritmii de sortare prezentati in 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 intregi:

Ordonati, fara program, acest sir in ordinea crescatoare a elementelor, folosind cele trei metode 'elementare' de sortare: insertia, metoda bulelor si selectia, aratand la fiecare pas al metodei care este noua configuratie a tabloului. Cate comparatii si cate mutari de elemente au avut loc pentru fiecare metoda? Care metoda este cea mai potrivita pentru acest tablou de intregi? 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 (in cadrul subtabloului din stanga 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 reprezentand 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 inlocuiti varianta prezentata ce foloseste recursivitatea, cu o varianta nerecursiva. Ce variabile trebuiesc initializate, cu ce valori si unde are loc saltul in 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 intr-un sir de lungime n cu elemente intregi, 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), avand semnificatia ca elementul j precede ca ordine elementul k. Sortarea trebuie sa aiba ca rezultat o lista in care oricare element k este devansat de predecesorul sau (sortarea topologica).

Sa se descrie algoritmul care realizeaza urmatoarele actiuni specifice unui examen de admitere:

A    efectuarea calculului mediilor candidatilor la examenul de admitere

A    repartizarea celor admisi dupa optiuni (se considera ca exista m optiuni, fiecare cu un numar dat de candidati admisi) si afisarea listei.

A     afisarea in 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 in considerare a doua), admitandu-se depasirea numarului de locuri in caz de egalitate si dupa acest criteriu.