Metode de sortare
Sortarea reprezinta una dintre cei mai utilizate metode de programare. Are utilizari de la domenii precum matematica ( statistica matematica ), pana la limbi ( realizarea unor dictionare ). De aceea se impune sa gasim cei mai convenabili algoritmi si sa prezentam avantajele si dezavantajele acestora. Ne vom rezuma la cei mai importanti.
Metodele de sortare se clasifica in metode directe si metode avansate.
- Metodele directe se bazeaza„ pe algoritmi de dificultate redusa, usor de gasit si de inteles. Metodele directe pe care le vom lua in considerare sunt sortarea prin selectie ( SelectSort ), sortarea prin insertie ( InsertSort ) si sortarea cu bule ( BubbleSort ).
- Metodele avansate se bazeaza pe algoritmi putin mai complicati, dar care nu necesita unostinte avansate de algoritmica. Cateva din cele mai cunoscute sunt sortarea rapida (QuickSort), sortarea prin interclasare (MergeSort) si sortarea cu micsorarea incrementului( Shell Sort ).
1. Metode directe
1.1 BubbleSort
Acesta metoda se rezuma la a compara fiecare element cu celelalte, facandu-se interschimbarea daca elementul mai mare are indexul mai mic. Este cea mai simpla metode de sortare si nu necesita cunoasterea detaliata a limbajului de programare. Poate fi folosita cu succes de catre incepatori.
1.1 BubbleSort
Acesta metoda se rezuma la a compara fiecare element cu celelalte, facandu-se interschimbarea daca elementul mai mare are indexul mai mic. Este cea mai simpla metode de sortare si nu necesita cunoasterea detaliata a limbajului de programare. Poate fi folosita cu succes de catre incepatori.
- Bubble sort este o metodã de sortare simplã, eficientã pentru un numãr mic de elemente (mai putin de 15), dar nu pentru tabele mari.
- Nu necesitã foate multã memorie, dar este de douã ori mai lentã decât InsertionSort în aproape orice situatie.
- Timpul de executie depinde de input, adicã de ordinea initialã al elementelor.
- Dacã tabela este deja sortatã e nevoie de un singur pas, adicã N-1 comparãri. În cazul cel mai nefavorabil sunt necesare N ×(N-1)/2 comparãri si N × (N-1)/2 interschimbãri.
- Performanta algoritmului în caz general este mai greu de analizat dar este asemãnãtor cazului nefavorabil. Complexitatea timpului al Bubble sortului este O(N2).
BubbleSort nu foloseste alte structuri de date si din aceasta cauza este recomandabil in cazurile cu putine elemente de sortat si in cazul in care memoria este limitata.
1.2 SelectionSort
Selectia directã este una dintre cele mai simple metode de sortare si va lucra foarte bine pentru tabele mici, fiecare element (înregistrare), este mutat cel mult o datã.. Implementarea algoritmului este simplu.Algoritmul presupune ca la fiecare pas “i “ sa se gaseasca elementul minim dintre a[i+1], a[i+2]…a[n] si se interschimba cu a[i].
Se cheltuie cel mai mult timp cu cãutarea elementului minim din partea nesortatã a tabelei.Cãutarea se face de la stânga la dreapta. Pe parcursul fiecãrui pas este necesar o interschimbare, deci numãrul interschimbãrilor pentru N elemente este: N-1.
Selectia directã este una dintre cele mai simple metode de sortare si va lucra foarte bine pentru tabele mici, fiecare element (înregistrare), este mutat cel mult o datã.. Implementarea algoritmului este simplu.Algoritmul presupune ca la fiecare pas “i “ sa se gaseasca elementul minim dintre a[i+1], a[i+2]…a[n] si se interschimba cu a[i].
Se cheltuie cel mai mult timp cu cãutarea elementului minim din partea nesortatã a tabelei.Cãutarea se face de la stânga la dreapta. Pe parcursul fiecãrui pas este necesar o interschimbare, deci numãrul interschimbãrilor pentru N elemente este: N-1.
1.3 InsertionSort
Insertia directã apartine familiei de tehnici de sortare care se bazeazã pe metoda "jucãtorului de bridge". Este un algoritm aproape la fel de simplu ca Selection sort, dar poate mai flexibil. Considerãm elementele A[1]...A[i-1] fiind sortate, inserãm elementul A[i] în locul ce îi revine.
Fiind dat o tabelã A cu N elemente nesortate, parcurgem tabela si le inserãm fiecare element în locul propriu între celelalte elemente considerate sortate. Pentru fiecare i = 2..N , elementele A[1]…A[i] sunt sortate prin inserarea lui A[i] între lista elementelor sortate: A[1]…A[i-1]. Elementele aflate în stânga indexului sunt în ordine sortatã dar nu sunt în pozitia lor finalã. Tabela este sortatã complect când indexul ajunge la capãtul drept al tabelei.
Insertia directã apartine familiei de tehnici de sortare care se bazeazã pe metoda "jucãtorului de bridge". Este un algoritm aproape la fel de simplu ca Selection sort, dar poate mai flexibil. Considerãm elementele A[1]...A[i-1] fiind sortate, inserãm elementul A[i] în locul ce îi revine.
Fiind dat o tabelã A cu N elemente nesortate, parcurgem tabela si le inserãm fiecare element în locul propriu între celelalte elemente considerate sortate. Pentru fiecare i = 2..N , elementele A[1]…A[i] sunt sortate prin inserarea lui A[i] între lista elementelor sortate: A[1]…A[i-1]. Elementele aflate în stânga indexului sunt în ordine sortatã dar nu sunt în pozitia lor finalã. Tabela este sortatã complect când indexul ajunge la capãtul drept al tabelei.
- Insertion sort este un algoritm de sortare simplu, liniar: O(N) pentru tabele care contin N elemente aproape sortate.
- Timpul de executie al algoritmului depinde de numãrul inversãrilor, deci de ordinea initialã al elementelor. În caz general sunt necesare N 2 /4 comparatii si interschimbãri, N 2 /8 deci ordinea magnitudinii este O(N 2).
2. Metode avansate de sortare
2.1 QuickSort
În practicã algoritmul de sortare cel mai rapid este Quicksort numitã sortare rapidã, care foloseste partitionarea ca idee de bazã.
2.1 QuickSort
În practicã algoritmul de sortare cel mai rapid este Quicksort numitã sortare rapidã, care foloseste partitionarea ca idee de bazã.
- Este mai rapidã decât orice metodã de sortare simplã, se executã bine pentru fisiere sau tabele mari, dar ineficient pentru cele mici.
- Strategia de bazã folositã este "divide et impera", pentru cã este mai usor de sortat douã tabele mici, decât una mare.
- Algoritmul este usor de implementat, lucreazã destul de bine în diferite situatii si consumã mai putine resurse decât orice altã metodã de sortare în multe situatii.
- Necesitã numai în jur de NlogN operati în cazul general pentru a sorta N elemente.
Metoda QuickSort presupune gasirea pozitiei finale pe care o ocupa elemenetul de pe prima pozitie comparandu-l cu elementele din cealalta partitie a tabelului, acest algoritm realizandu-se pana cand partitia are 1 element.
Potrivit algoritmului, fiecare element este comparat cu pivoul, adicã operatiunea este de O(N), tabela este divizatã în douã pãrti, fiecare parte este divizatã iarãsi în douã. Dacã fiecare parte este împãrtitã aproximativ în jumãtate, va rezulta log2N împãrtiri. Deci timpul de executie al Quicksortului în caz mediu este de O(N log2 N), iar în caz nefavorabil O(N2) .
Quicksort este o metodã bunã în caz general, dar nu si în caz nefavorabil când este preferabil folosirea a 3 indicii de impartire. Randomizarea este o idee importantã si folositoare, o unealtã generalã pentru a îmbunãtãti algoritmul. Quicksort este sensibil la ordinea datelor de intrare. Nu este o metodã stabilã.
Dezavantajul algoritmului este cã, e recursiv. Necesitã în jur de N 2 de operatii în caz nefavorabil. Este fragil, o simplã gresealã în implementare poate cauza o executare gresitã pentru anumite fisiere.
Potrivit algoritmului, fiecare element este comparat cu pivoul, adicã operatiunea este de O(N), tabela este divizatã în douã pãrti, fiecare parte este divizatã iarãsi în douã. Dacã fiecare parte este împãrtitã aproximativ în jumãtate, va rezulta log2N împãrtiri. Deci timpul de executie al Quicksortului în caz mediu este de O(N log2 N), iar în caz nefavorabil O(N2) .
Quicksort este o metodã bunã în caz general, dar nu si în caz nefavorabil când este preferabil folosirea a 3 indicii de impartire. Randomizarea este o idee importantã si folositoare, o unealtã generalã pentru a îmbunãtãti algoritmul. Quicksort este sensibil la ordinea datelor de intrare. Nu este o metodã stabilã.
Dezavantajul algoritmului este cã, e recursiv. Necesitã în jur de N 2 de operatii în caz nefavorabil. Este fragil, o simplã gresealã în implementare poate cauza o executare gresitã pentru anumite fisiere.
quicksort.cpp | |
File Size: | 0 kb |
File Type: | cpp |
2.2 MergeSort
Algoritmul de sortare prin interclasare se bazeazã pe urmãtoarea idee: pentru a sorta o tabelã cu N elemente îl împãrtim în douã tabele pe care le sortez separat si le intrclasãm. Este o metodã de sortare care foloseste strategia de bazã "divide et impera", conform cãreia problema se descompune în alte douã subprobleme de acelasi tip si dupã rezolvarea lor rezultatele se combinã. Algoritmul sorteazã elementele în ordine crescãtoare.Tabelul se imparte in n/2, dupa aceea tabelele se impart in jumatate, tot asa pana cand tabelele formate au mai putin sau cel mult de k elemente(in cazul nostru k=2-este cel mai usor sa compari 2 elemente).
Algoritmul de sortare prin interclasare se bazeazã pe urmãtoarea idee: pentru a sorta o tabelã cu N elemente îl împãrtim în douã tabele pe care le sortez separat si le intrclasãm. Este o metodã de sortare care foloseste strategia de bazã "divide et impera", conform cãreia problema se descompune în alte douã subprobleme de acelasi tip si dupã rezolvarea lor rezultatele se combinã. Algoritmul sorteazã elementele în ordine crescãtoare.Tabelul se imparte in n/2, dupa aceea tabelele se impart in jumatate, tot asa pana cand tabelele formate au mai putin sau cel mult de k elemente(in cazul nostru k=2-este cel mai usor sa compari 2 elemente).
mergesort.cpp | |
File Size: | 0 kb |
File Type: | cpp |