Sortări în structuri de date

Metodele de sortare cele mai des folosite pot fi clasificate în doua

categorii: METODE DIRECTE si METODE AVANSATE.

METODELE DIRECTE se bazeazã pe algoritmi de dificultate redusa, usor de gãsit si de înteles. Metodele directe pe care le vom lua în considerare sunt sortarea prin selectie (SelectSort) si sortarea cu bule (BubbleSort).

METODELE AVANSATE se bazeaza pe algoritmi putin mai complicati, dar care nu necesitã cunostinte avansate de algoritmica. Cateva din cele mai cunoscute sunt sortarea rapida (QuickSort), sortarea prin interclasare (MergeSort) si sortarea cu ansamble (HeapSort).

Se considera un set finit de obiecte, fiecare avand asociata o caracteristica, numita CHEIE, care ia valori intr-o multime pe care este definita o relatie de ordine.

SORTAREA este procesul prin care elementele setului sunt rearanjate astfel incat cheile lor sa se afle intr-o anumita ordine.

Consideram setul de valori intregi: (5,8,3,1,6). In acest caz cheia de sortare coincide cu valoarea elementului. Prin sortare crescatoare se obtine setul (1,3,5,6,8) iar prin sortare descrescatoare se obtine (8,6,5,3,1).

Aplicatia creata in Microsoft Visual C++ 6.0, realizeaza diferite modalitati de sortare a urmatoarelor structuri de date:

- Vector;

- Matrice;

- Lista simplu inlantuita;

- Lista dublu inlantuita;

Fisierul proiectSD.cpp reprezinta codul sursa al aplicatiei.

In momentul in care utilizatorul ruleaza aplicatia, acestuia ii sunt afisate urmatoarele optiuni:

- Sortarea unui vector, ce urmeaza sa fie introdus de la tastatura, prin metoda bulelor;

- Sortarea unui vector, ce urmeaza sa fie introdus de la tastatura, prin metoda selectiei;

- Sortarea unei linii a unei matrice ce urmeaza sa fie introdusa de la tastatura;

- Sortarea unei coloane a unei matrice ce urmeaza sa fie introdusa de la tastatura;

- Sortarea linilor unei matrice in functie de suma acestora;

- Sortarea coloanelor unei matrice in functie de suma acestora;

- Sortarea unei liste simple ce urmeaza sa fie introdusa de la tastatura;

- Sortarea unei liste dublu inlantuite ce urmeaza sa fie introdusa de la tastatura;

Selectarea optiunilor se face pe baza apasarii unei taste corespunzatoare fiecarei optiuni. Odata apasata tasta corespunzatore se vor rula, intr-o ordinea stabilita, subprogramele ce sunt necesare executarii optiunii dorite.

La sfarsitul executiei uneia dintre optiuni utilizatorul va fii intrebat daca doreste revenirea la meniul principal. In cazul in care utilizatorul nu doreste acest lucru programul se va inchide.

In principal pentru realizarea celor 8 tipuri de sortari prezentate s-au folosit metodele de sortare prin selectii si prin metoda bulelor.

Aceste 2 metode sunt prezentate mai jos:

SORTARE prin METODA BULELOR

Prezentarea metodei

Se parcurge vectorul, interschimband cheile adiacente daca este cazul. Atunci cand in urma unei asemenea treceri nu s-a mai facut nici o interschimbare inseamna ca vectorul este sortat.

La prima parcurgere cheia de valoare maxima migreaza in ultima pozitie. La a doua parcurgere cheia cu valoare imediat mai mica va ocupa penultima pozitie, s.a.m.d.