Aceasta e o versiune anterioară a paginii.
Propunem studierea următorilor algoritmi de sortare:
Numim sortare orice aşezare(sau - mai clar - reaşezare) a unor elemente date în aşa fel încât, după aşezare, să existe o ordine completă în funcţie de un atribut(numit cheie) al elementelor.
Pentru a exista o ordine completă, trebuie să alegem o relaţie pe care vrem sa o impunem. Dacă relaţia este valabilă între oricare două elemente pentru care primul element este aşezat la stânga celui de-al doilea, atunci avem o ordine completă.
Exemplu: dacă alegem drept cheie un atribut număr întreg şi relaţia mai mic sau egal(⇐), obţinem ordinea crescătoare.
Vom descrie un algoritm de sortare prin:
Folosim notaţia O(n) pentru a indica:
Fiecare algoritm se bazează pe o metodă de sortare:
Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de sortare, dar cu un algoritm mai simplu.
fiind comparate elementele alăturate a[i] si a[i+1]. Dacă vor fi găsite 2 elemente neordonate, valorile lor vor fi interschimbate.
elemente neordonate.
//sortare descrescatoare void bubble(int a[],int n) { int i,schimbat,aux; do { schimbat = 0; // parcurgem vectorul for(i = 0; i < n-1; i++) { // daca valoarea i din vectorul a este mai mica decat cea de pe pozitia i+1 if (a[i] < a[i+1]) { // interschimbare aux = a[i]; a[i] = a[i+1]; a[i+1] = aux; schimbat = 1; } } } while(schimbat); }
Acest algoritm selectează, la fiecare pas i, cel mai mic element din vectorul nesortat(de la poziţia i până la n).Valoarea minimă găsită la pasul i este pusă în vector la poziţia i,facându-se intereschimbarea cu poziţia actuală a minimului.Nu este un algoritm indicat pentru vectorii mari, în majoritatea cazurilor oferind rezultate mai slabe decât insertion sort şi bubble sort.
void selectionSort(int a[],int n) { int i,j,aux,min,minPoz; for(i = 0; i < n - 1;i++) { minPoz = i; min = a[i]; for(j = i + 1;j < n;j++) //selectam minimul //din vectorul ramas( de la i+1 la n) { if(min > a[j]) //sortare crescatoare { minPoz = j; //pozitia elementului minim min = a[j]; } } aux = a[i] ; a[i] = a[minPoz]; //interschimbare a[minPoz] = aux; } }
Spre deosebire de alţi algoritmi de sortare, sortarea prin inserţie este folosită destul de des pentru sortarea tablourilor cu număr mic de elemente. De exemplu, poate fi folosit pentru a îmbunătăţi rutina de sortare rapidă.
imaginar în două părţi - o parte sortată şi o parte nesortată. La început, partea sortată conţine primul element al tabloului şi partea nesortată conţine restul tabloului.
void insertionSort(int a[], int n) { int i, j, aux; for (i = 1; i < n; i++) { j = i; while (j > 0 && a[j - 1] > a[j]) { //cautam pozitia pe care sa mutam a[i] aux = a[j]; //interschimbare a[j] = a[j - 1]; a[--j] = aux; } } }
În cazul sortării prin interclasare, vectorii care se interclasează sunt două secvenţe ordonate din acelaşi vector. Sortarea prin interclasare utilizează metoda Divide et Impera:
ordonată la un moment dat şi interclasată cu o altă secvenţă din vector corespunzătoare.
void mergeSort(int a[],int st, int m, int dr) { int b[100]; int i, j, k; i = 0; j = st; // copiem prima jumatate a vectorului a in b while (j <= m) b[i++] = a[j++]; i = 0; k = st; // copiem inapoi cel mai mare element la fiecare pas while (k < j && j <= dr) if (b[i] <= a[j]) a[k++] = b[i++]; else a[k++] = a[j++]; // copiem elementele ramase daca mai exista while (k < j) a[k++] = b[i++]; } void merge(int a[],int st, int dr) { if (st < dr) { int m = (st+dr)/2; merge(a,st, m); merge(a,m+1, dr); mergeSort(a,st, m, dr); } }
Quick Sort este unul dintre cei mai rapizi şi mai utilizaţi algoritmi de sortare până în acest moment,bazându-se pe tehnica „Divide et impera“.Deşi cazul cel mai nefavorabil este O(N^2), în practică, QuickSort oferă rezultate mai bune decât restul algoritmilor de sortare din clasa „O(N log N)“.
Algoritmul se bazează pe următorii paşi:
void qSort(int a[],int st,int dr) { int temp,min,max,mijl; mijl = a[st+(dr-st)/2]; //luam mijlocul intervalului min = st; max = dr; do { while(a[min] < mijl) min++; while(a[max] > mijl) max--; if(min <= max) //interschimbare { temp = a[min]; a[min++] = a[max]; a[max--] = temp; } }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr //cand numai avem ce face schimbam intervalul if(st < max) qSort(a,st,max); //crescator if(dr > min) qSort(a,min,dr); //crescator }
E0. Alegeţi un algoritm A(dintre Bubble, Insertion şi Selection) şi un algoritm B(dintre Merge şi Quick). Introduceţi nişte variabile globale cu care să contorizaţi numărul de comparaţii pentru algoritmii A şi B. Comparaţi rezultatele pentru un vector de întregi de lungime n = 20.
E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare.
E2. Implementaţi un algoritm(dintre Merge şi Quick) pentru sortarea unui vector de structuri, unde fiecare structură reprezintă un moment de timp(int ora,min,sec).
E3. Se dă un vector de n întregi, iar toate valorile din vector sunt între 0 şi 1000. Sortaţi vectorul în timp O(n).
Puteţi utiliza următorul model pentru exerciţiile propuse: scheletsortare.zip
Pentru acest laborator puteți descărca scheletul de cod de aici. Descărcați arhiva și dezarhivați-o.
Puteti folosi utilitarul wget
pentru descarcare si utilitarul unzip
pentru dezarhivare.
wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab8_sortari-skel.zip
unzip lab8_sortari-skel.zip
Pentru compilare folositi comanda make
. Pentru rulare puteti folosi comanda make run
sau ./sort
.