-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathHeap_sort.html
140 lines (120 loc) · 6.71 KB
/
Heap_sort.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
<!DOCTYPE html>
<html lang="ro">
<head>
<meta charset="utf-8"/>
<title>Heap sort</title>
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">
<link rel="stylesheet" type="text/css" href="styles/general_style.css">
<link rel="stylesheet" type="text/css" href="styles/heap_style.css">
<link rel="stylesheet" type="text/css" href="styles/resident_evil/stylesheet.css">
<link rel="icon" href="imagini/sort-by-numeric-order.png" type="image/gif" sizes="16x16">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.7/umd/popper.min.js" integrity="sha384-UO2eT0CpHqdSJQ6hJty5KVphtPhzWj9WO1clHTMGa3JDZwrnQq4sF86dIHNDz0W1" crossorigin="anonymous"></script>
<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/js/bootstrap.min.js" integrity="sha384-JjSmVgyd0p3pXB1rRibZUAYoIIy6OrQ6VrjIEaFf/nJGzIxFDsf4x0xIM+B07jRM" crossorigin="anonymous"></script>
</head>
<body>
<div id="container">
<div class="item-a">
<nav class="navbar navbar-expand-md navbar-toggleable-sm justify-content-center">
<ul class="navbar-nav">
<li class="nav-item"><a class="nav-link" href="index.html">Home</a></li>
<li class="nav-item"><a class="nav-link" href="Help.html">Help</a></li>
<li class="nav-item dropdown">
<a class="nav-link dropdown-toggle" href="#" id="navbardrop" data-toggle="dropdown">
Sorting Algorithms
</a>
<div class="dropdown-menu">
<a class="dropdown-item" href="Bubble_sort.html">Bubble Sort</a>
<a class="dropdown-item" href="Selection_sort.html">Selection Sort</a>
<a class="dropdown-item" href="Insertion_sort.html">Insertion Sort</a>
<a class="dropdown-item" href="Shell_sort.html">Shell Sort</a>
<a class="dropdown-item" href="Merge_sort.html">Merge Sort</a>
<a class="dropdown-item" href="Quick_sort.html">Quick Sort</a>
<a class="active" href="Heap_sort.html">Heap Sort</a>
</div>
</li>
</ul>
</nav>
<h1 id="title">Heap Sort</h1>
</div>
<div class="item-b">
<div id="algoritm">
<p>void swap(int a[], int i, int j){</p>
<p class="p10">int aux = a[i];</p>
<p class="p10">a[i] = a[j];</p>
<p class="p10">a[j] = aux;</p>
<p>{</p>
<p>void downHeap( int a[], int v, int n)</p>
<p class="p10">int w = 2 * v + 1;</p>
<p class="p10d">//pimul descendent al lui v</p>
<p class="p10">while(w < n){</p>
<p class="p20">if(w+1 < n)</p>
<p class="p10d">//verificam daca mai exista alti descendenti</p>
<p class="p30">if(a[w+1] > a [w]) w++;</p>
<p class="p10d">//w este descendentul lui v</p>
<br>
<p class="p20">if(a[v] >= a[w]) return;</p>
<p class="p10d">//interschimbam v cu w</p>
<p class="p20">swap(a,v,w);</p>
<p class="p10d">//continuam</p>
<p class="p20">v = w;</p>
<p class="p20">w = 2 * v + 1;</p>
<p class="p10">}</p>
<br>
<p >void HeapSort(int a[], int n){</p>
<p class="p10d">//creem heap-ul</p>
<p class="p10">for(int v = n/2-1; v > 0 ; v--)</p>
<p class="p20">downHeap(a,v,n);</p>
<p class="p10">while (n > 1){</p>
<p class="p20">n--;</p>
<p class="p20">swap(a,0,n);</p>
<p class="p20">downHeap(a,0,n);</p>
<p class="p10">}</p>
<p >}</p>
</div>
</div>
<div class="item-c">
<div id="positioning_text">
<h2 class="alignc">PREZENTAREA METODEI</h2>
<p> Heapsort poate fi condiderat ca fiind un algoritm de selectie mai bun: la fel ca ca in Selection sort, Heapsort divide vectorul in doua regiuni
, una sortata si una nesortata, si in mod iterativa micsoreaza regiuna nesortata extragand de acolo cel mai mare element si mutandu-l in cea sortata.
Imbunatarirea consta in utilizarea unei structuri de date in loc de o cautare liniara a maximului. Desi mai incet decat un Quicksort bine imlementat
, Heapsort are avantajul ca in cel mai rau caz timpul sau de executie se va apropia de O( N*log(N)), spre deosebire de Quicksort care se va apropia de O(N^2).
Un alt avantaj este faptul ca Heapsort nu este un algoritm recursiv. Algoritmii recursivi ruleaza rapid, dar consuma o mare cantitate de memorie, ceea ce nu le
permite sa sorteze tablouri de dimensiuni oricat de mari. Algoritmul Heapsort poate fi impartit in doua parti.</p>
<p> -In prima etapa, un heap este construit din date. Heap-ul este adesea plasat intr-o matrice cu aspectul unui arbore binar complet.
Arborele binar complet traseaza structura binara a arborelui in indici de matrice; fiecare index de matrice reprezinta un nod;
indicele de baza al nodului, ramura stanga, sau ramura dreapta sunt expresii simple. Pentru o matrice de baza zero, nodul radacina este stocat la indexul 0.</p>
<p> -În a doua etapa, o matrice sortata este creata prin indepartarea in mod repetat a celui mai mare element din heap (radacina heap)
si introducand-ul in matrice. Heap-ul este actualizat dupa fiecare stergere pentru a mentine integritatea acestuia. Odata ce toate obiectele au fost scoase din
heap, rezultatul este o matrice sortata.Astfel pasii sunt urmatorii:</p>
<p class="alignl"> 1.Creearea heap-ului.</p>
<p class="alignl"> 2.Schimbaraea primului element din lista cu ultimul. Scade marimea listei cu unu deoarece ultimul element se afla deja la pozitia finala in matricea sortata.</p>
<p class="alignl"> 3.Pozitionarea noului prim element din lista la indexul lui corect din heap.</p>
<p class="alignl"> 4.Daca lista nu este formata dintr-un singur elememnt, ne intoaecem la pasul 2.</p>
</div>
<div id="img">
<h2 class="alignc">O reprezentare vizuala a algoritmului:</h2>
<img src="imagini/Heapsort-example.gif" alt="HTML5 Icon" id="alg">
</div>
</div>
<div class="item-d">
<div id="sortInfo">
<h2 id="sorth2"> Timpuri de executare:</h2>
<ol id="list">
<li>Cazul mediu : O( N*log(N))</li>
<li>Cazul defavorabil : O( N*log(N))</li>
<li>Cazul cel mai bun: O( N*log(N))</li>
<li>Memorie folosita : O( 1)</li>
<li>Stabil : NU</li>
<li>Sortare descrescatoare :if(a[w+1]< a[w]) w++;
<p class="p170"> if (a[v]<=a[w]) return;</p> </li>
<li>Sortare crescatoare :if (a[w+1]> a[w]) w++;
<p class="p150"> if (a[v]>=a[w]) return;</p> </li>
</ol>
</div>
</div>
</div>
</body>
</html>