Documente online.
Zona de administrare documente. Fisierele tale
Am uitat parola x Creaza cont nou
 HomeExploreaza
upload
Upload




ALGORITMI FUNDAMENTALI DE SORTARE

c


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.





Document Info


Accesari: 14628
Apreciat: hand-up

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site


in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate | Termenii si conditii de utilizare




Copyright © Contact (SCRIGROUP Int. 2025 )