Prezentarea algoritmilor de sortare. |
1.Prezentarea algoritmului de sortare. >>>
In domeniul calculatoarelor si al matematicii,
un algoritm de sortare este o metoda prin care se aranjeaza elementele
unui tablou intr-o ordine precisa.Cele mai folosite tipuri de date
in cadrul acestor metode de sortare sunt tipul de ordin numeric si
tipul lexicografic.Eficienta metodelor de sortare este importanta deoarece
se pune un mare accent pe optimizarea altor algoritmi (cum sunt algoritmii
de cautare) care necesitta sortarea tablourilor cu care lucreaza, devenind
astfel mai eficienti; si se foloseste adesea pentru fixarea datelor catre
un rezultat care mai este denumit si iesire.Printr-o iesire se intelege
rezultatul sortarii.Mult mai formal, iesirea trebuie sa indeplineasca
doua conditii:
Conditia 1: Iesirea trebuie sa contina un tablou (sau lista) in
care valorile termenilor sa fie aranjate in ordine crescatoare.Fiecare
element al tabloului nu trebuie sa fie mai mic decat termenul de dinaintea
lui, aceasta conditie fiind valabila pentru toti termenii din tablou.
Conditia 2: Iesirea este o permutare, sau o reordonare a datelor
de la intrare (datele care nu sunt sortate).Prin date de intrare intelegandu-se
valorile termenilor prezenti in tabloul care trebuie sa fie sortat.
La inceputul aparitiei calculatoarelor, problemele
sortarii datelor au atras dupa sine multe studii si cercetari,probabil
datorita complexitatii rezolvarii comportarii eficiente a unui algorim
de sortare, desi initial se parea simplu de rezolvat.De exemplu sortarea
prin interschimbare ("bubble sort") a fost analizata destul de timpuriu,
prin anul 1956.De atunci multe din problemele sortarii s-au rezolvat
prin aparitia altor algoritmi de sortare mult mai eficienti.Algoritmii
de sortare sunt cel mai adesea utilizati in studiul performantei calculatoarelor.
2.Criterii de performanta ale algoritmilor
de sortare. >>>
Algoritmii de sortare sunt cel mai adesea
clasificati dupa urmatoarele criterii:
Complexitatea metodei de sortare (calculelor).
Acest criteriu determinand functionarea algoritmului si a metodelor
proprii de a realiza o sortare.Daca un algoritm realizeaza o sortare
prin procedee complexe el poate avea o comportare avantajoasa, comportare
multumitoare sau o comportate dezavantajoasa.Prin complexitatea metodei
(calcului) se intelege efectuarea operatiilor de comparare a valorii
unui termen oarecare din tabloul de marime n, cu celelelte
n valori ale termenilor prezenti in cadrul aceluiasi
tablou.Pentru algoritmii de sortare eficienti functia de comportare va
fi O(n logn), iar cea mai dezavantajoasa comportare poate fi in
cazul incare functia de comportare este de ?(n2).Comportarea
ideala pentru un algoritm de sortare este O(n).Algoritmii de
sortare care folosesc numai valori abstracte,vor necesita ,in medie,
un numar de ?(n log n) comparatii pentru a realiza o sortare completa.
Complexitatea de sortare a termenilor
cu valori repetate.
Acesta caracteristica este prezenta in general la algorimtii
care realizeaza o sortare interoioara ("pe loc").
Utilizarea memoriei (sau a altor
resurse ale calculatorului).
In particular, unii algoritmi de sortare realizeaza sortari
interioare ("pe loc"), astfel ca sunt necesare numai un numar de O(1)
sau O(log n) locatii de memorie pentru ca si valorile celor mai
indepartati termeni ai tabloului de sortat sa fie memorati.Sunt insa
si alti algoritmi de sortare care desii utilizeaza metoda de memorare
prezentata putin mai sus, necesita si locatii suplimentare de memorie
pentru a putea memora temporar datele.
Recursia.
Exista algoritmi desortare poti fi de tip recursiv, sau nerecursivi,
desii exista algorimi care detin ambele proprietati cum este de exemplu
algoritmul de sortare prin interclasare ("mergesort").
Utilizeaza sau nu
utilizeaza metoda sortarii prin comparare.
Un algoritm de sortare care utilizeaza pe baza metodei de comparare,
testeaza valorile termenilor prezenti intr-un tablou sau lista ce trebuie
sortata comparand doi termni aflati in tablou cum un operator (indiciu)
de comparare,numit adesea si "pivot".
Functionare cu mai multe metode
de sortare.
Sunt unii algoritmi de sortare care au fost dezvoltati in jurul
metodei de sortare al altui algoritm de aceasi categorie.Adica au
rezultat in urma unor imbunatatiri a metodelor de sortare a altor algoritmi
de sortare, insa avand o comportare diferita primind astfel si o denumire
specifica.De exemplu algorimul de sortare prin intershimbare cuprinde
si metoda de sortare "bubblesort" si "quicksort", iar un alt exemplu este
algoritmul de sortare prin selectie care si el cuprinde metoda de sortare
"shakersort" si "heapsort".
Stabilitatea algoritmilor de
sortare.
Un algoritm de sortare se numeste stabil numai daca pastreaza
ordinea relativa a inregistrarilor care au aceeasi valoare.De exemplu,
se presupune existenta unui tablou care trebuie sortat si in care
sunt doi termeni care au valori identice A si B, iar termenul cu valoarea
A este inaintea termenului cu valoarea B.Daca se sorteaza tabloul in
care se afla cei doi termeni A si B aplicand un algoritm de sortare
oarecare, si daca in urma sortarii tabloul va avea valoarea termenului
A ca fiind tot inaintea termenului cu valoare B, atunci algoritmul cu
care s-a efectuat sortarea se poate numi stabil.Cand termenii cu valori
egale sunt indistinctibili, cum sunt datele care detin valori de tip
intreg, stabilitatea nu reprezinta o problema.Iata un nou exemplu: sa
presupunem ca urmatoarele perechi de numere trebuiesc sortate dupa prima
coordonata:
(4 , 1) (3 , 1) (3 , 7) (5 , 6).
In acest caz,in urma sortarii sunt
posibile doua rezultate (iesiri) diferite: un rezultat care pastreaza
ordinea relativa a inregistrarilor termenilor cu valori identice,si un
alt rezultat care nu pastreaza ordinea relativa a inregistrarilor:
(3 , 1) (3 , 7) (4 , 1) (5 , 6) <- ordine pastrata
(3 , 7) (3 , 1) (4 , 1) (5 , 6) <- ordine schimbata.
Algoritmii de sortare nestabili ar
putea schimba ordinea inregistrarilorpentru termenii cu valori identice,
insa algoritmii stabili niciodata nu vor proceda asa.Algoritmii de
sortare caracaterizati ca fiind nestabili, pot fi implementati ca sa
devina stabili.O metoda pentru a realiza aceasta este prin extinderea
artificiala a tabloului de sortat facand loc si cheii de cautat.Procedand
asa comparatiile dintre o pereche de doi termeni care au valori identice
vor fi nevoitisa foloseasca ordinea intrarilor conform ordinii initiale
in care au fost introdusi in tabloul initial.Procedand asa va fi necesar
un spatiu aditional de memorie pentru ca algorimul de sortare sa functineze
corect.
3.Lista algorimilor de sortare. >>>
In tabloul de mai jos n reprezinta
numarul de inregistrari a sortarilor facute, si k este lungimea
valorilor medii.Coloanele Compoartare eficienta, comportare
medie, comportare ineficienta reprezinta complexitatea segventelor(calulelor)
realizate; mentionand ca nu se foloseste k ca termen fix (constant).Coloana
denumita Memorie indica numai spatiul de memorie folosit
de catre tablou, fara memorie suplimentara:
|
Numele sortarii
|
Comportare eficienta
|
Comportare medie
|
Comportare ineficienta
|
Nr. accese la memorie
|
Stabilitate
|
Metoda sortarii
|
Alte observatii
|
|
Sortare interschimbare
|
O(n)
|
--
|
O(n2)
|
O(1)
|
Da
|
Inteschimbare
|
Timpul este cea mai buna varianta
|
|
Sortare selectie
|
O(n2)
|
O(n2)
|
O(n2)
|
O(1)
|
Nu
|
Selectie
|
--
|
|
Sortare insertie |
O(n)
|
O(n + d)
|
O(n2)
|
O(1)
|
Da
|
Insertie
|
d este numarul inversiunilor ->O(n2)
|
|
Sortare insertie cu pas variabil
|
--
|
--
|
O(n1.5)
|
O(1)
|
Nu
|
Insertie
|
--
|
|
Sortare interclasare
|
O(n log n)
|
O(n log n)
|
O(n log n)
|
O(n)
|
Da
|
Interclasare
|
--
|
|
Sortare ansamble
|
O(n log n)
|
O(n log n)
|
O(n log n)
|
O(1)
|
Nu
|
Selectie
|
--
|
|
Sortarea rapida
|
O(n log n)
|
O(n log n)
|
O(n2)
|
O(log n)
|
Nu
|
Segmentare
|
Variantele bune folosest un spatiu O(n)
|
Tabloul de mai jos descrie algoritmii
de sortare care nu folosesc metoda sortarii prin comparare.Astfel dar,ei
nu sunt constransi prin realizare de segvente in timp conform O(n logn).Complexitatea
segventelor algoritmilor de mai jos e reprezentata prin termenul n
care reprezinta numarul de termeni care trebuiesc sortati,k dimensiunea
numarica a valorii termenilor si s dimensiunea folosita pentru
implementare:
|
Numele sortarii
|
Comportare eficienta
|
Comportare medie
|
Comportare ineficienta
|
Nr. accese la memorie
|
Stabilitate
|
|
Sortarea "Pigeonhole"
|
O(n+2k)
|
O(n+2k)
|
O(n+2k)
|
O(2k)
|
Da
|
|
Sortarea "Bucket"
|
O(n)
|
O(n)
|
O(n)
|
O(2k)
|
Da
|
|
Sortarea "Counting"
|
O(n+2k)
|
O(n+2k)
|
O(n+2k)
|
O(n+2k)
|
Da
|
|
Sortarea "LSD Radix"
|
O(nxk/s)
|
O(nxk/s)
|
O(nxk/s)
|
O(n)
|
Da
|
| Sortarea "MSD Radix"
|
O(nxk/s)
|
O(nxk/s)
|
O(nx(k/s)x2s)
|
O((k/s)x2s)
|
Nu
|
|
Sortarea "Spread"
|
O(n)
|
O(nxk/log(n))
|
O(nx(k - log(n)).5)
|
O(n)
|
Nu
|
Tabloul de mai jos descrie cativa
algoritmi de sortare care sunt neutilizati in timp real, deoarece au
un grad de performanta scazut, sau sunt influentati de conditiile de functionare
a echipamentelor hardware:
|
Numele sortarii
|
Comportare eficientaBest
|
Comportare medie
|
Comporatare ineficienta
|
Nr. acese la memorie
|
Stabilitate
|
Comparatii
|
Alte observatii
|
|
Sortarea "Bogosort"
|
O(n)
|
O(nxn!)
|
Infinit
|
O(1)
|
Nu
|
Da
|
Implementarea Knuth este eficienta.
|
|
Sortarea "Bozo"
|
O(n)
|
O(nxn!)
|
Infinit
|
O(1)
|
Nu
|
Da
|
--
|
|
Sortarea "Stooge"
|
O(n2.71)
|
O(n2.71)
|
O(n2.71)
|
O(1)
|
Nu
|
Da
|
--
|
|
Sortarea "Bead"
|
O(n)
|
O(n)
|
O(n)
|
--
|
Da/Nu
|
Nu
|
Necesita hardware special.
|
|
Sortarea "Pancake"
|
O(n)
|
O(n)
|
O(n)
|
--
|
Nu
|
Da
|
Necesita hardware special.
|
|
Sortarea retelelor
|
O(log n)
|
O(log n)
|
O(log n)
|
--
|
Da
|
Da
|
La 0 necesita un circuit adecvat O(nlog
n)
|
4.Descrierea celor mai utilizati algoritmi de
sortare. >>>
Sortarea prin interschimbare (bubble sort). [Sunt curios...]
Acest algoritm de sortare functioneaza pe o metoda directa si simpla
de sortare a datelor care sunt utilizate in domeniul calculatoarelor.Algoritmulincepe
procedeul de sortarea prin aranjarea termenilor din tabloul ce trebuie
sortat.Astfel ca se va compara primi doi termnei, iar daca s-a constatat
ca valoarea numarica a primului termen este mai mare ca valoarea numarica
a celui de-al doilea termen va avea loc o interschimbare de pozitii: primul
termen va trece pe pozitia pe care se afla al doilea termen in cadrul tasbloului ce
trebuie sortat.Se procedeaza asa si cu restul perechilor de numere din
tablou, pana nu mai este nici o pereche de numere comparata.Acum algoritmul
reia de la inceput compararea perechilor de numere din tabloul si se tot
repeta astfel pana cand nu mai exista nici o neconcordanta intre valorile
termenilor din tablou nedescoperita la ultima trecere (comparare).Desii simplu,
acest algoritm de sortare se comporta eficient si usor de implementat, si
se folosete in mod fregvent in educatie.O varianta de algoritm putin maibun
decat sortarea prin interschimbare este algoritmul de sortare numit "coktail
sort", care functioneaza pe metoda de a inversa criteriul de ordine al termenilor
si efectuarea sortarii prin treceri alternative.Daca "bubble-ul" se utilizeaza
la sortarea unui numar mic de termeni (de exemplu 20) el se comporta mult
mai eficient in comparatie cu algoritmul de sortare cel mai rapid "quick
sort".
Sortarea prin insertie (insertion sort). [Sunt curios...]
Acest tip de algoritm simplu de sortare si se comporta eficient
in lucrul cu tablouri de date de dimensiuni mici sau in cadrul tablourilor
sortate partial, el fiind adesea intalnit ca facand parte din alti algoritmi
de sortare mai sofisticati.El procedeaza prin aducerea termenilor (elementelor)
din tabloul unul cate unul si inserarea lor in pozitia corecta intr-un nou
tablou.Sortare prin insertie lucreaza - dealtfel dupa cum este si denumita
- inseeraza fiecare element sortat din tabloul de intrare (initial) intr-un
tablou iesire (rezultat) la locul potrivit.Simplitatea algoritmului consta
prin necesitatea de a avea doar doua tablouri structurate: tabloul de intrare
(nesortat) si tabloul de iesire in care termenii care se sorteaza sunt inserati.Pentru
a prevenii un numar prea mare de accese la memorie, cele mai multe implementari
folosesc metoda sortarii interioare ("pe loc") care functioneaza prin mutarea
termenului curent i partea termenilor sortati si segventa se tot repeta
pana cand termenului i s-a gasit valoarea de loc.Sortarea numita "shell
sort" este o varianta a sortarii prin insertie, insa se comporta eficient
si-n cazul sortarii unor tablouri mari de date.Sortarea prin insertie ese
mult mai eficienta decat sortare prin interschimbare (bubble sort), desii
trebuie sa se tine cont de anumite proprietati.
Sortarea prin insertie cu pas variabil (shell sort). [Sunt curios...]
Acest algoritm de sortare a fost implementat prima oara ,fiind
si denumta astfel, de catre Donald Shell in 1959.Algoritmul este inspirat
din principiul de sortare al algoritmului de sortare prin interschimbare
("bubble sort") si din algoritmul de sortare prin insertie.Principul de
sortare al algoritmului de sortare shell consta in schimbarea pozitiei
a mai multor termeni din tablou si nu doar schimbarea a unei pozitii al
un aunit timp.O implementare al acestui tip de algoritm poate fi descrisa
prin aranjarea segventelor de date intr-un tablou bidimensional, si apoi
sortarea coloanelor tabloului folosind sortarea prin insertie, metoda sortarii
prin insertie este integrata ca fiind parte din acest algortm.Algoritmul
de sortare Shell se comporta ineficient in cazul in care el trebuie sa
sorteze baze de date de mari dimensiuni, insa acest algoritm se poate aprecia
ca unul dintre cei mai rapizi in cazul in care lucreaza cu baze mici de date
(acestea avand un numar mai maic decat 1000 de termeni).Un alt avantaj al
algoritmului este faptul ca necesita, relativ, parti mici de memorie.
Sortarea prin interclasare (merge sort). [Sunt curios...]
Aceasta metoda (algoritm) de sortare usureaza procedeul de inlocuire
a tablourilor deja sortate si care trebuiesc resortate si puse intr-un
nou tablou.Algoritmul incepe prin a compara fiecare pereche de cate doua
elemente (adica 1 cu 2, si 3 cu 4) si inlocuirea lor daca primul element
ar trebui sa soseasca, in urma metodei (trecerii) de sortare, dupa primul
element din aceeasi pereche.Astfel se vor interschimba fiecare element
(termen) situate in tablourile sortate initial, rezultand tablouri de cate
doua elemente, apoi patru elemente etc,ca apoi sa se inceapa o noua
interclasare pentru numarul maxim de tablouri sortate rezultate, pana cand
si ultimele doua tablouri sunt sortate ca apoi sa rezulte numai un singur
tablou sortat.dintre algoritmii de sortare prezentati pana acum, acest tip
de algoritm este singurul care se poate comporta eficient in lucrul cu baze
de date de dimensiuni mari.
Sortarea cu ansamble (heap sort). [Sunt curios...]
Algoritmul "heapsort" face parte din familia algoritmilor care abordeaza
sortarea prin selectie.Aceasta familie de algoritmi functioneaza prin
a determina ceam mai mare sau cea mai mica valoare a termenului prezent
in tabloul care trebuie sortat plasandu-l la inceputul sau sfarsitul tabloului
in functie de marimea numarica a valorii a termenului, astfel continuand
si cu ceilalti termeni din tablou.Algoritmul poate executa treceri de sortare
intr-un interval de timp O(n2), acesta realizand task-uri
eficiente printr-o structura de date abstracta numita arbore binar care
are valoarea parintelui mai mare decat valorile fiilor.Abordand structura
arborelui binar in cadrul tabloului catre a fost sortat ar rezulta ca nodul
radacina al arborelui binar detin termenul din tablou cu cea mai mare valoare.Daca
in timpul procesului de sortare cest termen (element) care detine cea
mai mare valoare din tabloul sortat (ordonat) a fost comparata cu valoarea
si mai mare al altui termen din tablou, el va fi pus in tablou la locul
potrivit in timp ce elementul cu termenul cu cea mai mare va fi pus la
sfarsitul tabloului, obtinand astfel o sortare corecta.Algoritmul efectueaza
in timp un numar de O(n logn) treceri.
Sortarea rapida (quick sort). [Sunt curios...]
Este un algoritm de tip instabil care realizeaa operatii de segmentarea
datelor.Prin segmentarea unui tablou se intelege alegerea unui element
(termen) numit pivot cu care v-om compara toate elementele
tabloului pentru ca toate elementele care au valoari mai mici decat pivotul
se vor pozitiona inaintea lui obtinand astfel un segment (sub-tablou) din
tabloul initial iar toate elementele care au valori mai mai mari decat
pivotul v-or trece dupa acesta obtinandu-se un nou sub-tablou (segment).Acest
mecanism de sortare se petrece intr-un timp scurt, deoareace algoritmul
nu se foloseste alte structuri de date exterioare in care pozitioneaza
rezultatele sortarii,el lucrand astfel in cadrul tabloului initial (original).Algoritmii
care functioneaza dupa acest principu se numest algoritmi care functioneaza
"pe loc".Dupa ce tabloul initial a fost sectionat in functie
de valoarea pivotului rezultand un numar oarecare de sub-tablouri, aceste
sub-tablouri se vor sorta recursiv pentru a determina cel mai mare sau
cel mai mic subtablou.Eficienta implementarilor in sortarea rapida (cu
elegerea pivotului "pe loc") este tipica sortarilor instabile,
si care se aseamana cu eficienta algoritmulor cu metode complexe de sortare,
insa se numara printre cei mai eficienti algoritmi de sortare utilizati.sortarea
rapida foloseste si un modest spatiu de O(n logn) locatii de memorie,
particularitate care-l face sa fie printre cei mai utilizati algoritmi de
sortare.Cea mai complexa problema in cadrul algoritmului de sortare rapida
o reprezinta alagerea corecte a pivotului, caci corespunzator alegerii corecte
a pivotului algoritmul se comporta eficient, insa ineficienta algoritmul
consta uneori in alegrea necorespunzatoare a pivotului (medianei) rezultand
o performanta scazuta (O(n2)).Insa daca la fiecare pas
de sortare se va alege un pivot corect, atunci algoritmul va functiona dupa
functia O(n log n).
Sortarea prin selectie.[Sunt curios...]
Sortarea prin selectie este un algoritm de sortare, si a carui principiu de functionare este specific algoritmilor de sortare prin comparare care se fac "pe loc".Acest tip de sortare are complexitatea ?(n2), si se comporta eficient daca lucreaza cu liste mari de date, iar in cazul in care se comporta ineficient algoritmul are o rapiditate de sortare asemanatoare cu rapiditatea algoritmului de sortare ineficienta al metodei de sortare prin insertie.Sortarea prin selectie este preferata in practica deoarece reprezinta un algoritm simplu, avand si alte avantaje performante rezultand astfel ca sortarea prin selectie se situeaza deasupra altor algoritmi complicati de sortare chiar daca se sorteaza structuri de date de aceeasi complexitate..
5.Accesul algoritmilor la memorie. >>>
Daca dimensiunea unui tablou care se doreste sa fie
sortat se apropie sau depaseste dimensiunea memoriei interne, trebuie sa
se asigure memorarea tdatelor tabloului in spatii de memorie suplimentara
aflata pe un alt suport de memorie (discul fix sau memorie swap), deoarece
performanta algoritmul care face sortarea devine foarte inficienta daca
tablou memorat in meoria calculatorului este greu accesibil.Folosiera
memoriei de catre algoritmii de sortare reprezinta un criteriu de clasificare
important, insa pentru un algoritm necesita prea multe accese la memorie
nu mai este (relativ) important numarul de treceri realizate in timp pentru
a aranja elementele din tabloul care trebuie sortat cat conteaza numarul
de accese la memorie.Astfel dar, in cadrul acestor algoritmi numarul comparatiilor
dintre termenii tabloului aflati in memoria calculatorului este mul mai
semnificativa decat numarul de treceri pentru aranjarea lor, deoarece comparatiile
termenilor memorati in locatii succesive in memoria interna se realizeaza
mult mai rapid deoarece se executa la viteza a magistralei de sistem sau
a microprocesorului care sunt net superioare comparativ cu situatiile
in care datele care trebuiesc accesate pentru a fi comparate sunt memorate
pe discul fix sau pe un alt suport extern de memorie.
De exemplu, algoritmul de sortare recursiva "quick sort"
furnizeaza comportare eficienta avand datele memorate intr-o memorie RAM
(Random Access Memory) adecvata, insa numai prin metoda recursivitatii
el poate segmenta tabloul ce trebuie sortat in functie de pivot.Performanta
lui renumit de rapida ar scadea drastic in cazul in care ar trebui sa efectueze
o sortare in care datele ce trebuiesc sortate trebuiesc memorate intr-o
alta memorie decat memoria interna (RAM), deoarece ar putea cauza un numar
redus de operatii de copiere sau operatii de interschimbare din si pe
discul fix.In acest caz un alt algoritm ar putea fi mult mai eficient, deoarece
este implementat sa camumice cu meoria , chair daca necesita un numar mare
de accese.O alta metoda de a gasii solutii la accesul algoritmilor de sortare
la memorie sa se desfasoare eficient sunt inregistrarile complexe de date
(asemenatoare cu bazele de date relationale) deoarece ele folosestc metode
de osrtare pentru un numar mic de elemente, sau crearea unui index in interiorul
tabloului ce trebuie sortat.O versiune de sortare pentru tablouri este crearea
unui pivot (reper) care la fiecare trecere de sortare va fi cumparat cu
celelalte elementele ale tabloului, deoarece pivotul este mult mai mic in
comparatie cu dimensiunea intregului tablou,algoritmul trebuind sa memoreze
numai valoarea pivotului in memorie nu si dimensiunea intregului tabloului
intr-o memorie insuficienta, astfel fiind necesar memorarea datelor nememorate
din tablou pe un alt suport de memorie procedura numita "sortare tangentiala".
Alta tehnica pentru prevenirea memorarii datelor in
afara memoriei interne este combinarea a doi algoritmi intr-unul singur
unuind astfel avantajele lor pentru a realiza performante in comun.De
exemplu sunt algoritmi care segmenteaza tablourile ce trebuiesc sortate
in sub-tablouri (segmente) de dimensiuni reduse care pot fi memorate usor
in memoria interna.Sub-tablourile rezultate se pot si ele sorta si segmenta
folosind algoritmi care abordeaza o astfel de motoda, cum sunt de exemplu
algoritmul de sortare rapida "quick sort" sau "heap sort".
Tehnicile de sortare pot fi combinate.Pentru memorarea
unor date mari care depasesc dimensiunea memoriei interne ca trebui sortat
si pivotul cu ajutorul unor algoritmi, sau combinatie de algoritmi, care
realizeaza performante in comincare cu memoria deoarece rapiditatea unui
algoritm consta in cat mai putine accese la memorie.
6.Implementarea algoritmilor de sortare in
software. >>>
Cele mai multe limbaje de programare si-au implementat
propriul algoritm de sortare.Aceste limbaje folosesc tipic numai un singur
algoritm care este imbunatatit si implementat in sintaxa specifica fiecarui
limbaj de programare, si se comporta eficient in lucrul cu memoria.Cel
mai folosit este sortarea rapida ("quick sort"), iar din punct de vedere
al utlizarii este urmat de algoritmul de sortare "heap sort" si e algoritmul
de sortare prin interclasare ("merge sort").
Iata cateva exemple de componente software
care folosesc algoritmii de sortare:
Limbajul C.
Include qsort(),care este o functi de librarie
standard care realizeaza o sortare prin comparatii utilizand un operator
de comparare care este folosit ca pointer in cadrul acestei functii.Aceasta
implementare se comporta eficient, desii nu este prea folosita, ea bazandu-se
pe principiul algoritmului de sortare rapida.(REF ISO/MEC 9899:1999(E),
sectiunea 7.20.5.2, sau ANSI/ISO 9899:1990 sectinea 7.10.5.2)
Limbajul C++.
Foloseste functia qsort()insa adusa ca o demostratie
pentru functia STL std :: sort, care sorteaza rangurile
dintre doua iteratii cu acces aleatoriu.In plus, clasa std ::
list (liste inlantuite), care nu utilizeaza accese alatorii
este in metoda sort.tipul elementelor sortate trebuie sa accepte
operatorul de comparare, in caz contrar va fi necesar un operator de comparare
adecvat.In plus este usor sa se foloseasca principuil compararii cu operator
de comparare, el adesea performand cu metoda qsort(),
functie prezenta in limbajul C.Limbajul C++ fooseste si metodele stable_sort
si partial_sort.(REF sectiunile 25.3 si 25.4 din ISO/IEC
14882:2003(E) si 14882:1998(E)).
Limbajul Java.
Clasele utilizate in acest limbaj sunt numiteArrays
si Collections (ambele valabile in versiunea
1.2 car si in versiunile urmatoare) include functia sort,
care prezinta metode statice grupate lucrul cu structuri de date de tip
tablou si liste.Este necesar ca tablourile sa fie tablouri de primitive,
fiind preferabila situatia in care si tablourile si listele cu care se
lucreaza trebuie sa apartina metodelor care implementeaza interfata comparable,
sau trebuie declarat un indice Comparator adecvat.
Utilitarul Microsoft .NET Framework.
Aceasta componenta software ofera metoda statica Array.sort()
care poate sorta un tablou de obiecte folosind un indiciu (reper) de comprare
arbitrara.Desii nu este aceasta metoda nu este raspandita, este eficienta
in cadrul principiului de functionare deoarece este inspirata din algoritmii
de sortare de tip rapid ("quick sort").In plus se mai oferasi metoda
sort(), aflata in cadrul clasei ArrayList
care si ea foloseste principul metodei de sortare rapida ("quick sort").O
alta metoda cu capacitati de sortare este genericul List.
Utilitarul Perl.
Ofera o functiesort, care este o functie-operator ca
returneaza valori de tip intreg.In versiunea Perl 5.6 se foloseste o
metoda de sortare rapida ("quick sort"), insa in versiunile de dupa 5.6
se mai foloseste si metoda de sortare prin interclasare ("merge sort")
ca procedeu de sortare secundar.Un prim motiv pentru care se abordeaza
metode de sortare prin interclasare este securitatea aplicatiilor, deoarece
Perl este o unealta software cu care se pot construi aplicatii web.
Python
El ofera doua functii de sortare.Una este denumita functia sorted
care functioneaza dupa principiul metodelor de sortari albitrare, si cea
de-a doua functie este denumita sorted si functioneaza
ca o metode de sortare "pe loc" pentru sortarea elementelor din tablouri.
Standard M.
Nu are implementate metode proprii de sortare, utilizand pentru
metodele de sortare libraria SML/NJ care face parte
din libraria Standard ML of New Jersey.Aceasta
librarie mai ofera si functia QsortFn, cu ajutorul
careia se pot sorta elementele unui tabloul de date prin algoritmul de
sortare rapida ("quick sort").
Haskell.
Ofera o functie de sortare, care este dedicata in special pentru
sortarea listelor (nu si a tablourilor).Aceasta caracteristica este specificata
in termenii sortarii prin insertie, insa numai implementarile sortarilor
stabile sunt permise.
OCaml.Ofera trei tipuri de functii de sortare care
se pot aplica atata tablourilor cat si listelor.Aceste functii sunt denumite
sort, stable-sort si fast-sort
care in comparatie cu primele doua este foarte se comporta foarte rapid.In
fiecare versiune OCaml este folosita o metoda de sortare sort
diferita.
Common Lisp.
Common Lisp defineste in sectiunea 17.3 doua functii de sortare
denumite SORT si STABLE-SORT,
insa sunt nefolosite deoarece incalca principiile programarii structurate
prin functii de salt.Poate permite in limbaj specific Lisp orice metode
de sortare. |
Structuri de date abstracte |
SDA Arbori |
SDA Arbori Binari |
SDA Arbori Multicai |
SDA Arbori Optimi |
SDA Graf |
Traversarea grafurilor |
SDA Graf Ponderat |
SDA Graf Orientat |
SDA Lista Inlantuita |
SDA Tablou Asociat |
Despre algoritmi. |
Algoritmi de cautare neinformata, cautarea inforamata,cautarea in liste,in grafuri, in SQL-uri |
Algoritmi de cautare liniara, binara, interpolare |
Prezentare Algoritmi Sortare |
Sortare Insertie cu Pas Variabil (Shellsort) |
Sortarea Prin Ansamble (Heapsort) |
Sortarea Prin Insertie (Insertionsort) |
Sortarea Prin Interclasare (Mergesort) |
Sortarea Prin Interschimbare (Bubblesort) |
Sortarea Prin Selectie (Selectionsort) |
Sortarea Rapida (Quicksort)
|
Inapoi la pagina
principala |
|