Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate stiintaSa fii al doilea inseamna sa fii primul care pierde - Ayrton Senna





Aeronautica Comunicatii Drept Informatica Nutritie Sociologie
Tehnica mecanica




Informatica


Qdidactic » stiinta & tehnica » informatica
Algoritmi fundamentali de sortare



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 =(a0, a1, , an-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(n2). 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 a0 < a1 < a2 < aj-1.

Inserarea elementului aj in aceasta secventa consta in compararea lui aj cu aj-1, aj-2 pana cand se ajunge la ai < aj; se insereaza aj dupa ai, cu mentiunea ca in prealabil elementele aj-1, aj-2, , ai+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 aj, avand in 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 in 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., 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(n2), 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 ai  aj, pana cand elementele vectorului apar in ordine crescatoare.

Din aceasta categorie fac parte metoda bulelor si metoda quicksort.

Metoda bulelor consta in 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 avand 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 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 aj dintre a0, a1, , an-1 si se aduce pe pozitia zero in 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 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.








Contact |- ia legatura cu noi -|
Adauga document |- pune-ti documente online -|
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -|
Copyright © |- 2022 - Toate drepturile rezervate -|

Informatica



Access
Autocad
Baze de date
C
Calculatoare
Catia
Excel
Foxpro
Grafica design
Html
Internet
Java
Linux
Mathcad
Matlab
Oracle
Outlook
Photoshop
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word

Lucrari pe aceeasi tema


Algoritmi fundamentali de sortare
Aplicatii - nnmodel



Ramai informat
Informatia de care ai nevoie
Acces nelimitat la mii de documente, referate, lucrari. Online e mai simplu.

Contribuie si tu!
Adauga online proiectul sau referatul tau.