https://www.algopedia.ro/wiki/index.php?action=history&feed=atom&title=10_2018_Lectia2310 2018 Lectia23 - Revision history2026-04-13T17:48:00ZRevision history for this page on the wikiMediaWiki 1.44.2https://www.algopedia.ro/wiki/index.php?title=10_2018_Lectia23&diff=16090&oldid=prevBella: Created page with "= Tema Rezolvari = = Lectie = == [https://www.pbinfo.ro/?pagina=probleme&id=1024 Quicksort] == === Varianta 1 de implementare === <syntaxhighlight> #include <iostream> usin..."2019-03-27T13:21:10Z<p>Created page with "= Tema Rezolvari = = Lectie = == [https://www.pbinfo.ro/?pagina=probleme&id=1024 Quicksort] == === Varianta 1 de implementare === <syntaxhighlight> #include <iostream> usin..."</p>
<p><b>New page</b></p><div>= Tema Rezolvari =<br />
= Lectie =<br />
== [https://www.pbinfo.ro/?pagina=probleme&id=1024 Quicksort] ==<br />
<br />
=== Varianta 1 de implementare ===<br />
<br />
<br />
<syntaxhighlight><br />
#include <iostream><br />
using namespace std;<br />
int a[100000], n, i;<br />
void quickSort(int a[], int p, int u) {<br />
int i = p, j = u;<br />
int aux;<br />
int pivot = a[( p + u ) / 2];<br />
while ( i <= j ) {<br />
while ( a[i] < pivot ) // inaintez cu i pana gasesc un element mai mare sau egal cu pivotul<br />
i ++;<br />
while ( a[j] > pivot ) // inaintez cu j pana gasesc un element mai mare sau egal cu pivotul<br />
j --;<br />
if ( i <= j ){ // daca elem de pe poz i se afla in stanga celui de pe poz j,<br />
aux = a[i]; // interchimb cele doua valori<br />
a[i] = a[j];<br />
a[j] = aux;<br />
i++; // mut cei doi pointeri cu o pozitie<br />
j--;<br />
}<br />
}<br />
// de la p la j au elemente mai mici decat pivotul<br />
// de la i la u am elemente mai mari decat pivotul<br />
if ( p < j )<br />
quickSort( a, p, j ); // sortez [p,j] daca am mai mult de un element<br />
if ( i < u )<br />
quickSort( a, i, u ); // sortez [i,u] daca am mai mult de un element<br />
}<br />
int main() {<br />
int n, i;<br />
cin >> n;<br />
for( i = 1; i <= n; i++ )<br />
cin >> a[i];<br />
quickSort( a, 1, n );<br />
for( i = 1; i <= n; i++ )<br />
cout<< a[i] <<" ";<br />
return 0;<br />
}<br />
</syntaxhighlight><br />
<br />
=== Varianta 2 de implementare ===<br />
<syntaxhighlight><br />
#include <bits/stdc++.h><br />
<br />
using namespace std;<br />
<br />
int a[100001];<br />
<br />
int Partition( int a[], int l, int r ){<br />
int x = a[l];<br />
int j=l;<br />
for(int i = l + 1; i <= r; i++ ){<br />
if(a[i] <=x ){<br />
j ++;<br />
swap( a[j], a[i] );<br />
}<br />
}<br />
swap(a[l], a[j]);<br />
return j;<br />
}<br />
<br />
void QuickSort( int a[], int l, int r ){<br />
if( l >= r ){<br />
return;<br />
}<br />
int m = Partition( a, l, r ); <br />
QuickSort( a, l, m-1 );<br />
QuickSort( a, m + 1, r );<br />
}<br />
<br />
int main(){<br />
int l, r, n;<br />
<br />
cin >> n;<br />
for(int i = 1; i <= n; i++ )<br />
cin >> a[i];<br />
<br />
l = 1;<br />
r = n;<br />
QuickSort( a, l, r );<br />
for(int i = 1; i <= n; i++ )<br />
cout << a[i] <<" ";<br />
<br />
return 0;<br />
}<br />
</syntaxhighlight><br />
<br />
= TEMA = <br />
usor<br />
* https://www.pbinfo.ro/?pagina=probleme&id=1024 Quicksort<br />
* https://www.pbinfo.ro/?pagina=probleme&id=1264 Statisticiordine<br />
* https://www.pbinfo.ro/?pagina=probleme&id=1156 InaltimiQ<br />
* https://www.pbinfo.ro/?pagina=probleme&id=1157 KSort2<br />
<br />
medie<br />
* https://www.pbinfo.ro/?pagina=probleme&id=2525 Cioc<br />
<br />
== Tema rezolvari ==</div>Bella