Algoritmi de Sortare prin Comparare
Algoritmi de Sortare prin Comparare
2
Cuprins Cuprins................................................................................................................................ 2 Cuvând de deschidere ......................................................................................................... 3 Problema ............................................................................................................................. 3 Bubble Sort ......................................................................................................................... 4 Insertion Sort....................................................................................................................... 5 Merge Sort .......................................................................................................................... 6 Quicksort............................................................................................................................. 8 Heapsort ............................................................................................................................ 10
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
3
Cuvând de deschidere În acest material se vor găsi implementările Pascal a 5 algoritmi de sortare prin comparare: bubble sort, insertion sort, merge sort, quicksort şi heapsort. Ei vor fi grupaţi după simplitatea şi înrudirea lor ca metodă de rezolvare. Pentru claritatea codului toţi algoritmii vor opera asupra unei variabile globale.
Problema Problema constă în introducerea de la tastatură a unui şir de numere întregi în ordine aleatoare, sortarea acestuia folosind unul din cei 5 algoritmi şi afişarea pe ecran a şirului introdus în ordine crescătoare. În majoritatea cazurilor se va folosi o variabilă globală de tipul TArray, numai pentru heap sort folosindu-se o structură numită THeap care este în esenţă structura TArray însă are adăugat câmpul heapsize. type TArray=record data:array[1..100] of integer; length:integer; end; type THeap=record data:array[1..100] of integer; length:integer; heapsize:integer; end;
Variabila globală asupra căreia se lucrează este a. var a:TArray; var a:THeap;
Citirea de la tastatură a lungimii şirului şi a elementelor sale se face cu procedura de mai jos: procedure reada; var i:integer; begin repeat write('Number of elements: '); readln(a.length); until (a.length>=1) and (a.length<=100); for i:=1 to a.length do begin write('a[',i,']='); readln(a.data[i]); end; end;
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
4
Afişarea pe ecran a şirului după ce a fost sortat se face folosind procedura showa. procedure showa; var i:integer; begin write('Sorted array: '); for i:=1 to a.length do write(a.data[i],' '); readln; {Waits to press ENTER.} end;
Bubble Sort Cel mai simplu algoritm de sortare şi prin urmare unul din cei mai lenţi. Se compară valorile două câte două şi se interschimbă dacă nu sunt în ordinea dorită folosind procedura exchange, care va fi folosită şi pentru algoritmii care au nevoie de această operaţie. program _bubblesort_; type TArray=record data:array[1..100] of integer; length:integer; end; var a:TArray; {Procedures works on this variable.} procedure exchange(i,j:integer); var tmp:integer; begin tmp:=a.data[i]; a.data[i]:=a.data[j]; a.data[j]:=tmp; end; procedure bubblesort; var i:integer; b:boolean; begin repeat b:=true; for i:=1 to a.length-1 do if a.data[i]>a.data[i+1] then begin exchange(i,i+1); b:=false; end; until b; end;
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
5
procedure reada; var i:integer; begin repeat write('Number of elements: '); readln(a.length); until (a.length>=1) and (a.length<=100); for i:=1 to a.length do begin write('a[',i,']='); readln(a.data[i]); end; end; procedure showa; var i:integer; begin write('Sorted array: '); for i:=1 to a.length do write(a.data[i],' '); readln; {Waits to press ENTER.} end; begin reada; bubblesort; showa; end.
Insertion Sort Insertion sort este un algoritm mult mai rapid decât Bubble Sort pentru a sorta un număr mic de elemente. Modul de funcţionare este asemănător cu felul în care oamenii aranjează cărţile de joc. Se pleacă fără nici o carte în mâna stângă, cărţile fiind cu faţa în jos pe masă. Se ia o carte de pe masă şi se inserează în poziţia corectă în mâna stângă. Pentru a găsi poziţia corectă pentru o carte, se compară cu fiecare carte existentă deja în mână, de la dreapta spre stânga. program _insertionsort_; type TArray=record data:array[1..100] of integer; length:integer; end; var a:TArray; {Procedures works on this variable.}
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
6
procedure insertionsort; var i,j,key:integer; begin for i:=2 to a.length do begin key:=a.data[i]; j:=i-1; while (j>0) and (a.data[j]>key) do begin a.data[j+1]:=a.data[j]; j:=j-1; end; a.data[j+1]:=key; end; end; procedure reada; var i:integer; begin repeat write('Number of elements: '); readln(a.length); until (a.length>=1) and (a.length<=100); for i:=1 to a.length do begin write('a[',i,']='); readln(a.data[i]); end; end; procedure showa; var i:integer; begin write('Sorted array: '); for i:=1 to a.length do write(a.data[i],' '); readln; {Waits to press ENTER.} end; begin reada; insertionsort; showa; end.
Merge Sort Merge sort foloseşte metoda divide-and-conquer. Metoda divide-and-conquer presupune 3 paşi la fiecare nivel al recursiei: 1. împarte problema într-un număr de subprobleme. 2. rezolvă subproblemele în mod recursiv; însă dacă mărimea subproblemelor este suficient de mică, se rezolvă subproblemele în mod direct. 3. combină soluţiile subproblemelor în soluţia finală a problemei.
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
7
Procedura merge primeşte 3 poziţii p, q şi r în şirul a cu p ≤ q < r . Se consideră şirul a sortat între p şi q şi între q+1 şi r. Procedura are sarcina să aşeze elementele între p şi r astfel încât ele să fie sortate. Procedura mergesort împarte problema în două subprobleme şi se apelează recursiv pentru a le rezolva, după care combină soluţiile. program _mergesort_; type TArray=record data:array[1..100] of integer; length:integer; end; var a:TArray; {Procedures works on this variable.} procedure merge(p,q,r:integer); var i,j:integer; b:TArray; begin b.length:=0; i:=p; j:=q+1; while (i<=q) and (j<=r) do begin if (a.data[i] < a.data[j]) then begin b.length:=b.length+1; b.data[b.length]:=a.data[i]; i:=i+1; end else begin b.length:=b.length+1; b.data[b.length]:=a.data[j]; j:=j+1; end; end; while (i<=q) do begin b.length:=b.length+1; b.data[b.length]:=a.data[i]; i:=i+1; end; while (j<=r) do begin b.length:=b.length+1; b.data[b.length]:=a.data[j]; j:=j+1; end; for i:=p to r do a.data[i]:=b.data[i-p+1]; end; procedure mergesort(p,r:integer); var q:integer; begin if p
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
8
procedure reada; var i:integer; begin repeat write('Number of elements: '); readln(a.length); until (a.length>=1) and (a.length<=100); for i:=1 to a.length do begin write('a[',i,']='); readln(a.data[i]); end; end; procedure showa; var i:integer; begin write('Sorted array: '); for i:=1 to a.length do write(a.data[i],' '); readln; {Waits to press ENTER.} end; begin reada; mergesort(1,a.length); showa; end.
Quicksort Quicksort foloseşte metoda divide-and-conquer asemeni algoritmului merge sort. Procedura partition rearanjează elementele şirului fără a avea nevoie de zone de stocare temporară. Ea foloseşte o variabilă pivot care este elementul în jurul căruia se face împărţirea intervalului [p..r]. Fiecare element din partea inferioară a şirului va fi mai mic sau egal cu oricare din elementele din partea superioară a şirului. Ea va returna poziţia unde cele două zone se separă. program _quicksort_; type TArray=record data:array[1..100] of integer; length:integer; end; var a:TArray; {Procedures works on this variable.} procedure exchange(i,j:integer); var tmp:integer; begin tmp:=a.data[i]; a.data[i]:=a.data[j]; a.data[j]:=tmp; end;
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare function partition(p,r:integer):integer; var i,j,pivot:integer; b:boolean; begin pivot:=a.data[p]; i:=p-1; j:=r+1; b:=true; while b do begin repeat j:=j-1; until a.data[j]<=pivot; repeat i:=i+1; until a.data[i]>=pivot; if i<j then exchange(i,j) else b:=false; end; partition:=j; end; procedure quicksort(p,r:integer); var q:integer; begin if p=1) and (a.length<=100); for i:=1 to a.length do begin write('a[',i,']='); readln(a.data[i]); end; end; procedure showa; var i:integer; begin write('Sorted array: '); for i:=1 to a.length do write(a.data[i],' '); readln; {Waits to press ENTER.} end; begin reada; quicksort(1,a.length); showa; end.
Copyright© 2005 xunRAGE
9
Algoritmi de Sortare prin Comparare
10
Heapsort Heapsort foloseşte o structură de date numită heap. Teoria în jurul acestei structuri este ceva mai lungă şi nu o voi trata aici. Algoritmul rearanjează elementele şirului astfel încât el să reprezinte un heap şi apoi extrage primul element din heap, refăcând şirul rămas ca să reprezinte tot un heap cu procedura heapify. Repetă acest lucru până când în heap nu mai este nimic. program _heapsort_; type THeap=record data:array[1..100] of integer; length:integer; heapsize:integer; end; var a:THeap; {All procedures work on this global variable.} procedure exchange(i,j:integer); var tmp:integer; begin tmp:=a.data[i]; a.data[i]:=a.data[j]; a.data[j]:=tmp; end; function parent(i:integer):integer; begin parent:=i div 2; end; function left(i:integer):integer; begin left:=2*i; end; function right(i:integer):integer; begin right:=2*i+1; end; procedure heapify(i:integer); var l,r,largest:integer; begin l:=left(i); r:=right(i); if (l<=a.heapsize) and (a.data[l]>a.data[i]) then largest:=l else largest:=i; if (r<=a.heapsize) and (a.data[r]>a.data[largest]) then largest:=r; if largest<>i then begin exchange(i,largest); heapify(largest); end; end;
Copyright© 2005 xunRAGE
Algoritmi de Sortare prin Comparare
procedure buildheap; var i:integer; begin a.heapsize:=a.length; for i:=a.length div 2 downto 1 do heapify(i); end; procedure heapsort; var i:integer; begin buildheap; for i:=a.length downto 2 do begin exchange(1,i); a.heapsize:=a.heapsize-1; heapify(1); end; end; procedure reada; var i:integer; begin repeat write('Number of elements: '); readln(a.length); until (a.length>=1) and (a.length<=100); for i:=1 to a.length do begin write('a[',i,']='); readln(a.data[i]); end; end; procedure showa; var i:integer; begin write('Sorted array: '); for i:=1 to a.length do write(a.data[i],' '); readln; {Waits to press ENTER.} end; begin reada; heapsort; showa; end.
Copyright© 2005 xunRAGE
11