Algoritmi de Sortare. Caracteristici Si Clasificare
Capitolul 1
NOȚIUNI INTRODUCTIVE
1.1. NOȚIUNEA DE SORTARE
Înainte de a începe prezentarea anumitor algoritmi de sortare se impune a specifica ce înseamnă sortare sau, cu alte cuvinte, ce-si propun sa rezolve algoritmii de sortare. Se dorește ca pornind de la o secvență de înregistrări conținând fiecare o cheie, secvența să fie reordonată astfel încât cheile să fie într-o anumită relație de ordine. Pentru chei numerice poate fi crescătoare sau descrescătoare, iar pentru chei alfanumerice poate fi ordinea alfabetică. Restul informației din înregistrare, mai puțin cheia se numește informație satelit.
1.2. APLICAȚII ALE SORTĂRII
Unele din cele mai importante aplicații ale sortării sunt:
Soluționarea problemei legate de punerea împreună a tuturor articolelor care au aceeași identitate, adică dându-se n (suficient de mare) articole într-o ordine aleatoare, din care multe au aceeași valoare, ne propunem să rearanjăm acest fișier astfel încât toate articolele cu valori egale să apară în poziții consecutive; elementele pot fi așezate crescător sau descrescător.
Dacă două sau mai multe fișiere au fost sortate în aceeași ordine, devine posibilă găsirea intrărilor identice printr-o singură trecere prin ele, fără întoarcere. Este mult mai economic să accesăm o listă de informații de la început la sfârșit, decât sa accesăm lista sărind aleator in listă, cu excepția cazului când lista este suficient de mică, pentru a fi memorată într-o memorie rapidă cu acces aleator. Sortarea face posibilă utilizarea adresării secvențiale în fișiere mari, ca un substitut fezabil adresării directe.
Sortarea este un mijloc ajutător pentru căutare, permițând astfel ca ieșirile de la calculator să poată fi adaptate cerințelor umane.
O altă aplicație, mai clară, a sortării apare în cazul rutinelor de editare a fișierelor unde fiecare linie este identificată de un număr de cheie. În timp ce un utilizator tipărește adăugări și modificări nu este necesar să se păstreze întreg fișierul în memorie. Liniile pot fi modificate, apoi sortate (oricum ele sunt ordonate) și după aceea comasate cu fișierul original. Aceasta permite o utilizare rezonabilă a eficienței memoriei într-o situație ce presupune multiprogramarea.
Fabricanții de calculatoare estimează că peste 25% din timpul de rulare al calculatoarelor este ocupat de sortare, în condițiile în care toți clienții sunt luați în considerare.Există multe instalații în care sortarea reclamă peste jumătate din timpul de calcul. Din aceste statistici putem conchide ca:
există o multitudine de aplicații ale sortării;
multe persoane utilizează sortarea fără sa fie nevoie;
se utilizează pe scară largă algoritmi de sortare ineficienți.
1.3. FORMULAREA PROBLEMEI
Se dau n articole R1, R2 …, Rn care urmează a fi sortate. Aceste articole Ie vom numi înregistrări, iar colecția de n înregistrări o vom numi fișier. Fiecare înregistrare Rj are o cheie Kj care guvernează procesul de sortare. Înregistrările pot conține si altă informație în afara cheii, numită informație satelit, care nu va avea nici un efect asupra procesului de sortare.
0 relație de ordine "<" este specificată asupra cheilor astfel ca pentru orice valoare a celor trei chei a, b, c, următoarele condiții să fie satisfăcute:
i) numai una din posibilitățile a<b, a=b, b<a este adevărată {legea trihotomiei);
ii) dacă a<b si b<c, atunci a<c (legea tranzitivității).
Aceste două posibilități caracterizează conceptul matematic de ordonare liniară, denumită și ordonare totală. Orice relație "<" ce satisface i) și ii) poate fi sortată prin majoritatea metodelor descrise în acest capitol, cu toate ca unele tehnici de sortare vor necesita chei numerice sau alfanumerice cu ordonarea obișnuită.
Scopul ordonării este de a determina o permutare a înregistrărilor, care va pune cheile într-o ordine nedescrescătoare:
Kp(1) ≤ Kp(2) ≤….≤ Kp(n). (1)
De exemplu, primind secvența de intrare (219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440) un algoritm de sortare întoarce ca rezultat secvența ordonată, (98, 129, 134, 151, 162, 193, 219, 231, 243, 332, 376, 429, 440, 449, 452, 491), conform relației de ordine "<".
În cazul algoritmilor de sortare, există o dependență profundă între reprezentarea datelor care trebuie prelucrate și alegerea algoritmului de prelucrare. Acest lucru conduce la clasificarea algoritmilor de sortare în algoritmi interni (secvența de sortat este păstrată în memoria internă) si algoritmi externi (secvența de sortat este păstrată pe un suport extern).
Distincția dintre cele doua reprezentări este sugestiv ilustrată de ordonarea cărților de joc. Dacă secvența care trebuie sortată este în memoria internă, suntem în situația în care toate cărțile de joc se află pe masă, fiecare fiind vizibilă și putând fi luată. În cazul păstrării datelor de intrare pe suportul extern cu acces secvențial, suntem în situația în care cărțile sunt puse într-un teanc, din care numai cartea din vârf este vizibilă.
În general, pentru a caracteriza dimensiunea problemei se folosește numărul de înregistrări din secvența, n. Acesta nu este întotdeauna suficient pentru a evalua timpul de execuție al unui algoritm, el depinzând și de modul de aranjare inițială a elementelor în secvență (de exemplu, secvență aproape sortată sau cu multe chei egale). Dorim sa obținem dependența de lungime a secvenței de sortat, a doi parametri: timpul de execuție și memoria suplimentară utilizată. Algoritmii de sortare care nu folosesc memorie suplimentară se numesc in situ.
1.4. CARACTERISTICILE ALGORITMILOR DE SORTARE
1.4.1.STABILITATEA
0 caracteristică importantă a unui algoritm de sortare este stabilitatea. 0 metoda de sortare va fi stabilită dacă păstrează ordinea relativă a înregistrărilor cu chei egale, adică
p(i) < p(j) pentru Kp(i) = Kp(j) și i < j. (2)
Este util ca o metodă de sortare sa fie stabilă în cazul unei duble sau multi sortări. De exemplu, dacă avem o secvență de înregistrări conținând un câmp nume și un câmp nota, secvența fiind sortată după nume, și dacă sortăm secvența și după nota, atunci în secvența finală pentru o sortare stabilă înregistrările cu aceeași valoare a câmpului notă vor fi încă în ordine alfabetică.
În unele cazuri vom dori ca înregistrările sa fie rearanjate fizic în memorie astfel încât cheile să fie în ordine, în timp ce, în alte cazuri, va fi suficient să avem un tabel auxiliar în care să se specifice într-un mod oarecare permutările, astfel ca accesul la înregistrări să se facă în ordinea cheilor. Unele metode de sortare presupun existența uneia sau a ambelor valori "+∞" sau "−∞", care se definesc ca fiind mai mari sau mai mici decât toate cheile, adică
− ∞ < Kj < +∞, pentru 1 ≤ j ≤ n . (3)
Aceste valori reprezintă substitute pentru chei artificiale și sunt de asemenea utilizate ca indicatoare santinelă. Cazul egalității este exclus din (3). Dacă egalitatea apare, algoritmii pot fi modificați astfel încât ei să funcționeze, dar în dauna eleganței și eficienței.
1.4.2.NATURALEȚEA
0 a doua caracteristică importantă a unei metode de sortare este naturalețea. 0 metodă de sortare este naturală dacă timpul de execuție scade odată cu creșterea gradului de sortare inițială. Deși intuitiv este evident ce înseamnă grad de sortare, pentru rigurozitate vom defini această noțiune. Trebuie specificat ca definiția are o semnificație atâta timp cât sortarea are la bază, ca operație elementară, compararea de valori, ea neavând nici un sens (și nici o utilitate) pentru algoritmi de tipul sortării după ranguri. Definim. gradul de sortare al unei secvențe elementare, ca fiind:
g =, (4)
unde n este lungimea secvenței de sortat, iar d(i) reprezintă distanța, în valoare absolută, între poziția finală și cea inițială a elementului aflat inițial pe poziția i. În cazul în care vectorul este sortat avem d(i)=0 pentru 1 ≤i ≤ n, deci g = 0. Dacă vectorul este sortat invers avem d(l)= n -1, iar d = 0. Presupunând ca gradul de sortare este o funcție liniară, adică
d(1) = ai + b, obținem ecuațiile , de unde . Deci expresia pentru d(i) este dată prin
(5)
și, cum g = ∑ d(i), obținem:
(6)
1.4.3. COMPLEXITATEA
Prin calculul de complexitate, care se va face pentru fiecare algoritm, se înțelege analiza algoritmului din care să reiasă o dependență între dimensiunea datelor de intrare și timpul de execuție. Se pot defini diferite măsuri (metrică) pentru intrare, dar pentru problema sortării cea mai naturală măsură este dată de numărul de elemente de sortat. În general, performanțele unei metode de sortare depind și de gradul de sortare parțială a vectorului, deci ar fi normal să intre ca parametru în expresia timpului de execuție. De obicei, se calculează timpul de execuție pentru diferite grade de sortare, cazul cel mai defavorabil, cazul mediu, cazul cel mai favorabil.
În studiul complexității algoritmilor de sortare vom folosi drept criterii de evaluare numărul de comparații de chei (Nc) și numărul de mutări de chei (Mc). Calculele făcute la definirea gradului de sortare au arătat că, în general, cheile se mută în cadrul procesului de sortare pe distanțe ce depind de gradul de sortare inițială. De aceea, nu va fi de ajuns să calculăm Nc si Mc doar în funcție de n, numărul de elemente din secvență, ci va trebui să facem o diferențiere în funcție de valoarea gradului de sortare.
Capitolul 2
ELEMENTE TEORETICE NECESARE
ANALIZEI ALGORITMILOR
2.1. CALCULUL DE COMPLEXITATE ȘI
NOTAȚII ASIMPTOTICE
Pentru o problemă se pot găsi o sumedenie de algoritmi. Pentru problema sortării, algoritmi diferiți se comportă diferit, chiar dacă primesc la intrare aceleași date. Eficiența unui algoritm, în cazul sortării, poate depinde de numărul de articole de sortat, de gradul de sortare parțială, sau de tipul de memorie în care este păstrată secvența. De aceea avem nevoie de o metodologie pentru a analiza acești algoritmi.
Compararea diferiților algoritmi trebuie făcută ținând cont de resursele limitate ale calculatorului (memorie ocupată și timp de utilizat de microprocesor). În ciuda progreselor tehnologice spectaculoase, trebuie elaborați algoritmi eficienți (care au cod mașină scurt și sunt rapizi) pentru rezolvarea problemelor moderne din ce in ce mai complexe. În general, se urmărește ca în urma analizei să rezulte o dependentă între timpul de execuție și dimensiunea datelor de prelucrat. Identificăm următoarele criterii de comparare a diferiților algoritmi ce pot rezolva o aceeași problemă dată: complexitatea spațiu și complexitatea timp a unui algoritm. Trebuie să definim cele două noțiuni.
2.1.1. COMPLEXITATEA SPAȚIU
Complexitatea spațiu este dimensiunea spațiului de memorie utilizat de program, spațiu care este de două tipuri:
– constant – folosit pentru memorarea codului programului executabil, a constantelor, variabilelor simple și a structurilor de date de dimensiune constantă alocate static; deci este independent de volumul și tipul datelor de intrare;
– variabil – folosit pentru structurile de date alocate dinamic (HEAP), precum și pentru apelurile de proceduri și funcții (STACK); dimensiunea acestui spațiu depinde și de tipul și volumul datelor de intrare, precum și de instanța problemei de rezolvat (starea la un moment dat al execuției: dacă folosesc sau nu structuri dinamice de date, dacă apelează sau nu subprograme).
Progresele tehnologice realizate (crearea unor memorii cu capacități de stocare din ce în ce mai mari) duc la scăderea importanței complexității spațiu.
2.1.2. COMPLEXITATEA TIMP
Complexitatea timp a unui algoritm influențează în mod direct timpul necesar execuției programului pe calculator. Nu vom determina timpul de execuție al programului (TEP) pe calculator, ci vom realiza analiza complexității (ACT) a algoritmului din următoarele motive: – timpul de execuție al programului depinde de numărul exact de operații elementare efectuate de algoritmul ce stă la baza conceperii programului și rezolvăriă calculăm Nc si Mc doar în funcție de n, numărul de elemente din secvență, ci va trebui să facem o diferențiere în funcție de valoarea gradului de sortare.
Capitolul 2
ELEMENTE TEORETICE NECESARE
ANALIZEI ALGORITMILOR
2.1. CALCULUL DE COMPLEXITATE ȘI
NOTAȚII ASIMPTOTICE
Pentru o problemă se pot găsi o sumedenie de algoritmi. Pentru problema sortării, algoritmi diferiți se comportă diferit, chiar dacă primesc la intrare aceleași date. Eficiența unui algoritm, în cazul sortării, poate depinde de numărul de articole de sortat, de gradul de sortare parțială, sau de tipul de memorie în care este păstrată secvența. De aceea avem nevoie de o metodologie pentru a analiza acești algoritmi.
Compararea diferiților algoritmi trebuie făcută ținând cont de resursele limitate ale calculatorului (memorie ocupată și timp de utilizat de microprocesor). În ciuda progreselor tehnologice spectaculoase, trebuie elaborați algoritmi eficienți (care au cod mașină scurt și sunt rapizi) pentru rezolvarea problemelor moderne din ce in ce mai complexe. În general, se urmărește ca în urma analizei să rezulte o dependentă între timpul de execuție și dimensiunea datelor de prelucrat. Identificăm următoarele criterii de comparare a diferiților algoritmi ce pot rezolva o aceeași problemă dată: complexitatea spațiu și complexitatea timp a unui algoritm. Trebuie să definim cele două noțiuni.
2.1.1. COMPLEXITATEA SPAȚIU
Complexitatea spațiu este dimensiunea spațiului de memorie utilizat de program, spațiu care este de două tipuri:
– constant – folosit pentru memorarea codului programului executabil, a constantelor, variabilelor simple și a structurilor de date de dimensiune constantă alocate static; deci este independent de volumul și tipul datelor de intrare;
– variabil – folosit pentru structurile de date alocate dinamic (HEAP), precum și pentru apelurile de proceduri și funcții (STACK); dimensiunea acestui spațiu depinde și de tipul și volumul datelor de intrare, precum și de instanța problemei de rezolvat (starea la un moment dat al execuției: dacă folosesc sau nu structuri dinamice de date, dacă apelează sau nu subprograme).
Progresele tehnologice realizate (crearea unor memorii cu capacități de stocare din ce în ce mai mari) duc la scăderea importanței complexității spațiu.
2.1.2. COMPLEXITATEA TIMP
Complexitatea timp a unui algoritm influențează în mod direct timpul necesar execuției programului pe calculator. Nu vom determina timpul de execuție al programului (TEP) pe calculator, ci vom realiza analiza complexității (ACT) a algoritmului din următoarele motive: – timpul de execuție al programului depinde de numărul exact de operații elementare efectuate de algoritmul ce stă la baza conceperii programului și rezolvării problemei (algoritmul are comportări diferite pentru seturi de date de intrare diferite);
– timpul de execuție depinde de tipul calculatorului pe care se execută programul (programul este "rapid" pe calculatoare puternice, dar "lent" pe calculatoare mai slabe);
– timpul de execuție al programului depinde și de limbajul de programare în care
este implementat (același program scris în limbajul C s-ar putea să fie mai rapid decât
implementarea sa în Pascal);
– din considerente practice, nu putem testa pe calculator programe pentru cazuri
oricât de mari, care ar dura ore, zile și chiar ani;
– se pot obține informații empirice asupra comportării în timp (duratei) a
programelor numai pentru seturi particulare de date de intrare, nu pentru situații generale.
Observații:
1) Timpul de execuție al unui program (TEP) se poate determina pentru programelen scrise în limbajul Pascal, folosind procedura standard gettime (ora, minutul, secunda, centisecunda) din unit-ul DOS, iar în limbajul C folosind funcția gettime din "DOS.H".
2) Această modalitate oferă informații concrete asupra TEP numai pentru seturile de date de intrare particulare pe care le folosim în testările noastre.
Analiza complexității timp (ACT) a unui algoritm constă în următoarele etape generale:
1) stabilirea operațiilor elementare (OE) efectuale de algoritm;
2) determinarea costurilor acestor operații elementare:
3) alegerea operației elementare reprezentative (OER);
4) determinarea ordinului de mărime pentru numărul de. operații elementare.
Definiție:
Se numește operație elementară acea operație sau grup de operații care are durata (timpul) de execuție independentă de datele de intrare ale problemei.
Exemple de operații elementare: o adunare, o scădere, o înmulțire, o împărțire, o comparație, o atribuire, 10 adunări, 10 scăderi, etc., pot constitui o operație elementară, dar un grup de n adunări nu poate reprezenta o operație elementară, deoarece durata lui de execuție depinde de volumul datelor de intrare (n).
Costul unei operații elementare este dat de timpul necesar execuției acestei operații elementare. Timpul unei operații elementare este fix. Fiecare operație elementară are alt timp de execuție.
Ideal ar fi să putem calcula timpul total de execuție al algoritmului (TEA), adică a sumei timpilor de execuție pentru toate operațiile elementare ale algoritmului. Un astfel de calcul este mult prea laborios și chiar imposibil de realizat practic, deoarece un algoritm se comportă diferit (are instanțe foarte multe) pentru diferite seturi de date de intrare, deci numărul de operații elementare și tipul lor diferă de la o instanță la alta.
Din considerentele anterioare se va proceda astfel:
– șirul timpilor de execuție ai operațiilor elementare este mărginit superior de o constantă C>0;
– presupunem că toate operațiile elementare au același timp de execuție;
– acest timp de execuție este egal cu această constantă C;
– operația (eventual fictivă) al cărei timp de execuție este egal cu C o numim
operație elementară reprezentativă.
Stabilind o operație elementară reprezentativă, nu mai este necesar să calculăm timpul total de execuție al tuturor operațiilor elementare, ci vom determina numai numărul de operații elementare. Chiar și acest calcul se dovedește dificil de realizat, deoarece algoritmul se comportă diferit pentru diferite seturi de date de intrare (numărul de operații diferă de la o instanță la alta). De aceea ne vom mulțumi numai cu determinarea ordinului de mărime (0) pentru numărul de apariții al operațiilor elementare reprezentative. Ordinul de mărime poate fi: constant, liniar, pătratic, cubic, logaritmic, exponențial, etc.
Concluzii:
1) ACT TEA TEP, adică ACT oferă informații generale și aproximative despre TEA și TEP;
2) Teoretic se realizează analiza complexității timp, dar practic se poate determina timpul de execuție al programului pentru cazuri particulare;
3) Analiza complexității timp arc un caracter pur teoretic ("pe hârtie”). Ea ignoră toți factorii care depind de mașină (calculator) sau de limbajul de programare ales pentru scrierea programului. Se axează pe determinarea ordinului de mărime pentru numărul de operații elementare, dar nu se determină și numărul operațiilor elementare.
4) Din nefericire, analiza complexității timp nu oferă informații care să caracterizeze cu precizie algoritmul respectiv; totuși se obține o comportare generală a algoritmului, cu o anumită doză acceptabilă de aproximație;
5) Rezolvarea unei probleme se poate face în mai multe feluri, prin mai mulți algoritmi diferiți; cunoașterea complexității timp a algoritmilor ne ajută mult în alegerea unei anumite variante de rezolvare.
2.1.3. REALIZAREA CONCRETĂ
A ANALIZEI COMPLEXITĂȚII TIMP A UNUI ALGORITM (ACT)
Analiza riguroasă a complexității timp pentru un algoritm dat necesită un aparat matematic laborios și serioase cunoștințe de matematică.
Notații:
n = ordinul de mărime al datelor de intrare în algoritm;
T(n) = complexitatea timp a algoritmului;
0 = ordinul de mărime al complexității timp;
f(n) = o funcție (estimată) dependentă de numărul operațiilor elementare reprezentative (OER.) din algoritm.
Definiție
Algoritmul are complexitatea timp T(n) de ordinul f(n) dacă există constantele c0 > 0 și n0 > 0 astfel încât T(n) <= co*f(n), pentru orice n ≥ n, adică pentru valori foarte mari ale lui n, T(n) tinde să ia aceleași valori cu f(n). Pentru aceasta se folosește notația T(n)= O(f(n)), numită notație asimptotică.
Ordinul de mărime al complexității timp (O) oferă o limită superioară pentru durata de execuție a algoritmului; această limită nu va fi depășită, oricât de mare va fi n (oricât de "voluminoase" vor fi datele de intrare în algoritm). Vom căuta să determinăm o "cea mai mică funcție" f(n) și o "cea mai mică'' valoare pentru c0, astfel încât complexitatea timp T(n) să fie cât mai "mică".
Deoarece nu ne interesează valoarea exactă a lui T(n), ci numai ordinul lui de mărime, vom reține în calculul său numai termenul dominant., care este chiar f(n). De exemplu, dacă T(n.)=3n2+14n+7, atunci termenul dominant este 3n2, f(n) este n2, iar ordinul de mărime al lui T(n) este n2, deci algoritmul are complexitate timp O(n2).
Observații:
a) Pentru mai mulți algoritmi complexitatea timp depinde și de structura datelor de intrare în algoritm (nu numai de volumul lor); în aceste situații se studiază trei tipuri de complexitatea timp: complexitatea pentru cazul cel mai defavorabil (timp mare de execuție pe calculator), complexitatea pentru cazul mediu, complexitatea pentru cazul cel mai favorabil (timp mare de execuție pe calculator). De exemplu,
– unii dintre algoritmii de sortare au complexitatea timp dependentă de ordinea inițială a îregistrărilor pe care dorim să le sortăm;
– sortarea prin interschimbare: dacă vectorul este deja ordonat, atunci se execută n-l comparații (se parcurge vectorul o singură dată); dacă vectorul este ordonat invers, atunci se execută comparații.
b) Prezintă interes practic doar studiul pentru cazul mediu (timpul mediu) și cel mai defavorabil (timpul maxim).
Pentru a indica complexitatea timp se folosesc următoarele exprimări:
– algoritmul este constant (nu depinde de n) dacă T(n) = O(l);
– algoritmul este logaritmic dacă T(n) = O(log n);
– algoritmul este liniar dacă T(n) = O(n);
– algoritmul este liniar logaritmic dacă T(n) = O(n log n);
– algoritmul este pătratic dacă T(n) = O(n2);
– algoritmul este cubic dacă T(n) = O(n3);
– algoritmul este polinomial dacă T(n) = O(nk), unde k > 3 ;
– algoritmul este exponențial dacă T(n)= O(kn), unde k ≥ 2;
– algoritmul este factorial dacă T(n) = O(n!).
Notația asimptotică O permite stabilirea următoarelor relații:
O(l) ≤ O(log n) ≤ O(n) ≤ O(n log n) ≤ O(n2) ≤ O(n3) ≤ O(nk) ≤ O(kn) ≤ O(n!)
Algoritmii preferați sunt cei care au ordinul de complexitate (O) situat spre stânga acestui șir. Practica a impus ca acceptabili algoritmii cu complexitate timp "polinomială", deoarece programele ce-i implementează au o durată rezonabilă la executarea cu ajutorul calculatorului.
2.1.4. CAZUL MEDIU ȘI CAZUL CEL MAI DEFAVORABIL
Realizarea unui algoritm nu se face după o rețetă anume, ea este legată mai mult de experiența programatorului, nu este un proces liniar pentru că de multe ori va fi necesar să revenim la etape anterioare pentru a le repeta. După ce am demonstrat corectitudinea algoritmului și am analizat eficiența acestuia, putem scrie codul într-un limbaj de programare după care putem să-l optimizăm sau numai să-l implementăm, situații care ne conduc la etape anterioare de rescriere a unor porțiuni din algoritm, după care evident va trebui să facem teste de corectitudine, teste de determinare a complexității, o analiză teoretică a acesteia.
Complexitatea in cazul cel mai defavorabil reprezintă numărul. maxim de operații elementare executate de algoritm. Sunt foarte des întâlnite situații când o serie de algoritmi foarte utili au o comportare convenabilă în practică (adică pentru majoritatea seturilor de date de intrare), dar pentru cazul cel mai defavorabil (când natura și structura datelor de intrare este deosebită) sunt nesatisfăcători.
Complexitatea medie. Pentru studierea complexității în medie este necesar să cunoaștem caracteristicile cât mai multor seturi de date de intrare și, din acest motiv, analiza complexității în medie este mai dificil de realizat.
Notații:
S- spațiul de intrare,
p(s) – probabilitatea apariției datei s Є S la intrarea algoritmului;
TA (s) – numărul de operații elementare efectuate de algoritm pentru intrarea s Є S .
Atunci complexitatea medie este p(s) TA(s).
Capitolul 3
SORTAREA INTERNĂ
Sortare internă presupune păstrarea înregistrărilor în memoria internă. Sortarea internă se împarte în câteva importante:
i) Sortarea prin inserție. Articolele sunt considerate pe rând câte unul. Fiecare articol nou este inserat in locul corespunzător în raport cu articolele sortate anterior.
ii) Sortarea prin interschimbare. Dacă două articole vor fi găsite necorespunzătoare ordonării cerute, ele vor fi interschimbate. Acest proces se repetă până când nu mai sunt necesare interschimbări.
iii)Sortarea prin selecție. La început se găsește articolul cel mai mic (sau cel mai
mare) și el este separat de rest, apoi este găsit cel mai mic (sau cel mai mare) articol din cele rămase, și așa mai departe.
Sortarea prin numărare. Fiecare articol este comparat cu toate celelalte.
Numărând câte vor fi mai mici, se găsește poziția finală a articolului inițial. În capitolele care urmează, voi prezenta fiecare metodă în parte.
3.1. ALGORITMI DE SORTARE PRIN NUMĂRARE
3.1.1. SORTAREA PRIN NUMĂRAREA COMPARAȚIILOR
3.1.1.1. PREZENTAREA METODEI
Sortarea prin numărare este o metodă simplă, care se bazează pe ideea că cheia j din secvența finală sortată este mai mare decât (j-1) din celelalte chei. Metoda constă în compararea fiecărei perechi de chei, numărând câte vor fi mai mici decât fiecare cheie particulară. Comparațiile se fac în modul următor:
((compara Kj, cu Ki) pentru 1 ≤ j ≤ n) pentru 1 ≤ i ≤ n.
Se observă că jumătate din aceste comparații sunt redondante, deoarece nu este necesar să se compare Ka cu Ka, pentru 1 ≤ a ≤ n, și nici Ka cu Kb și apoi Kb cu Ka, pentru 1 ≤ a, b ≤ n . {în aceste condiții avem nevoie de ((compara Kj cu Ki) pentru 1 ≤ j ≤ i) pentru 1 ≤i ≤ n.
3.1.1.2. PREZENTAREA ALGORITMULUI
Algoritmul A (comparare prin numărare) va sorta R1, R2, …, Rn, după cheile K1, K2 …, Kn prin intermediul unui tabel auxiliar COUNT[1],COUNT[2], …, COUNT[n] pentru a număra câte chei sunt mai mici decât o cheie dată. După terminarea algoritmului COUNT[j]+1 va specifica poziția finală a înregistrării Rj. La terminarea algoritmului, înregistrările sunt deplasate într-o zonă de ieșire X1 , X2, …, X n.
Algoritmul A este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul X[n] care conține elementele sortate.
Am mai folosit vectorul COUNT[n] care conține pozițiile în vectorul sortat X[n], adică COUNT[j]+l va specifica poziția finală a înregistrării Rj.
Pentru i=1, i<=n, i = i+1, execută
COUNT[i] = 0
Pentru i =1, i<=n, i = i+1, execută
Pentru j = i, i<=n, j = i+1, execută
Daca K[j]<K[i] atunci COUNT[j] = COUNT [j] +1
altfel COUNT [i] = COUNT [i] +1
Pentru i=1, i<=n, i<-i+1, execută
X[COUNT[i]] = K[i]
Se observă că acest algoritm nu comportă nici o deplasare de înregistrări. El este similar cu o sortare prin tabele de adrese, deoarece vectorul COUNT specifică aranjamentul finall al înregistrărilor. Există și o diferență, pentru că COUNT[j] indică unde trebuie deplasat Rj. Trebuie luat în considerare cazul cheilor egale. In acest caz, cheilor egale le vor corespunde C0UNT-uri egale, rearanjarea finală fiind greoaie, dar algoritmul dă rezultatul corect indiferent de numărul de chei egale.
3.1.1.3. COMPLEXITATEA ALGORITMULUI
Numărul de comparații din acest algoritm este egal cu Cn2 = , al cărui factor dominant n2 reprezintă timpul de rulare a acestui algoritm. Factorul n2 care domină timpul de rulare arată că algoritmul nu este o cale eficientă de sortare în cazul în care n este mare; dublarea numărului de înregistrări duce la creșterea timpului de rulare de patru ori. Deoarece metoda solicită compararea tuturor perechilor de chei distincte (Ki, Kj.), nu există o posibilitate de a scăpa de dependența de n2. Timpul mediu de rulare poate fi redus la n log n folosind un alt algoritm. Acest algoritm este interesant pentru simplitate și nu pentru eficiență.
Tabel 1.Algoritmul A (Sortare prin numărare).
După aplicarea algoritmului se obțin pozițiile pe care se află elementele sortate.
3.1.2. SORTAREA PRIN NUMĂRAREA DISTRIBUȚIILOR
Există o altă posibilitate de sortare prin numărare foarte importantă din punct de vedere al eficienței. Acesta se aplică mai ales în cazurile în care există multe chei egale și când toate cheile sunt cuprinse în intervalul [u, v], cu v-u mic, adica u ≤ Kj ≤ v, pentru 1 ≤ j ≤ n. Aceste condiții par foarte restrictive. Metoda se aplică doar pentru unul din câmpurile cheie și nu pentru toată cheia, obținând fișierul sortat parțial și va fi simplu să terminăm sortarea.
3.1.2.1. PREZENTAREA METODEI
Toate cheile sunt cuprinse între 1 și 100. Intr-o primă trecere prin fișier numărăm câte 1-uri, 2-uri, …, 100-uri sunt prezente. In a doua trecere putem deplasa înregistrările în locurile corespunzătoare în zona de ieșire, etc.
3.1.2.2. PREZENTAREA AlGORITMULUI
Algoritmul B (Numărarea distribuțiilor)
Considerăm că toate cheile sunt întregi în domeniul u ≤ Kj ≤ v penlru 1≤j≤n. Acest algoritm va sorta înregistrările R1, R2 …, Rn utilizând un tabel auxiliar COUNT[u] COUNT[u+1], …, COUNT[v]. La terminarea algoritmului, înregistrările sunt deplasate într-o zonă de ieșire X1, X2, …, Xn.
Algoritmul B este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul X[n] care conține elemntele sortate.
Am mai folosit vectorul auxiliar COUNT[u] , COUNT[u+1], …, COUNT[v] care conține numărul de elemente egale cu u,u +1,…,v.
u = r[1]
v = r[1]
Pentru i =2, i<=n, i = i+1, executa
Daca u>=K[i] atunci
u = K[i]
altfel
Daca v<K[i] atunci v = K[i]
Pentru i =2, i<=n, i = i+1, executa
COUNT[i]:=0
Pentru j =1, j<=v, j = j+1 executa
COUNT[K[j]] = COUNT[K[j]] +1
Pentru i = u+1, i<=v, j = j+1executa
COUNT[i] = COUNT[i] + COUNT [i-1]
Pentru j = n ,j>=1, j = j – 1 executa
i = COUNT[K[j]]
X[i] =K[j]
COUNT[K[j]] = i-1
3.2. SORTAREA PRIN INSERȚIE
Una din familiile importante de tehnici de sortare se bazează pe metoda “jucătorului de bridge". Articolele sunt considerate pe rând câte unul. Fiecare articol nou inserat în locul corespunzator cu articolele sortate anterior. Metoda este folosită de jucătorii de bridge în sortarea cărților, când iau cărțile una cate una. Înainte de a examina înregistrarea Rj, vom considera că înregistrările precedente R1, R2 …, Rn au fost deja sortate, apoi vom insera Rj în locul ce îi revine între înregistrările sortate anterior. Sunt posibile mai multe variații bazate pe această temă.
3.2.1. SORTAREA PRIN INSERȚIE DIRECTĂ
3.2.1.1. PREZENTAREA METODEI
Cea mai simplă sortare prin inserție este și cea mai evidentă. Se consideră 1 < j ≤ n și înregistrările R1, R2 …, Rj-1, aranjate astefel încât K1 ≤ K2 ≤…≤ Kj-1. Cheia de sortare pentru înregistrarea Rj este Kj. Vom compara pe rând noua cheie Kj cu Kj-1, Kj-2,…, până ce vom descoperi că Rj trebuie inserat între înregistrările Ri și Ri+1; apoi deplasăm înregistrările Ri+1, Ri+2,…,Rj-1 cu o poziție și introducem noua înregistrare în poziția i+1. Este convenabil să se combine operațiile de comparare și deplasare, întrețesându-le așa cum se vede în algoritm. Deoarece Rj "intră în locul său', această metodă de sortare a fost denumită metoda de cernere suu scufundare.
3.2.1.2. PREZENTAREA ALGORITMULUI
Algoritmul C (sortarea prin inserție directă) va sorta înregistrările R1, R2, …, Rn; după sortare, cheile vor fi în ordinea K1 ≤ K2 ≤ … ≤ Kn.
Algoritmul C este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul R[n] care conține elementele sortate.
Pentru j =1, j<=n, j = j+1, executa
element = K[j]
i = j -1
Cat_timp(i>=1) si (K[i]>element) executa
K[i+1] = K[i]
i = i-1
K[i+1] = element
Tabelul 2: Algoritmul C (Sortare prin inserție directă)
3.2.1.3. COMPLEXITATEA ALGORITMULUI
Analizăm algoritmul în funcție de n, numărul de înregistrări ce urmează a fi sortate. La fiecare iterație a primului ciclu repetitiv, elementele R1, R2,…, Rj-1, sunt deja ordonate și va trebui să inserăm valoarea lui Rj pe poziția corectă în șirul ordonat. În cazul cel mai defavorabil (înregistrările sunt ordonate în sens invers al cheilor), fiecare element Rj va fi plasat pe prima poziție, deci următorul ciclu repetitiv se execută de j-1 ori. Cum am considerat că operația elementară este comparația K[i] > cheie urmată de deplasarea elementului cu o poziție, vom avea 1 + 2 +… + n -1 = comparații, atunci în cazul cel mai defavorabil algoritmul este O(n2).
Să analizăm acum comportarea acestuia în medie. Pentru aceasta, vom considera K[i] ≠ K[j] pentru 1 ≤ i, j ≤ n, i ≠ j și că orice permutare a lor are aceeași probabilitate de apariție. Atunci probabilitatea ca K[j] să fie plasată pe poziția k în șirul R1, R2,…, Rj-1, k Є {l,2,…,i} este . Numărul mediu de operații elementare, pentru un i fixat este:
Pentru a sorta cele n elemente sunt necesare:
operații elementare, deci complexitatea medie este tot O(n2).
3.2.2. SORTAREA PRIN INSERȚIE BINARĂ
În timpul sortării prin inserție directă, în timp ce înrergistrarea j este prelucrată, va trebui să comparăm cheia sa în medie cu aproximativ j din cheile sortate anterior. De aceea, numărul de comparații va fi în jur de , ceea ce devine foarte mare în cazul valorilor mici ale lui n. Am vazut în capitolul 3 diferite tehnici de căutare, printre care și cea de căutare binară, care vor indica unde trebuie inserat articolul j, numai după efectuarea log2 j comparații bine alese. Numărul total de comparații pentru inserara tuturor celor n articole va fi aproximativ n log2 j, ceea ce este o îmbunătățire substanțială, față de . Această metodă este denumită, inserție binară și a fost mentionată de John Mauchly, în 1946, în prima discuție publică referitoare la sortarea pe calculator.
3.2.2.1. PREZENTAREA METODEI
Sortarea prin inserție binară se bazează pe următoarea metodă: Fie R1, R2, …, Rn cele n înregistrări ale fișierului, care au cheile K1, K2, …, Kn. Pornim cu subfișierul R1 și la primul pas căutăm, folosind căutarea binară, poziția în care ar trebui să se găsească R2. Dacă K2 < K1, atunci R2 trebuie să fie înainte de R1 deci îl mutăm pe R1, în locul lui R2. La pasul i, unde 2 ≤ i ≤ n, avem înregistrările R1, R2,…, Ri-1 sortare crescător și încercăm să inserăm înregistrarea Ri, astfel încât să obținem elementele sortate între 1 si i. Căutăm poziția pe care ar trebui inserat elementul Ri folosind tot căutarea binară. Odată găsită poziția k pe care va trebui să se plaseze elementul Ri, mai rămâne problema deplasării elementelor de la poziția k, cu câte o poziție spre dreapta.
Pentru cele șaisprezece chei (219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440), sortarea prin inserție binară are următorul efect:
– Pentru i = 1, primul element ramâne pe loc R[1] =219.
– Pentru i = 2, luăm inc = 1 și sf = 1. Se caută locul elementului elem = 129 . Cum inc ≤ sf, facem m = 1. Cum 129 = elem < R[m] =219, luăm sf = 0. Structura repetitivă se încheie aici pentru că inc > sf . Mai trebuie să deplasăm acum elementul R[1] =219 în locul componentei R[2],adică R[2]= 219, și apoi facem R[1]= 129 . Astfel obținem:
(129, 219, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 3, luăm inc =1 și sf = 2 . Se caută locul elementului elem = 243 . Cum inc ≤ sf, facem m = 1. Cum 243 = elem > R[m] = 129, luăm inc = 2 . Facem m = 2. Cum 243 = elem > R[m]= 219, luăm inc = 3. Structura repetitivă se incheie aici pentru că inc > sf . De această dată nu mai trebuie să deplasăm elementele și obținem:
(129, 219, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 4 , luăm inc =1 și sf = 3. Se caută locul elementului elem = 98. Cum inc ≤ sf, facem m=2. Cum 98 = elem < R[m] = 219, luăm sf = 1 Facem m = 1. Cum 98 = elem < R [m] = 129, lu[m sf = 0. Structura repetitivă se încheie aici pentru că inc > sf. Deplasăm elementele 129, 219, 243 și obținem:
(98, 129, 219, 243, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 5, luăm inc = 1 și sf = 4 . Se caută locul elementului elem = 491. Cum inc ≤ sf, facem m = 2. Cum 491 = elem > R[m] =129, luăm inc = 3. Facem m = 3. Cum 491 = elem > R[m] = 219, luăm inc = 4. Facem m = 4. Cum 491 = elem > R[m]= 243, luăm inc = 5. Structura repetitivă se înehceie aici pentru că inc > sf . Nu mai este necesar să deplasăm elementele și obținem:
(98, 129, 219, 243, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 6, luăm inc = 1 și sf = 5 . Se caută locul elementului elem =151. Cum inc < sf , facem m = 3. Cum 151 = elem < R[m]= 219, luăm sf = 2 . Facem m = 1. Cum 151 = elem >R[m]= 98, luăm inc =2. Facem m = 2. Cum 151 = elem > R[m]= 129, luam inc = 3. Structura repetitivă se încheie aici pentru că inc > sf . Vom deplasa elementele 219, 243, 491 și obținem:
(98, 129, 151, 219, 243, 491, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 7, luăm inc =1 și sf = 6. Se caută locul elementului elem = 452. Cum inc ≤ sf , facem m = 3, Cum 452 = elem > R[m] =151, luăm inc = 4. Facem m = 5 . Cum 452 = elem > R[m] = 243, luăm inc = 6. Facem m = 6. Cum 452 = elem < R[m] = 491, luăm sf = 5. Structura repetitivă se încheie aici pentru că inc. > sf . Vom deplasa elementul 491 și obținem:
(98, 129, 151, 219, 243, 452, 491, 162, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i=8, luăm inc. = 1 și sf = 7 . Se caută locul elementului elem =162 . Cum inc < sf , facem m = 4. Cum 162 = elem < R[m] =219, luăm sf = 3 . Facem m = 2 . Cum 162 = elem > R[m] = 129 , luăm inc = 3 . Facem m = 3 . Cum 162 == elem > R[m] =151, luăm inc = 4 , Structura repetitivă. se încheie aici pentru că inc > sf . Vom deplasa elemenlele 219, 243, 452, 491 și obținem:
(98, 129, 151, 162, 219, 243, 452, 491, 376, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 9, luăm inc =1 și sf = 8 . Se caută locul elementului elem = 376 . Cum inc ≤ sf , facem m = 4. Cum 376 = elem > R[m]=162, luăm inc = 5 . Facem m = 6 . Cum 376 == elem > R[m] = 243, luăm inc = 7 . Facem m = 7 . Cum 376 = elem < R[m] = 452, luăm sf = 6. Structura repetitivă se încheie aici pentru că inc > sf . Vom deplasa elementele 452, 491 și obținem:
(98, 129, 151, 162, 219, 243, 376, 452, 491, 193, 134, 231, 332, 429, 449, 440)
– Pentru i = 10, luăm inc =1 și sf = 9. Se caută locul elementului elem =193. Cum inc ≤ sf, facem m = 5 . Cum 193 = elem < R[m] = 219, luăm sf = 4 . Facrm m=2. Cum 193 = elem > R[m] = 129, luăm inc = 3. Facem m = 3 . Cum 193 = elem > R[m] =151, luăm inc = 4. Facem m = 4. Cum 193 = elem > R[m] = 162, luam inc = 5 . Structura repetitivă se încheie aici pentru ea inc > sf. Vom deplasa elementele 219, 243, 376, 452, 491 și obținem:
(98, 129, 151, 162, 193, 219, 243, 376, 452, 491, 134, 231, 332, 429, 449, 440)
– Pentru i=11, luăm inc = 1 și sf=10. Se caută locul elementului elem=134. Cum inc ≤ sf , facem m=5. Cum 134 = elem < R[m]= 193, luăm sf=4. Facem m =2. Cum 134 = elem > R[m] = 129 , luăm inc = 3. Facem m = 3. Cum 134 = elem < R[m] =151, luăm sf = 2. Structura repetitivă se încheie aici pentru ca inc > sf. Vom deplasa elementele 151, 162, 193, 219, 243, 376, 452, 491 și obținem:
(98, 129, 134, 151, 162, 193, 219, 243, 376, 452, 491, 231, 332, 429, 449, 440)
– Pentru i=12, luăm inc = 1 și sf=11 Se caută locul elementului elem =231. Cum inc ≤ sf , facem m = 6. Cum 231 = elem > R[m] = 193, luăm inc = 7. Facem m = 9. Cum 231 = elem < R[m] = 376, luăm sf = 8. Facem m = 8 . Cum 231 = elem < R[m] = 243, luăm sf = 7. Facem m=7. Cum 231 = elem > R[m]= 219, luăm inc=S. Structura repetitivă se încheie aici pentru că inc > sf. Vom deplasa elementele 243, 376, 452, 491 și obținem:
(98, 129, 134, 151, 162, 193, 219, 231, 243, 376, 452, 491, 332, 429, 449, 440)
– Pentru i=13, luăm inc = 1 și sf=12. Se caută locul elemeutului elem=332. Cum inc ≤ sf , facem m = 6. Cum 332 = elem > R[m] = 193, luăm inc = 7. Facem m=9. Cum 332 = elem > R[m]= 243, luăm inc =10. Facem m = 11. Cum 332 elem < R[m]= 452, luăm sf=10. Facem m=10. Cum 332 = elem < R[m] = 376, luăm sf = 9. Structura repetitivă se încheie aici pentru că inc > sf . Vom deplasa elementele 376, 452, 491 obținem:
(98, 129, 134, 151, 162, 193, 219, 231, 243, 332, 376, 452, 491, 429, 449, 440)
– Pentru i=14, luăm inc = 1 și sf=13. Se caută locul elementului elem = 429. Cum inc ≤ sf , facem m = 7 . Cum 429 = elem > R[m]= 219, luăm inc =8. Facem m=10. Cum 429 = elem > R[m]= 332, luăm inc = 11. Facem m = 12. Cum 429 = elem < R[m] = 452, luăm sf = 11. Facem m = 11. Cum 429 = elem > R[m] = 376, luăm inc = 12. Structura repetitivă se încheie aici pentru că inc > sf. Vom deplasa elementele 452, 491 și obțnem:
(98, 129, 134, 151, 162, 193, 219, 231, 243, 332, 376, 429, 452, 491, 449, 440)
– Pentru i=15, luăm inc = 1 și sf = 14. Se caută locul elementului elem = 449. Cum inc ≤ sf, facem m = 7. Cum 449 = elem > R[m] = 219, luăm inc = 8. Facem m = 11. Cum 449 = elem > R[m] = 376, luăm inc =12. Facem m=13. Cum 449 = elem < R[m]=452, luăm sf = 12. Facem m=12. Cum 449 = elem > R[m]= 429, luăm inc = 13. Structura repetitivă se încheie aici pentru că inc > sf. Vom deplasa elementele 452, 491 și obținem:
(98, 129, 134, 151, 162, 193, 219, 231, 243, 332, 376, 429, 449, 452, 491, 440)
Pentru i=16, luăm inc = 1 și sf = 15. Se caută locul elementului elem = 440. Cum inc ≤ sf , facem m = 8. Cum 440 = elem > R[m] = 231, luăm inc = 9. Facem m =12. Cum 440 = elem > R[m] = 429, luăm inc=13. Facem m=14. Cum 440 = elem < R[m]= 452, luăm sf = 13. Facem m=13. Cum 440 = elem < R[m]= 449, luăm sf = 12. Structura repetitivă se închrie aici pentru că inc > sf . Vom deplasa elementele 449, 452, 491 și obținem:
(98, 129, 134, 151, 162, 193, 219, 231, 243, 332, 376, 429, 440, 449, 452, 491)
Astfel am obținut elementele în ordine crescătoare.
3.2.2.2. PREZENTAREA ALGORITMULUI
Algoritmul D (sortarea prin inserție binară) va sorta înregistrările R1, R2, …, Rn; după sortare, cheile vor fi în ordinea K1 ≤ K2 ≤ … ≤ Kn .
Algoritmul D este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul R[n] care conține elementele sortate.
Pentru i =2, i<=n, i = i+1, executa
element = r [i]
inceput = 1
sfarsit = i -1
cat_timp (inceput<=sfarsit) executa
mijloc = | (inceput+sfarsit)/2 |
daca element < r[mijloc] atunci sfarsit = mijloc-1
altfel inceput:= mijloc+1
for j:=i downto inceput+1 do r [j]:=r [j-1]
r[inceput] = element
3.2.2.3. COMPLEXITATEA ALGORITMLUI
Conform analizei făcute la căutarea binară, pentru a determina locul în care trebuie inserat Rk între celelalte înregistrări astfel încât K1 ≤ K2 ≤ … ≤ Kk-1 sunt necesare cel mai mult [log2 k] comparații. În aceste condiții, metoda sortării prin inserție binară necesită cel mult T(n) = comparații. Se poate arăta că T(n)= .
Pentru n = 2 relația se verifică ușor. Să presupun relația adevarată pentru n și să o demonstrez pentru n + 1. Deosebim două cazuri:
dacă 2m-1< n< 2m, atunci [log2 n] = [log2 (n+1)] = m și
S(n+1) = S(n) + [log2 (n+1)] = nm – 2m + 1 + m = (n+1)m – 2m +1=
= (n+1)[log2 (n+1)] – +1
dacă n = 2m, atunci [log2 n] = m și [log2(n+1)] = m+1. Rezultă că
S(n +1) = S(n) + [log2 (n +l)] = nm – 2m +1 + m = (n+1)m -2m +2,
iar
(n+1)[log2 (n+1)] –
= (n + l)m – .
3.2.2.4. ÎMBUNĂTĂȚIRE A SORTĂRII PRIN INSERȚIE BINARĂ:
SORTAREA PRIN INSERȚIE ÎN DUBLU SENS
Din nefericire, inserția binară, rezolvă numai jumătate din problemă. După găsirea locului unde trebuie inserată înregistrarea R[j], va trebui să deplasăm aproximativ din înregistrările sortate anterior pentru a face loc lui R[j], aslfel că timpul total de rulare va rămâne proporțional cu n2. Prima încercare propusă la începutul anilor 1950 se numește inserție în dublu sens. Primul articol este pus în centrul unei zone de ieșire, iar pentru articolele ce urmează se face spațiu prin deplasare la stânga sau la dreapta, după cum este mai convenabil. Aceasta va economisi aproximativ jumătate din timpul de rulare față de inserția binară obținută. Prețul plătit pentru această economie constă într-un program ceva mai complicat. Această metodă se poate utiliza fără a solicita spațiu mai mult decât pentru cele n înregistrări.
3.2.3. SORTARE CU MICȘORAREA INCREMENTULUI
METODA LUI SHELL
Această metodă a fost pusă la punct de către Donald L. Shell în 1959 si este o completare a algoritmului de insertie directă. El mai poartă numele si de sortare prin micsorarea incrementului. Incrementul reprezintă de fapt numărul de grupe în care va fi împărtit tabloul R.
Este unul din algoritmii care deplasează articole numai cu câte o poziție deodată, timpul său mediu de rulare va fi în cel mai bun caz cu n2, deoarece fiecare înregistrare trebuie deplasată în medie aproximativ poziții, în timpul procesului de sortare. Pentru a îmbunătăți inserția directă, avem nevoie de un mecanism, prin intermediul căruia înregistrările să efectueze salturi lungi în loc de pași mici. O asemenea metodă a fost propusă în anul 1959 de Donald L. Shell și se numește sortare cu micșorarea incrementului.
3.2.3.1. PREZENTAREA METODEI
Considerăm 16 înregistrări R1, R2, …, R16. Aceste înregistrări le vom împărți în 8 grupe a câte două, adică (R1, R9), (R2, R10), …. (R8, R16). Sortând fiecare grupă separat, ne va conduce la a doua linie a tabelului; aceasta numindu-se prima trecere. Acum vom împărți înregistrările în câte 4 grupe de câte patru înregistrări fiecare, adică (R1, R5, R9, R16), …., (R4, R8, R12, R16), și din nou fiecare grup este sortat separat. Această a doua trecere ne va conduce la linia a treia. A treia trecere va sorta două grupe de opt înregistrări, apoi o a patra trecere termină treaba sortând toate cele 16 înregistrări. Fiecare din procesele intermediare de sortare, implică fie un fișier relativ scurt, fie un fișier bine ordonat, astfel că inserția directă poate fi utilizată pentru fiecare operație de sortare. Înregistrările tind să conveargă rapid spre destinația lor.
Aici s-a utilizat secvența de incremente 8, 4, 2, 1. Dar poate fi utilizată orice secvență ht, ht-1, …,h1, cu condiția ca ultimul increment h, să fie egal cu 1. De exemplu 7, 5, 3, 1.
Anumite secvențe sunt mai bune ca altele. In program s-a utilizat impartirea sirului considerand h i+1=hi*3+1
Tabelul 3: Sortarea prin micșorarea incrementului (8, 4, 2, 1)
3.2.3.2. PREZENTAREA ALGORITMULUI
Algoritmul E (sortarea cu micșorarea incrementului): Înregistrările R1, R2, …, Rn sunt rearanjate pe loc; după terminarea sortării, cheile vor fi în ordinea K1 ≤ K2 ≤ …. ≤ Kn. Pentru controlul procesului de sortare se utilizează incremenții ht, ht-1,…,h1 se ulilizează pentru controlul procesului de sortare, unde h1 =1; alegerea corectă a incremenților poate micșora semnificativ timpul de sortare. Acest algoritm se reduce la Algoritmul S când t= 1.
Algoritmul E este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul R[n] care conține elemntele sortate.
index = 1
i:=3*index+1
cat_timp i < n executa
index:=i
i:=3*index+1
h=index;
cat_timp h>0 executa
pentru j = h+1, j<n, j=j+1 executa
i = j-h
tmp = r[j]
cat_timp i > 0 executa
daca tmp >r[i] atunci intrerupe_bucla_curenta
altfel
r[i+h] = r[i]
i =i-h
r[i+h] = tmp
h = (h-1)/3
3.2.4. INSERȚII DE LISTE
3.2.4.1. PREZENTAREA METODEI
Una din căile generale cele mai importante pentru a îmbunătăți un algoritm constă în examinarea atentă a structurii sale de date, deoarece reorganizarea structurii de date astfel încât să evite operații redundante, conduce des la îmbunătățiri substanțiale.
Inserția directă implică două operații de bază;
i) parcurgerea unui fișier ordonat pentru a găsi cea mai mare cheie, mai mare sau egală cu o cheie dată;
ii) inserarea unei înregistrări noi într-o anumită parte a fișierului ordonat. Fișierul va fi o listă liniară și algoritmul de sortare cu micșorarea incrementului va manipula această listă ulilizând alocarea secvențială. De aceea va fi necesar să se deplaseze aproximativ jumătate din înregistrări pentru a efectua fiecare operație de inserție. Pe de altă parte, alocarea cu legături este ideală pentru inserție, deoarece trebuie schimbate numai câteva legături. Cealaltă operație, parcurgerea secvențială, este la fel de ușoară în cazul alocării secvențiale. Sunt necesare numai legături unidirecționale deoarece parcurgerea listei are loc întotdeauna în aceeași direcție. Structura de date adecvată pentru inserție directă este o listă liniară cu legături, unidirecțională.
3.2.4.2. PREZENTAREA ALGORITMULUI
Algoritmul F (Inserție de listă) Considerăm că înregistrările R1, R2,…, Rn conțin cheile K1, K2, …, Kn și câmpurile de legătură L1, L2, …, Ln capabile de a conține numere de la 0 până la n. Există un câmp de legătură L0 într-o înregistrare artificială K0 la începutul fișierului. Algoritmul va fixa câmpurile de legătură astfel încât înregistrările să fie legate în ordine crescătoare. Aslfel, dacă p(l), p(2), …, p(n) este permutare stabilă care face Kp(1), Kp(2), …, Kp(n), acest algoritm va da:
L0 =p(1); Lp(t) = p(p+1), pentru 1 ≤ i ≤ n; Lp(n) =0.
Algoritmul F este următorul:
Date de intrare: vectorii R[n], K[n] și L[n]
Date de ieșire: vectorul R[n] care conține elementele sortate.
L[0] = n
L[n] = 0
Pentru j = n-1, j>=1, j = j+1 executa
p=L[0]
q= 0
cheie=k[j]
repeta
daca cheie<=k[p] atunci
L[q]=j
q=L[q]
altfel
q=p
p=L[q]
pana_cand p>0
3.2.5. CONCLUZII
La algoritmul de sortare prin inserție directă s-au făcut comparații și deplasări. Acest algoritm a fost îmbunătățit prin algoritmul de sortare prin inserție binară, care face aproximativ n log2 n comparații și deplasări. Schimbând structura de date, folosind sortarea prin inserție în dublu sens, se micșorează numărul de deplasări la aproximativ . Algoritmul de sortare prin mscșorarea incrementului (metoda lui Shell) reduce numărul de comparații și deplasări la n1.3 (pentru n nu foarte mare). Pentru n → ∞, acest număr poate fi micșorat la n(logn)2. O altă metodă de îmbunătățire a algoritmului de sortare prin inserție directă este de a utiliza o structură de date legală, adică inserția de liste care necesită aproximativ comparații, 0 deplasări și 2n sehimbări de legături.
Combinând aceste metode, adică reducând numărul de comparații la ordinul de nlog2 n, ca în inserția binară, și reducând în același timp numărul de deplasări, ca în inserția de liste, obținem o structură arborescentă. Pentru aceasta se utilizează inserția în dublu sens până când apare necesitatea deplasării unor date. În loc de a efectua deplasarea datelor se inserează un indicator la o altă zonă a memoriei. Această tehnică este aplicată recursiv tuturor articolelor care trebuie inserate în această zonă nouă a memoriei.
3.3. SORTAREA PRIN INTERSCHIMBARE
0 a doua familie importantă de algoritmi de sortare este sortarea prin interschimbare. Algoritmii presupun folosirea unor metode de schimbare sau transpoziție, care interschimbă sistematic perechile de elemente ce nu sunt în ordine, până ce nu mai există astfel de perechi. De exemplu, algoritmul de inserție directă poate fi vizualizat ca o metodă de interschimbare, deoarece înregistrarea j va fi interschimbată cu vecinii săi din stânga, până când ajunge la locul potrivit. Metodele de sortare în care interschimbarea este caracteristica dominantă sunt: sortarea cu interschimbare și selecție (sortarea prin "metoda bulelor"); sortarea cu interclasare și interschimbare (sortare paralelă Batcher); sortarea cu interschimbarea partițiilor ('"sortarea rapidă" a lui Hoare) și sortarea după ranguri cu interschimbare.
3.3.1. SORTARE PRIN METODA BULELOR (BUBBLE SORT)
3.3.1.1. PREZENTAREA METODEI
Este cea mai evidentă cale de sortare prin interschimbare și constă în compararea cheilor K1 cu K2, și interschimbarea înregistrărilor R1, cu R2 dacă cheile nu sunt în ordine, apoi se va face același lucru pentru înregistrările R2. și R3 ,R3 și R4, ș.a.m.d. In timpul acestei secvențe de operații, înregistrările cu cheile cele mari tind să se deplaseze spre dreapta, iar înregistrarea cu cheia cea mai mare va avansa pentru a deveni Rn. Repetarea aeestui proces va pune înregistrările potrivite în pozițiile Rn-1 Rn-2, etc., astfel încât toate înregistrările vor fi sortate.
Tabelul 4 ilustrează această metodă de sortare, aranjând cele șaisprezece chei (219,129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440) corespunzător valorilor. Reprezentarea pe verticală este utiă, deoarece este foarte sugestivă. Metoda se numește "sortare prin metoda bulelor” deoarece elementele mari "se ridică ca niște bule" în poziția lor corespunzătoare, prin contrast cu sortarea prin inserție directă în care elementele se cufundă la un nivel corespunzător.
Tabelul 4: Selecția prin metoda bulelor în acțiune
După fiecare trecere prin fișier se observă că toate înregistrările Superioare, inclusiv ultima care se schimbă, trebuie să se găsească în poziția lor finală, astfel încât să nu mai fie necesară examinarea lor la trecerile următoare. Liniile orizontale arată evoluția sortării din acest punct de vedere. Se observă că la a patra trecere au fost așezate în poziția finală cinci elemente. La ultima trecere nu se execută nici un interschimb.
3.3.1.2. PREZENTAREA ALGORITMULUI
Algoritmul G (sortarea prin metoda bulelor) va sorta înregistrările R1, R2 …;Rn după sortare, cheile vor fi în ordinea K1 ≤ K2 ≤… ≤ Kn.
Algoritmul G este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul R[n] care conține elemntele sortate.
cat_timp not ordonat executa
ordonat =adevarat {Pesupune sirul sortat }
pentru i =1, i<n-1, i = i+1 executa
daca r[i]>r[i+1] atunci
aux:= r[i]
r[i] = r[i+1]
r[i+1] = aux
ordonat = fals {se constata ca sirul nu este sortat }
3.3.1.3. COMPLEXITATEA ALGORITMULUI
Când înregistrările sunt aranjate în ordinea crescătoare a cheilor (cazul cel mai favorabil), se parcurg înregistrările o singură dată și se execută n-1 comparații. Dacă înregistrările sunt aranjate în ordinea descrescătoare a cheilor (cazul cel mai defavorabil), se execută operații de bază, iar înregistrările se parcurg de n ori, deci algoritmul este de ordinul 0(n2) .
3.3.1.4. PERFECȚIONĂRI ALE SORTĂRII PRIN METODA BULELOR
Analiza sortării prin metoda bulelor a condus la concluzia că nu este o metodă foarte bună. Comparând această metodă cu inserția directă se ajunge la concluzia că timpul necesar sortării cu metoda bulelor este dublu, iar programul este mult mai complicat. S-a încercat îmbunătățirea acestuia. Una din metodele găsite a fost ''sortarea prin amestecare” în care trecerile alternate merg în direcții opuse. Numărul mediu de comparații fiind ușor redus. Se parcurg înregistrările în ambele sensuri, ducând spre capetele cele mai mari, respectiv cele mai mici, elemente. K. E. Inverson a efectuat, în legătură cu aceasta, o observabție interesantă: dacă j este un indice astfel încât Rj și Rj+1 nu sunt interschimbate în două treceri consecutive, în direcții opuse, atunci Rj și Rj+1 se găsesc în pozițiile lor finale și nu este necesar să intre în nici una din comparațiile care urmează. Și cu această îmbunătățire algoritmul nu se îmbunătățește în așa fel încât să devină mai eficient decât inserția directă. 0 altă metodă constă în eliminarea celor mai multe interschimbări, deoarece cele mai multe elemente se deplasează simplu spre dreapta, cu un pas, pe durata unui interschimb, putem obține același efect prin cxaminarea diferită a tabloului și anume, deplasând originea de indexare. Algoritmul care rezultă nu este mai bun decât selecția directă.
3.3.2. SORTARE RAPTDĂ (QUICK SORT)
3.3.2.1. PREZENTAREA METODEI
Sortarea rapidă folosește doi indicatori i și j. Inițial i = 1 și j -= n . Se compară cheile Ki și Kj. Dacă interschimbul nu este necesar se micșorează j cu 1 și se repetă procedeul, iar dacă apare un interschimb se mărește i cu 1 și se continuă compararea, mărind i până la aparița unui nou interschimb. Apoi se micșorează din nou j, continuându-se în același mod de "ardere a lumânării la ambele capete” până când i = j .
Considerăm exemplul nostru cu cele șaisprezece numere 219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440.
Se dau numerele:219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440 i = 1, j = l6
– primul interschimb (i = 1, j descrește de la 16 până la 11)
134, 129, 243, 98, 491, 151, 452, 162, 376, 193, 219, 231, 332, 429, 449, 440
– al doilea interschimb (i crește de la 1 la 3, j = l1)
134, 129, 219, 98, 491, 151, 452, 162, 376, 193, 243, 231, 332, 429, 449, 440
– al treilea interschimb (i=3, j descrește de la 11 la 10)
134, 129, 193, 98, 491, 151, 452, 162, 376, 219, 243, 231, 332, 429, 449, 440
– al patrulea interschimb (i crește de la 3 la 5, j = 10)
134, 129, 193, 98, 219, 151,452, 162, 376, 491, 243, 231, 332, 429, 449, 440
– al cincelea interschimb (i = 5, j descrește de la 10 la 8)
134, 129, 193, 98, 162, 151, 452, 219, 376, 491, 243, 231, 332, 429, 449, 440
– al șaselea interschimb (i crește de la 5 la 7, j=8)
134, 129, 193, 98, 162, 151, 219, 452, 376, 491, 243, 231, 332, 429, 449, 440
După acești pași j descrește de la 8 la 7, obținând i = j = 7.
Se observă că fiecare comparație implică cheia 219, deoarece ea va fi modificată odată cu fiecare schimbare d direcție. În momentul în care i = j, înregistrarea originală R1 va fi plasată în poziția finală, deoarece nu vor mai exista chei mai mari la stânga și nici chei mai mici la drepta sa. Fișierul final va fi parționat în așa fel încât problema inițială este redusă la doua probleme mai simple, sortarea R1, R2., …,Ri-1, (independent) sortarea Ri+1, Ri+2,…, Rn. Aceeași tehnică se poate aplica fiecăruia din cele două subfișiere până când vom obține subfișiere suficient de mici.
Această metoda se numește sortare prin interschimb de partiții. Toate comparațiile de la o etapă dată sunt făcute în raport cu aceeși cheie, care trebuie pastrată într-un registru, iar numărul de deplasări făcute este rezonabil. Contabilizarea indicilor i si j nu este dificilă, dar face ca procedura de sortare rapidă prin interschimb de partiții să fie mai convenabilă pentru n mare; de aceea este de dorit să se sorteze subfișiere scurte.
Această metodă a fost publicată de C. A. R. Hoare. Ideea sortării rapide, ca și la sortarea lui Shell, se bazează pe faptul că pentru a atinge o viteză mai bună este de dorit să permute elementele aflate la o distanță, mai mare unul de altul decât 1.
Alegem, în mod arbitrar, un element al fișierului și-l atribuim valoarea cheii variabilei x. Apoi vom parcurge elementele tabloului și vom face permutări de elemente dacă este necesar, așa încât toate elementele mai mici decât x să fie în stânga (indici mai mici), iar cele mai mari în dreapta lui. În felul acesta, în etapa următoare, se poate considera că avem de sortat două subfișiere distincte, unul care conține elemente mai mici decât x și unul care conține elemente mai mari decât x. Aceste subfișiere se sortează și ele prin același procedeu. Se poate considera că acest procedeu constă în divizarea unui tablou în douî parți, așa încât elementele unuia să fie toate mai mici decât elementele celuilalt. De aceea, această metode se mai numește și metoda de interschimb de partiții.
Metoda sortării rapide poate fi realizată ca mai jos:
1. se alege un element oarecare al fișierului, de exemplu elementul aflat la mijiocul fișierului și se atribuie lui x
2. se parcurge fișierul de la primul element și până se găsește un element Ki ≥ x
3. se parcurge subfișierul de la dreapta la stânga până se găsește un element Kj ≤ x
4. se permută între ele elementele Ri cu Rj, dacă i nu-l depășește pe j
5. se continuă pașii 2, 3, 4 de mai sus până se ajunge ca i > j . Când i > j, tabloul este divizat în două.
Pașii de mai sus se continuă apoi, asupra fiecăruia dintre cele două părți în care s-a divizat fișierul inițial. În felul acesta, se divide fiecare parte în două părți, realizându-se o divizare în 4 părți a fișierului inițial și așa mai departe. Divizarea continuă până când fiecare parte conține un singur element. În acest moment, fișierul are elementele sortate în ordine crescătoare a cheilor. Se observe că diviziunea este în mare măsură dependentă de elementul separator ales la fiecare pas. Dacă acesta este chiar elementul minim dintre elementele fișierului supus divizării, atunci prima parte se reduce chiar la acest element. Acestea sunt cazurile cele mai ineficiente deoarece tabloul se divide în așa fel încât una dintre părți conține un singur element. In general, divizările pentru fișiere mari este bine să fie cât mai echilibrate, adică cele două părți să fie de lungimi apropiate. Nu există însa un procedeu simplu care să asigure acest fapt. Alegerea elementului de la mijiocul fișierului este o metodă simplă și destul de practică.
3.3.2.2. PREZENTAREA ALGORITMULUI
Algoritmul H (Sortare prin interschimb de partiții) Înregistrările R1, R2,…, Rn sunt rearanjate pe loc; după terminarea sortării, cheile vor fi în ordinea K1 ≤ K2 ≤ … ≤ Kn.
Algoritmul H este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul R[n] care conține elementele sortate.
În vederea sortării se mai folosește stiva stiva[n], în care vor fi memorate marginile șirurilor. Inițial în stivă se memorează 1 (pentru marginea stângă = inc) și n (pentru marginea dreaptă = sf). De asemenea, mijloc va reține valoarea aflată pe poziția din mijioc în intervalul dintre pozițiile inc și sf.
stiva[1] =1 Stiva[2]=n v =2
repeta
{extragere limite partiale din virful stivei}
sf = stiva[v]
ince=stiva[v-1]
v=v-2
repeta
{partitionarea sirului a[s],…,a[d]}
i=ince
j=sf
mijloc=r[(ince+sf) div 2]
repeta
cat_timp r[i] < mijloc executa i = i+1
cat_timp r[j] > mijloc executa j = j -1
daca i<=j atunci
aux:= r[i]
r[i] = r[j]
r[j]=aux
i=i+1
j=j-1
pana_cand i>j
daca i<sf atunci
v=v+1
stiva[v]=i
v=v+1
stiva[v]=sf
sf=j
pana_cand ince>sf
pana_cand v=0
3.3.2.3. COMPLEXITATEA ALGORITMULUI
Pentru a analiza timpul folosit de algoritm vom evalua numărul de comparații între elememele fișierului, celelalte operații având același ordin de mărime.
Pentru a poziționa elementul Rp în secvența (Rp Rp+1 ,, …, Ru) sunt necesare u-p, p < u, comparații ale valorii inițiale Kp cu celelalte elemente. Dacă fișierul este de la început ordonat crescător, atunci se vor compara succesiv cheile elementelor cuprinse între perechile de indici: (l,n), (2,n), …, (n-1,n), ceea ce necesită (n-1)+(n – 2)+…+2+1 = comparații. Deci, în cazul cel mai defavorabil, algoritmul este de ordinul 0(n2).
Calculăm valoarea medie a numărului de comparații, notând prin T(n) numărul mediu de comparații pentru ordonarea unei secvențe de lungime n. În acest caz, poziționarea primului element pe oricare dintre cele n, poziții presupunând aceste cazuri echiprobabile, determină obținerea următoarei formule de recurență;
T(n)=n-1+, (1)
unde T(1)=T(0)=0
În continuare se obține succesiv:
nT{n)=n(n-1)+2[T(0)+T(1)+…+T(n-1)] (2)
Scriem această relație pentru n – 1;
(n-1)T(n-1) = (n-1)(n-2) + 2[T(0) + T(1) + … + T(n-2)] (3)
Scăzând relația (3) din (2), ajungem la
nT(n)-(n-1)T(n-l)=2(n-1)+2T(n-1) => nT(n)=(n+1)T{n-1)+2(n-1)=>
=> =+ =>
=>
= ≤ 2[] = 2 ≤ 2
Deci T(n)< 2(n+ l)ln(n+l), adică T(n)= O(n lnn).
3.4. SORTAREA PRIN SELECȚIE
0 altă familie importantă de tehnici de sortare este bazată pe ideea selecției repetate Cea mai simplă metodă de selecție este probabil urmatoarea; se alege cea mat mică cheie, se transferă înregistrarea corespunzătoare către ieșire, după care se înlocuiește cheia prin valoarea ∞ Se repetă operația anterioară selectându-se cea mai mică cheie (adică următoarea ca mărime, pentru că prima cheie a fost notată cu ∞). Continuăm procedeul până când toate cele n înregistrări au fost selectate. Această metodă presupune că toate elementele de intrare să fie cunoscute înainte de începerea sortării și sunt generate datele finale de ieșire, una după aila, în secvențe. Acesta este deosebirea esențială între această metodă și sortarea prin inserție, unde intrările se primesc secvențial, dar nu se știe nimic despre ieșiri, până când sortarea nu este completă.
3.4.1. SORTARE PRIN SELECȚIE DIRECTĂ
3.4.1.1. PREZENTAREA METODEI
Sortarea prin selecție directă folosește algoritmul descris anterior. Ea implică n-1 comparații de fiecare dată când o nouă înregistrare este selectată și, de asemenea, necesită un spațiu separat cu memorie pentru datele de ieșire. Există metode prin care se ameliorează acest neajuns, evitând utilizarea lui "∞". Se ia valoarea selectată și se mută într-o poziție adecvată ei, prin interschimbarea ei cu înregistrarea curentă care ocupă acea poziție, nemaifiind necesar să considerăm această poziție în selecțiile viitoare.
3.4.1.2. PREZENTAREA ALGORITMULUI
Algoritmul I (sortarea prin selecție directă) va sorta înregistrările R1, R2, …, Rn; după sortare, cheile vor fi în ordinea K1 ≤ K2 ≤ …≤ Kn,. Sortarea se bazează pe metoda prezentată anterior, exceptând faptul că acest algoritm demonstrează că este mai convenabil să se selecteze la început elementul cel mai mare, apoi al doilea element cu valoarea cea mai mare și așa mai departe.
Exemplificăm sortarea prin selecție directă pe cele șaisprezece chei (219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440).
Tabelul. 5: Sortarea prin selecție directă
Algoritmul I este următorul;
Date de intrare: vectorii R [n] ;i K[n]
Date de ieșire: vectorul R [n] care conține elemntele sortate.
pentru j =n, j>=2, j = j – 1 executa
max =r[j]
p =j
pentru i =j-1, i>=1, i=i-1 executa
daca r[i] > max atunci
max=r[i]
p=i
aux=r[p]
r[p]=r[j]
r[j]=aux
3.4.1.3. COMPLEXITATEA ALGORITMULUI
Lemă:
Orice algoritm pentru găsirea maximului din n elemente, bazat pe compararea perechilor de elemente, trebuie să facă cel puțin n-1 comparații.
Demonstrație: Presupunem că se fac mai puțin de n-1 comparații, rezultă că cel puțin două elemente care nu vor fi găsite niciodată ca fiind mai mici decât oricare altele. De aceea, nu vom ști niciodată care din aceste două elemente este mai mare și nu putem determina maximul.
În aceste condiții, procesul de selecție, care află elementuș cel mai mare, trebuie să aibă cel puțin n-1 pași. Această lemă se aplică doar la primul pas, la următorii pași ne putem folosi de informațiile obținute anterior. Cu toate acestea, numărul de comparații poate fi redus la jumătate.
Considerând cele 16 numcere (219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440), o metodă prin care se poate economisi timp în selecția repetată este de a privi aceste numere sub forma a 4 grupe câte 4. Se poate începe prin determinarea elementului cel mai mare din fiecare grupă. Astfel obținem: 243 (cel mai mare număr dintre 219, 129, 243, 98), 491 (cel mai mare număr dintre 491, 151. 452, 162), 376 (cel mai mare număr dintre 376, 193, 134, 231), 449 (cel mai mare număr dintre 332, 429,449, 440). Cel mai mare dintre cele 4 elemente, 491, este cel mai mare din întregul fișier. Pentru a obține numărul secund cel mai mare este nevoie numai să comparăm celelalte trei elemente din grupa care-l conține pe 491, adică dintre 151, 452, 162 și-1 găsim pe 452, iar cel mai mare dintre 243, 452, 376, 449 este 452. Se continuă asemănător pentru a obține al treilea element ca valoare. Fiecare nouă selecție după cea dintâi are cel mult 6 comparații suplimentare. În general, dacă n este un pătrat perfect, pentru împărțirea fișierului în grupe de elemente fiecare, nouă selecție, după prima, are cel mult comparații în grupa elementului selectat anterior, plus comparații în "grupa liderilor". Aceasta se numește selecție pătratică, timpul total de execuție este O, care este substanțial mai bun decât n2.
Selecția pătratică a fost publicată prima dată de E.H. Friend care a scos în evidență că ideea poate fi generalizată la cub perfect, etc. Selecția cubică împarte fișierul în grupe mari, fiecare conținând grupe mici, fiecare conținând înregistrări; timpul de execuție este proportional cu n. În acest mod ajungem la selecția de gradul n bazată pe structura arborelui binar. Această metodă are un timp de execuție proportional cu n log n și se numește selecție arborescentă.
3.4.2. SELECȚIA ARBORESCENTĂ
3.4.2.1. PREZENTAREA METODEI
Principiile sortării prin selecție arborescentă sunt ușor de înțeles gândindu-ne la meciurile dintr-un turneu prin eliminare.
Deci, daca sunt 8 jucatori (a, b, c, d, e, f, g si h) si rezultatele ar fi cele din figura de mai jos, jucatorul A, este campionul dintre cei 8 jucatori, si au fost necesare 7 meciuri. Jucatorul E, nu este neaparat cel mai bun jucator dupa C, deoarece oricare dintre jucatorii batuti de C, poate fi mai bun decat E. Se poate determina al doi-lea jucator prin rezultatul jocului D-A si rezultatul dintre castigatorul meciului de mai sus si jucatorul E; deci sunt necesare doar doua jocuri pentru a gasi ocupantul locului doi.
Tabel 6: Tabloul meciurilor de la o competiție de tenis feminin
Tabelul 6 ne arată că la competiție au participat 8 jucători și au fost necesare 7 (=8-1) meciuri (în cazul nostru comparații), pentru a determina câștigătorul. În general se poate scoate jucătorul prin rădăcina arborelui și înlocui cu cel mai slab jucător. Substituind acest jucător slab, înseamnă că al doilea jucător bun va fi acum cel mai bun, astfel că el va apare în rădăcina arborelui, dacă se recalculează învingătorii din nivelele superioare ale arborelui. În acest scop trebuie schimbată, numai o parte a arborelui astfet că sunt necesare mai puțin de [nlogn] comparații. pentru selectarea următorului jucător bun. Timpul total pentru o astfel de sortare prin selecție este direct proporțional cu [nlogn].
Acțiunea de sortare prin selecție arborescentă pentru cele 16 numere (219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440). Este necesar să se cunoască de unde vine cheia în rădăcina, în scopul cunoașterii locului în care se introduce "−∞" următor. Astfel, nodurile de ramificare a arborelui actual, conțin un indicator sau index, care specifică poziția cheii semnificative, în locul cheii însăși. De aici decurge faptul că este necesar un spațiu în memorie pentru n înregistrări de intrare, n-l cuvinte pentru indicator și înregistrări de ieșire.
Figura 1: Sortarea prin selecție arborescentă
(a) Configurația inițială
\
(b) 491 este înlocuit de către -∞, și următorul element în ordinea mărimii se deplasează în sus către rădăcină.
(c) Configurația după ce 491, 452, 449, 440, 429, 376, 332
Pentru a simplifica selecția arborescentă, K.. E. Iverson este de a renunța la indicatori anticipând în modul următor: când câștigătorul meciului din nivelul de la bază a arborelui este deplasat mai sus, el poate fi înlocuit imediat cu "-∞", la nivelul de bază; când câștigătorul se deplasează mai sus de la o ramură la alta, putem să-1 înlocuim prin acela care eventual, ar fi fost deplasat mai sus în locul lui inițial (adică cheia mai mare din cele două chei de dedesubt).
Repetând această operație obținem figura 2.
Figura 2: Principiul lui Peter la sortare. Fiecare element se ridică în ierarhie până la nivelul său de competență..
Odată ce arborele a fost realizat în această formă, putem trece la sortare prin metoda "de la vârf în jos" în locul metodei "de la bază în sus din figura l se scoate rădăcina, se mișcă în sus descendentul cel mai mare, se mișcă în sus următorul descendent cel mai mare, etc. Acest procedeu arată ca un sistem de promovare în cadrul unei competiți.
Se observă că metoda "de la vârf în jos" are avantajul că pot fi evitate comparațiile redundante pentru "− ∞" cu "− ∞". La metoda "de la bază în sus" se tot găsește "− ∞" în ultimele stadii ale sortării, dar abordarea prin metoda "de la vârf in jos" poate opri modificarea arborelui pe parcursul fiecărui stadiu, de câte ori a fost sortat"− ∞".
3.4.3. SORTAREA PRIN ANSAMBLE (HEAPSORT)
Arborii din figura 1 și figura 2 sunt arbori binari compleți cu 16 noduri terminale și se preferă să se reprezinte un astfel de arbore în locații consecutive, după cum este prezentat în figura 3. Se observă că tatăl nodului k este nodul și nodurile afiliate lui sunt nodurile 2k și 2k +1. Acesta conduce la un alt avantaj în abordarea metodei vârf – bază deoarece, adesea, este mai simplu să mergi vârf – bază de la nodul k la nodurile 2k și 2k +1, apoi de la bază în sus, de la nodul k, la nodul k +1 (dacă k este par) sau k – 1 (dacă k este impar) și .
Figura 3:
Exemplul pe care l-am dat a fost pentru n putere a lui 2, dar se poate lucra și pentru n arbitrar, deoarece arborele binar complet cu n noduri terminale este gata construit pentru orice n. Se pune problema utilizării metodei vârf – bază fără să utilizăm "− ∞" sau a găsirii unei metode prin care toate elementele să fie în locațiile de la 1 la 16, ale arborelui binar complet, fără a utiliza „− ∞". Algoritmul de sortare prin ansamble, care face posibilă rezolvarea problemei amintite, precum și sortarea a n înregistrări, fără un spațiu auxiliar pentru ieșiri.
3.4.3.1. PREZENTAREA METODEI
Se spune că un fișier de chei K1, K2,…, Kn reprezintă un ansamblu dacă: . pentru 1 ≤ < j ≤ n. Aceasta înseamnă K1, ≥ K2, K1 ≥ K3, K2 ≥ K4, etc. Această condiție se observă și în figura 2 care înseamnă că cheia cea mai mare a ansamblului, să apară în vârful ansamblului, K1 = max(K1, K2,…, Kn). Dacă putem transforma într-un fel oarecare un șir de intrare într-un ansamblu, putem utiliza procedura de selecție vârf-bază descrisă mai sus pentru a obține un algoritm eficient de sortare.
0 metodă eficientă pentru crearea ansamblului a fost sugerat de R.W. Floyd. Să presupunem că putem să aranjăm un fișier astfel încât pentru l < , unde l ≥ 1 este un număr oarecare.
Defnim noțiunea de ansamblu ca fiind un arbore binar care satisface următoarele proprietăți:
i) rădăcina se notează cu 1;
ii) dacă un nod i are descendenți, aceștia sunt notați: 2i descendentul din stânga 2i + 1 descendentul din dreapta;
iii) valoarea cheii oricărui nod este mai mare sau egală cu cea asociată descendenților săi (dacă aceștia există).
La sortarea cu ansamble sunt două faze: construirea ansamblului și corectarea ansamblului.
În prima fază, pornim de la cheia K1, care poate fi privită ca un ansamblu și adăugăm pe rând câte un element, K2 …, Kn,, la fiecare adăugare efectuând o’’înglobare’’ a unui element la un ansamblu deja existent, și deci creând un nou ansamblu conținând un element în plus. Tehnica de "înglobare'' presupune un șir de verificări, elementul adăugat i (care conține cheia Ki fiind descendentul nodului . Dacă acest element satisface față de părintele său condiția iii) din definiția ansamblului, înglobarea este terminată, dacă nu, apare necesar un șir de schimbări de valori pe verticală, urmate de noi verificări, între descendenți și părinți, până ce condiția este satisfăcută sau s-a făcut o ultimă schimbare între nodul 1 și un descendent al său. Se observă că schimbările pe verticală, pe langă faptul că ele colectează o relație "eronată" între noduri în ierarhia lor, nu deteriorează ceea ce era deja corect pe alte trasee ce leagă noduri aflate pe nivele succesive, pentru că urcă valori mai mari care vor satisface cu atât mai mult relația iii).
A doua fază se folosește pentru a deplasa elementele pe locul lor definitiv în ordine crescătoare și când, utilizând o deplasare de sus ân jos, un element care a fost adus în nodul rădăcină și care nu îndeplinește condiția iii) față de vreunul din descendenții săi, trebuie deplasat la locul sau în arbore. Dacă am ajuns cu ajustarea în nodul i (inițial i este l), mai întâi verificăm dacă nodul i are descendenți; dacă are doi, îl determinăm pe acela dintre frați care conține cea mai mare valoare, apoi verificăm condiția iii). pentru nodul i și descendentul determinat. Dacă relația este salisfăcută, corectarea este terminată, iar dacă nu, se face scbimbarea pe verticală între două valori asociate celor două noduri și se continuă analog luând acum ca nod părinte descendentul determninat anterior pentru nodul i și ca descendent demn de luat în seamă, pe acela care există, dacă există ambii descendenți. Procesul se termină fie când condiția iii) este satisfăcută, deci ansamblul e realizat, fie când un nod nu mai are descendent în subșirul considerat la pasul respectiv.
3.4.3.2. PREZENTAREA ALGORITMULUI
Algoritmul L (sortarea de ansamblu) ordonează înregistrările R1, R2, …, Rn. După ce sortarea este completă, cheile vor fi în ordinea K1 ≤ K2 ≤ … Kn. La început rearanjăm fișierul astfel încât să formeze un ansamblu, apoi repetăm înlocuirea vârfului ansamblului și îl transferăm în poziția lui finală. Presupunem că n ≥ 2
Algoritmul L este următorul:
Date de intrare: vectorii R[n] și K[n]
Date de ieșire: vectorul R[n] care conține elementele sortate.
Pentru j = 2, j<= n, j = j+1 executa
C=j
p =[c/2]
Cat_limp p >= 1 executa
Daca K[c] > K[p] atunci
aux = R[c]
R[c] =R[p]
R[p]= aux
c=p
p =c/2
altfel p=0
pentru i = 1, i<=n, i=i+1 executa
aux = K[l]
K[1| = K[i]
K[i]=aux
p=1
c=2
Cat_timp c<=i-1 executa
Daca (c +1<=i -1) si (K[c + l] > K[c]) atunci c= c + 1
Daca K[c] > K[p] atunci
aux= R[c]
R[c]=R|p]
R[p]=aux
p =c
c =2p
altfel c=i
3.4.3.3. COMPLEXITATEA ALGORITMULUI
Pentru analiza complexității presupunem 2k < n < 2k+1, iar cazul n = 2k se tratează analog. În acest caz, ansamblul are k+1 nivele, numerotate începând cu 0. În faza de constituire a ansamblului, fiecare element Ri, situat pe nivelul j, urcă în arbore cel mult k+1-j nivele. Cum pe fiecare nivel j se găsesc 2j elemente, rezultă că pentru elementul Ri se fac cel mult k+1-j comparații. Numărul maxim de comparații între elementele șirului dat este E =1∙2' +2∙22 +3∙23 +…+ k∙2k = k∙2k+1 -2k+1. Logaritmând în dubla inegalitate 2k < n < 2k+1, obținem k < log2 n <k+1, adică avem k = [log2n]. În concluzie, E = 2∙k∙2k+1 – 2k +1 < 2∙n∙[log2n] – și E > n∙[log2n]-n +1, adică timpul cerut de construcția ansamblului este de ordinul O(n∙log2n).
Analog se deduce că timpul cerut în etapa a doua, care include n ajustări ale ansamblului, este de ordinul O(n∙log2n).
Algoritmul este de complexitate O(n∙log2n).
3.5. ALȚI ALGORITMI DE SORTARE
3.5.1. SORTARE FOLOSIND METODA BACTRACKING
3.5.1.1. PREZENTAREA METODEI
Algoritmul presupune folosirea metodei bactracking în sortarea unui vector. Metoda bactracking se poate aplica problemelor în care soluția poate fi exprimată sub forma de vector x = (x1, x2,…,xn), unde xi Є Ai, cu 1 ≤ i ≤ n, iar mulțimile A1, A2,…, An trebuie să fie finite. Pentru aceasta se folosește noțiunea de stiva. Rezolvarea problemei se poate face generând toate soluțiile produsului cartezian A1xA2x…xAn și se elimină toate elementele acestui produs care nu satifac codițiile problemei. Acest lucru este greoi, deci ineficient.
Metoda backtracking constă în următoarele:
– se alege primul element x1, din mulțimea A1;
– presupunând generate elementele x1, x2,…, xn, aparținând mulțimilor A1, A2, …,Ak se alege (dacă există) xk+1, primul element disponibil din mulțimea Ak+1 care îndeplinește anumite condiții de continuare. Apar astfel două posibilități:
i) elementul există, și-atunci se testează dacă nu s-a ajuns la o soluție, iar în caz afirmativ acesta se tipărește, în caz contrar se consideră generate x1, x2,…, xk, xk+1;
ii) elementul nu există, situație în care se consideră generate elementele x1, x2,…, xk-1, reluându-se căutarea de la elementul următor xk în mulțimea Ak;
– algoritmul se încheie când au fost luate în considerație toate elementele mulțimii A1.
Implementarea acestei metode se poate face utilizând structura de stivă. Astfel, elementele x1, x2,…, xk-1, ni le imaginăm într-o stivă. Găsirea elementului xk+1 determinară urcarea în stivă pe nivelul k+1, în caz contrar se coboară la nivelul k-1. Algoritmul se incheie când s-a ajuns la nivelul O în stivă.
3.5.1.2. IMPLEMENTAREA METODEI
Algoritmul M (sortarea prin metoda bactracking) va sorta vectorul a = (a1, a2,…., an); după sortare, se va obține ordinea elementelor.
Algoritmul M este următorul.
Date de intrare: vectorul a[n]
Date de ieșire: vectorul x[n] care conține ordinea elemnteor sortate.
program ordonare; {metoda backtracking}
uses wincrt;
type stiva=array[1..100] of integer;
var x:stiva; n,k,i:integer; esuc:boolean;
a:array[1..100] of integer;
procedure tipar(x:stiva; n:integer);
var i: integer;
begin
for i:=1 to n do write(a[x[i]]:7);
writeln;
end;
function continuare(var x:stiva; k:integer):boolean;
var i:integer;
begin
continuare:=true;
if(k>1) and (a[x[k-1]]>=a[x[k]]) then continuare:=false;
end;
begin
write('n='); readln(n);
writeln('sirul A:');
for i:=1 to n do readln(a[i]);
x[1]:=0;k:=1;
while k>0 do
begin
esuc:=false;
while (x[k]<n) and (not esuc) do
begin
x[k]:=x[k]+1;
if continuare(x,k) then esuc:=true;
end;
if not esuc then k:=k-1
else
if k=n then tipar(x,n)
else
begin
k:=k+1;x[k]:=0;
end;
end;
readln;
end.
3.5.1.3. COMPLEXITATEA ALGORITMULUI
Algoritmul este de complexitate O(n2). În aceste condiții, algoritmul nu este foarte eficient, interesantă este aplicarea metodei backtracking.
3.5.2. SORTARE FOLOSIND LISTELE SIMPLU ÎNLĂNȚUITE
3.5.2.1. PREZENTAREA METODEI
Această metodă presupune crearea unei liste înlănțuită care conține niște numere nr și informația de legătură urm. Am sortat numerele din listă, crescător după nr prin modificarea legăturilor dintre articolele listei în cazul în care este necesară interschimbarea acestora. De asemenea afișează articolele din lista.
3.5.2.2. IMPLEMENTAREA METODEI
Algoritmul M (sortarea listelor) sortează crescător elementele unei liste prin modificarea legăturilor. Se lucrează cu liste alocate dinamic.
Algoritmul M este următorul;
Date de intrare: lista.
Date de ieșire: lista care conține elementele sortate.
{
sa se creeze o lista inlantuita care contine niste numere: nr, urm
sa se ordoneze numerele din lista crescator dupa NR prin modificarca legaturilor dintre articolele listei in cazul in care este necesara interschimbarea
sa se afiseze articolele din lista sortata
}
program sortarelista;
uses wincrt,Windos;
type lista=^nod;
nod=record
nr:integer;
urm:lista;
end;
var prim,ultim:lista;
procedure creare_lista;
var nou:lista; ch:char;
begin
prim:=nil;
repeat
write ('Introduceti un numar(d/n): ');readln(ch);
if upcase(ch)='D' then
begin
new(nou);
write('Numarul este:'); readln(nou^.nr);
nou^.urm:=nil;
if prim=nil then prim:=nou
else ultim^.urm:=nou;
ultim:=nou;
end
until upcase(ch)='N';
end;
procedure afisare_lista;
var p:lista;
begin
writeln('lista este:');
p:=prim;
while p<>nil do
begin
write(p^.nr:5);
p:=p^.urm;
end;
writeln;
writeln;
end;
procedure sortare_lista;
var v:boolean;el1,el2,anterior,posterior:lista;
begin
repeat
v:=true;
{initial}
anterior:=nil; el1:=prim; el2:=el1^.urm; posterior:=el2^.urm;
{gata initial}
while el2<>nil do
begin
if el1^.nr>el2^.nr then
begin
{interschimbul}
if anterior=nil then prim:=el2 else anterior^.urm:=el2;
el1^.urm:=posterior;
el2^.urm:=el1;
v:=false;
end;
{i devine i+1 de la siruri}
if anterior=nil then anterior:=prim
else anterior:=anterior^.urm;
el1:=el1^.urm;
el2:=el2^.urm;
if posterior<>nil then posterior:=posterior^.urm;
end
until v;
end;
begin
creare_lista;
afisare_lista;
sortare_lista;
afisare_lista;
readln;
end.
Capitolul 4
SORTAREA EXTERNĂ
Sortarea fișierelor este în general înțeleasă ca un proces de rearanjare a datelor unei mulțimi într-o ordine anumită. Sortarea se face în scopul facilității accesului ulterior la elementele mulțimii sortate, motiv pentru care este folosită în domenii diverse: numele din cartea de telefon sunt aranjate în ordine alfabetică, cărțile dintr-o bibliotecă sunt aranjate tot în ordine lexicografică ș.a.m.d. Deoarece volumul de date care se dorește să fie sortat este uneori mare, este necesară stocarea datelor în fișiere. Sortarea fișierelor necesită o astfel de strategie față de cea folosită la sortarea intenă, de exemplu a tablourilor.
Algoritmii de sortare intenă nu pot fi folosiți în cazul în care volumul de date de sortat nu poate fi stocat în memoria internă, ci doar în memoria externă, în fișiere. În acest caz, datele se consideră ca fiind organizate în fișiere secvențiale, care se caracterizează prin aceea ca la un moment dat nu se poate face acces decât la un element și numai unul. Această restricție este foarte drastică comparativ cu posibilitățile oferite de structurile de tip tablou. Iată de ce sunt necesare alte tehnici de sortare.
Cea mai importantă tehnică de sortare este cea prin interclasare. Interclsarea presupune combinarea a două sau mai multe secvențe ordonate într-o sigură secvență ordonată, prin selectarea repetată a unor secvențe care fuzionează. Interclasarea este o operație mult mai simplă decât sortarea propriu-zisă, fiind folosită doar ca o operație auxiliară în cadrul procesului de sortare externă.
4.1. SORTAREA PRIN INTERSCHIMBARE A FIȘIERELOR
4.1.1. PREZENTAREA METODEI
În cazul în care un limbaj permite accesul direct la înregistrările unui fișier organizat secvențial, sortarea acestuia se poate face folosind metodele de sortare internă cunoscute.
Voi prezenta în continuare implementarea algoritmului de creare, sortare și afișare a unui fișier în acces direct. Sortarea se bazează pe metoda interschimbării directe cu santinelă, singura deosebire fiind că lungimea fișierului nu este cunoscută aprioric.
Pentru a putea realiza sortarea unui fișier este necesar ca procedura sortarefisier care va realiza acest lucru să fie integrată în mediu.
Sortarea prin interschimbare impune necesitatea parcurgerii fișierului de la un capăt la altul acest lucru realizându-se printr-o buclă infinită. Interschimbarea a două elemente vecine necesită localizarea acestora, prin intermediul procedurii seek, iar în cazul în care nu sunt în ordinea dorită, se realizează mai întâi scrierea celui de-al doilea, apoi al primului.
4.1.2. PREZENTAREA IMPLEMENTĂRII METODEI
Algoritmul N (sortarea prin interschimbar a înregistrărilor) va sorta un fișier în care
o înregistrare a fișierului are tipul întreg.
Algoritmul N este următorul;
Date de intrare: fișierul
Date de ieșire: același fișier care conține înregistrările sortate.
program sortareinfisier;
uses wincrt;
var f:file of integer;
procedure crearefisier;
var nr:integer;
begin
rewrite(f);
write('dali nr<>0: '); readln(nr);
while nr<>0 do
begin
write(f,nr);
write('dati m-<>0:'); readln(nr);
end;
close(f);
end;
procedure afisarefisier;
var nr:integer;
begin
reset(f);
while not eof(f) do
begin
read(f,nr);
write(nr:4);
end;
writeln;
end;
procedure sortarefisier;
var v:boolean;
nr1,nr2,n,i:integer;
poz:word;
begin
reset(f);
n:=filesize(f);
repeat
v:=false;
for i:=1 to n-1 do
begin
read(f ,nr1,nr2);
if nr1 > nr2 then
begin
poz:=filepos(f);
seek(f,poz-2);
write(f,nr2,nr1);
v:=true;
end;
poz:=filepos(f);
seek(f,poz-1);
end;
seek(f,0);
until not v;
end;
begin
clrscr;
assign(f,'numere.dat');
crearefisier;
afisarefisier;
sortarefisier;
afisarefisier;
readln;
end.
ANEXA
program Sortare;
{R+}
uses wincrt,winprocs;
const Max=1000;
sortare_sir:array[1..9] of string=
('sortare prin numararea comparatiilot ',
'sortare prin numararea distributiilor',
'sortare prin insertie directa',
'sortare prin insertie binara',
'sortare folosind metoda Shell',
'sortare prin metoda bulelor',
'sortare folosind algoritnul QuckSort',
'sortare prin selectie directa',
'sortare folosind algoritmul HeapSort');
type
stiva=array[1..10000] of integer;
sir=array[1..Max] of integer;
timp_executie=array[1..20] of integer;
var
r:sir;
Range:integer;
n:integer;
t:timp_executie;
start,stop:integer;
tim:integer;
{***************************************}
function timp:integer;
begin
timp:=gettickcount;
end;
{***************************************}
procedure generare_vector(var r:sir; n:integer; range:integer);
var i:integer;
begin
randomize;
for i:=1 to n do
r[i]:=random(range);
end;
{***************************************}
procedure afisare_vector(n:integer);
var i:integer;
begin
for i:=1 to n do
writeln('r[',i,']=',r[i]);
end;
{***************************************}
procedure sortare_numararea_comp(r:sir;n:integer;var t:integer);
var
aux,count:sir;
i,j:integer;
begin
start:=timp;
for i:=1 to n do count[i]:=0;
for i:=1 to n do
for j:=i to n do
if r[j]>r[i] then inc(count[j])
else inc(count[i]);
for i:=1 to n do aux[count[i]]:=r[i];
r:=aux;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_numararea_distributiilor(r:sir;n:integer;var t:integer);
var
y,count:sir;
i,j:integer;
u,v:integer;
begin
start:=timp;
u:=r[1];
v:=r[1];
for i:=2 to n do
if u>=r[i] then u:=r[i]
else if v<r[i] then v:=r[i];
for i:=u to n do count[i]:=0;
for j:=1 to v do inc(count[r[j]]);
for i:=u+1 to v do count[i]:=count[i]+count[i-1];
for j:=n downto 1 do
begin
i:=count[r[j]];
y[i]:=r[j];
count[r[j]]:=i-1;
end;
r:=y;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_prin_insertie_directa(r:sir;n:integer;var t:integer);
var
i,j:integer;
element:integer;
begin
start:=timp;
for j:=1 to n do
begin
element:=r[j];
i:=j-1;
while(i>=1)and(r[i]>element)do
begin
r[i+1]:=r[i];
i:=i-1;
end;
r[i+1]:=element;
end;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_insertie_binara(r:sir;n:integer;var t:integer);
var
i,j:integer;
element:integer;
inceput:integer;
sfarsit:integer;
mijloc:integer;
begin
start:=timp;
for i:=2 to n do
begin
element:=r[i];
inceput:=1;
sfarsit:=i-1;
while(inceput<=sfarsit)do
begin
mijloc:=(inceput+sfarsit)div 2;
if element<r[mijloc] then sfarsit:=mijloc-1
else inceput:=mijloc+1;
end;
for j:=i downto inceput+1 do r[j]:=r[j-1];
r[inceput]:=element;
end;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_Metoda_Shell(r:sir;n:integer;var t:integer);
var
i,j,h,index:integer;
val:integer;
max,aux:integer;
flag:boolean;
tmp:integer;
begin
index:=1;
i:=3*index+1;
while i < n do
begin
index:=i;
i:=3*index+1;
end;
h:=index;
while h>0 do
begin
for j:=h+1 to n do
begin
i:=j-h;
tmp :=r[j];
while i > 0 do
if tmp >r[i] then break
else
begin
r[i+h] := r[i];
i:=i-h;
end;
r[i+h] := tmp
end;
h:=round((h-1)/3);
end;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_prin_metoda_bulelor(r:sir;n:integer;var t:integer);
var
aux:integer;
i:integer;
ordonat:boolean;
begin
start:=timp;
while not ordonat do
begin
ordonat:=true;
for i:=1 to n-1 do
if r[i]>r[i+1] then
begin
r[i]:=r[i+1];
r[i+1]:=aux;
ordonat:=false;
end;
end;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_QSort(r:sir; n:integer; var t:integer);
var
stiva:sir;
v:integer;
aux,sf,i,j,mijloc,ince:integer;
begin
stiva[1]:=1; Stiva[2]:=n ;v:=2;
repeat
{extragere limite partiale din virful stivei}
sf:=stiva[v];
ince:=stiva[v-1];
v:=v-2;
repeat
{partitionarea sirului a[s],…,a[d]}
i:=ince;
j:=sf;
mijloc:=r[(ince+sf) div 2];
repeat
while r[i] < mijloc do i:=i+1;
while r[j] > mijloc do j:=j-1;
if i<=j then begin
aux:=r[i];
r[i]:=r[j];
r[j]:=aux;
i:=i+1;
j:=j-1
end
until i>j;
if i<sf then begin
v:=v+1;
stiva[v]:=i;
v:=v+1;
stiva[v]:=sf;
end;
sf:=j;
until ince>sf;
until v=0;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure sortare_selectie_directa(r:sir; n:integer; var t:integer);
var i,j,p,max,aux:integer;
begin
start:=timp;
for j:=n downto 2 do
begin
max:=r[j];
p:=j;
for i:=j-1 downto 1 do
if r[i]>max then
begin
max:=r[i];
p:=i;
end;
aux:=r[p];
r[p]:=r[j];
r[j]:=aux;
end;
stop:=timp;
t:=stop-start;
end;
{***************************************}
procedure heap_sort(r:sir; n:integer; var t:integer);
var
i,j,c,p,aux:integer;
begin
start:=timp;
for j:=2 to n do
begin
c:=j;
p:=c div 2;
while p>=1 do
if r[c]>r[p] then
begin
aux:=r[c];
r[c]:=r[p];
r[p]:=aux;
c:=p;
p:=c div 2;
end
else p:=0;
end;
for i:=n downto 2 do
begin
aux:=r[1];
r[1]:=r[i];
r[i]:=aux;
p:=1;
c:=2;
while c<=i-1 do
begin
if (c+1<i-1) and (r[c+1]>r[c]) then c:=c+1;
if r[p]<r[c] then
begin
aux:=r[c];
r[c]:=r[p];
r[p]:=aux;
p:=c;
c:=2*p;
end
else c:=i;
end;
end;
stop:=timp;
t:=stop-start;
end;
begin
write('Dati nr. de elemente ce trebuiesc sortate n='); readln(n);
write('Dati intervalul 0..n= 0..'); readln(Range);
generare_vector(r,n,Range);
{SORTARE VECTOR:}
sortare_numararea_comp(r,n,t[1]);
sortare_numararea_distributiilor(r,n,t[2]);
sortare_prin_insertie_directa(r,n,t[3]);
sortare_insertie_binara(r,n,t[4]);
sortare_Metoda_Shell(r,n,t[5]);
sortare_prin_metoda_bulelor(r,n,t[6]);
sortare_QSort(r,n,t[7]);
sortare_selectie_directa(r,n,t[8]);
heap_sort(r,n,t[9]);
clrscr;
afisare_vector(n);
for tim:=1 to 9 do
writeln('Timpul aferent sortarii ',sortare_sir[tim],' este :',t[tim],'milisecunde');
end.
{***************************************}
{***************************************}
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Algoritmi de Sortare. Caracteristici Si Clasificare (ID: 149034)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.