10 0 -1 -3 1 -4 9 3 -1 -4 3 -4
Am apelat în main() QuickSort(1,12),
cu st=1 și
dr=12. 1<12=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(1+12)/2=6,
aux=v[st]=v[1]=10, v[st]=v[1]=v[m]=v[6]=-4, v[m]=v[6]=aux=10, i=st=1, j=dr=12,
d=0. (1<12=>i<j).
-4 0 -1 -3 1 10 9 3 -1 -4 3 -4
Intrăm în while (s-a respectat condiția).
-4=-4=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția). i=i+d=1+0=1,
j=j+d-1=12+0-1=11. (1<11=>i<j). Continuăm while-ul (s-a respectat condiția).
-4<3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=1+0=1, j=j+d-1=11+0-1=10. (1<10=>i<j). Continuăm while-ul (s-a
respectat condiția). -4=-4=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=1+0=1, j=j+d-1=10+0-1=9. (1<9=>i<j). Continuăm
while-ul (s-a respectat condiția). -4<-1=>v[i]≤v[j]. Nu intrăm în al
doilea if (nu s-a respectat condiția). i=i+d=1+0=1, j=j+d-1=9+0-1=8.
(1<8=>i<j). Continuăm while-ul (s-a respectat condiția).
-4<3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=1+0=1, j=j+d-1=8+0-1=7. (1<7=>i<j). Continuăm while-ul (s-a
respectat condiția). -4<9=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=1+0=1, j=j+d-1=7+0-1=6. (1<6=>i<j). Continuăm
while-ul (s-a respectat condiția). -4=-4=>v[i]≤v[j]. Nu intrăm în al doilea if
(nu s-a respectat condiția). i=i+d=1+0=1, j=j+d-1=6+0-1=5. (1<5=>i<j).
Continuăm while-ul (s-a respectat condiția). -4<1=>v[i]≤v[j]. Nu intrăm în
al doilea if (nu s-a respectat condiția). i=i+d=1+0=1, j=j+d-1=5+0-1=4.
(1<4=>i<j). Continuăm while-ul (s-a respectat condiția).
-4<-3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=1+0=1, j=j+d-1=4+0-1=3. (1<3=>i<j). Continuăm while-ul (s-a
respectat condiția). -4<-1=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=1+0=1, j=j+d-1=3+0-1=2. (1<2=>i<j). Continuăm
while-ul (s-a respectat condiția). -4<0=>v[i]≤v[j]. Nu intrăm în al
doilea if (nu s-a respectat condiția). i=i+d=1+0=1, j=j+d-1=2+0-1=1. (1=1=>i≥j).
Ieșim din while (nu s-a respectat condiția). QuickSort(st,i-1)=QuickSort(1,1-1)=QuickSort(1,0)=>dr=0.
1>0=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(1,0)=>(ne
întoarcem cu un apel, la QuickSort(1,12))=>QuickSort(i+1,dr)=QuickSort(1+1,12)=QuickSort(2,12)=>st=2.
2<12=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(2+12)/2=7,
aux=v[st]=v[2]=0, v[st]=v[2]=v[m]=v[7]=9, v[m]=v[7]=aux=0, i=st=2, j=dr=12,
d=0. (2<12=>i<j).
-4 9 -1 -3 1 10 0 3 -1 -4 3 -4
Intrăm în while (s-a respectat condiția).
9>-4=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția). aux=v[i]=v[2]=9.
v[i]=v[2]=v[j]=v[12]=-4. v[j]=v[12]=aux=9. d=1-d=1-0=1. Încheiem al doilea if. i=i+d=2+1=3,
j=j+d-1=12+1-1=12. (3<12=>i<j).
-4 -4 -1 -3 1 10 0 3 -1 -4 3 9
Continuăm while-ul (s-a respectat condiția).
-1<9=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=3+1=4, j=j+d-1=12+1-1=12. (4<12=>i<j). Intrăm în while (s-a
respectat condiția). -3<9=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=4+1=5, j=j+d-1=12+1-1=12. (5<12=>i<j). Intrăm
în while (s-a respectat condiția). 1<9=>v[i]≤v[j]. Nu intrăm în al doilea
if (nu s-a respectat condiția). i=i+d=5+1=6, j=j+d-1=12+1-1=12. (6<12=>i<j).
Continuăm while-ul (s-a respectat condiția). 10>9=>v[i]>v[j]. Intrăm în
al doilea if (s-a respectat condiția). aux=v[i]=v[6]=10. v[i]=v[6]=v[j]=v[12]=9.
v[j]=v[12]=aux=10. d=1-d=1-1=0. Încheiem al doilea if. i=i+d=6+0=6,
j=j+d-1=12+0-1=11. (6<11=>i<j).
-4 -4 -1 -3 1 9 0 3 -1 -4 3 10
Continuăm while-ul (s-a respectat condiția).
9>3=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția).
aux=v[i]=v[6]=9. v[i]=v[6]=v[j]=v[11]=3. v[j]=v[11]=aux=9. d=1-d=1-0=1. Încheiem
al doilea if. i=i+d=6+1=7, j=j+d-1=11+1-1=11.
-4 -4 -1 -3 1 3 0 3 -1 -4 9 10
(7<11=>i<j). Continuăm while-ul
(s-a respectat condiția). 0<9=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+1=7+1=8, j=j+d-1=11+1-1=11. (8<11=>i<j). Continuăm
while-ul (s-a respectat condiția). 3<9=>v[i]≤v[j]. Nu intrăm în al doilea
if (nu s-a respectat condiția). i=i+d=8+1=9, j=j+d-1=11+1-1=11. (9<11=>i<j).
Continuăm while-ul (s-a respectat condiția). -1<9=>v[i]≤v[j]. Nu intrăm în
al doilea if (nu s-a respectat condiția). i=i+d=9+1=10, j=j+d-1=11+1-1=11. (10<11=>i<j).
Continuăm while-ul (s-a respectat condiția). -4<9=>v[i]≤v[j]. Nu intrăm în
al doilea if (nu s-a respectat condiția). i=i+d=10+1=11, j=j+d-1=11+1-1=11.
(11=11=>i≥j). Ieșim din while (nu s-a respectat condiția). QuickSort(st,i-1)=QuickSort(2,11-1)=QuickSort(2,10)=>dr=10.
2<10=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(2+10)/2=6, aux=v[st]=v[2]=-4,
v[st]=v[2]=v[m]=v[6]=3, v[m]=v[6]=aux=-4, i=st=2, j=dr=10, d=0. (2<10=>i<j).
-4 3 -1 -3 1 -4 0 3 -1 -4 9 10
Intrăm în while (s-a respectat condiția).
3>-4=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția). aux=v[i]=v[2]=3.
v[i]=v[2]=v[j]=v[10]=-4. v[j]=v[10]=aux=3. d=1-d=1-0=1. Încheiem al doilea if. i=i+d=2+1=3,
j=j+d-1=10+1-1=10. (3<10=>i<j).
-4 -4 -1 -3 1 -4 0 3 -1 3 9 10
Continuăm while-ul (s-a respectat condiția).
-1<3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=3+1=4, j=j+d-1=10+1-1=10. (4<10=>i<j). Continuăm while-ul (s-a
respectat condiția). -3<3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=4+1=5, j=j+d-1=10+1-1=10. (5<10=>i<j). Continuăm
while-ul (s-a respectat condiția). 1<3=>v[i]≤v[j]. Nu intrăm în al doilea
if (nu s-a respectat condiția). i=i+d=5+1=6, j=j+d-1=10+1-1=10. (6<10=>i<j).
Continuăm while-ul (s-a respectat condiția). -4<3=>v[i]≤v[j]. Nu intrăm în
al doilea if (nu s-a respectat condiția). i=i+d=6+1=7, j=j+d-1=10+1-1=10.
(7<10=>i<j). Continuăm while-ul (s-a respectat condiția).
0<3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția). i=i+d=7+1=8,
j=j+d-1=10+1-1=10. (8<10=>i<j). Continuăm while-ul (s-a respectat condiția).
3=3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=8+1=9, j=j+d-1=10+1-1=10. (9<10=>i<j). Continuăm while-ul (s-a
respectat condiția). -1<3=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=9+1=10, j=j+d-1=10+1-1=10. (10=10=>i≥j). Ieșim
din while (nu s-a respectat condiția). QuickSort(st,i-1)=QuickSort(2,10-1)=QuickSort(2,9)=>dr=9.
2<9=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(2+9)/2=5, aux=v[st]=v[2]=-4,
v[st]=v[2]=v[m]=v[5]=1, v[m]=v[5]=aux=-4, i=st=2, j=dr=9, d=0. (2<9=>i<j).
-4 1 -1 -3 -4 -4 0 3 -1 3 9 10
Intrăm în while (s-a respectat condiția).
1>-1=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția).
aux=v[i]=v[2]=1. v[i]=v[2]=v[j]=v[9]=-1. v[j]=v[9]=aux=1. d=1-d=1-0=1. Încheiem
al doilea if. i=i+d=2+1=3, j=j+d-1=9+1-1=9. (3<9=>i<j).
-4 -1 -1 -3 -4 -4 0 3 1 3 9 10
Continuăm while-ul (s-a respectat condiția).
-1<1=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=3+1=4, j=j+d-1=9+1-1=9. (4<9=>i<j). Continuăm while-ul (s-a
respectat condiția). -3<1=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=4+1=5, j=j+d-1=9+1-1=9. (5<9=>i<j). Continuăm
while-ul (s-a respectat condiția). -4<1=>v[i]≤v[j]. Nu intrăm în al
doilea if (nu s-a respectat condiția). i=i+d=5+1=6, j=j+d-1=9+1-1=9. (6<9=>i<j).
Continuăm while-ul (s-a respectat condiția). -4<1=>v[i]≤v[j]. Nu intrăm în
al doilea if (nu s-a respectat condiția). i=i+d=6+1=7, j=j+d-1=9+1-1=9. (7<9=>i<j).
Continuăm while-ul (s-a respectat condiția). 0<1=>v[i]≤v[j]. Nu intrăm în
al doilea if (nu s-a respectat condiția). i=i+d=7+1=8, j=j+d-1=9+1-1=9. (8<9=>i<j).
Continuăm while-ul (s-a respectat condiția). 3>1=>v[i]>v[j]. Intrăm în
al doilea if (s-a respectat condiția). aux=v[i]=v[8]=3. v[i]=v[8]=v[j]=v[9]=1.
v[j]=v[9]=aux=3. d=1-d=1-1=0. Încheiem al doilea if. i=i+d=8+0=8,
j=j+d-1=9+0-1=8. (8=8=>i≥j).
-4 -1 -1 -3 -4 -4 0 1 3 3 9 10
Ieșim din while (nu s-a respectat condiția).
QuickSort(st,i-1)=QuickSort(2,8-1)=QuickSort(2,7)=>dr=7. 2<7=>st<dr=>(intrăm
în primul if)=>m=(st+dr)/2=(2+7)/2=4, aux=v[st]=v[2]=-1, v[st]=v[2]=v[m]=v[4]=-3,
v[m]=v[4]=aux=-1, i=st=2, j=dr=7, d=0. (2<7=>i<j).
-4 -3 -1 -1 -4 -4 0 1 3 3 9 10
Intrăm în while (s-a respectat condiția).
-3<0=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=2+0=2, j=j+d-1=7+0-1=6. (2<6=>i<j). Continuăm while-ul (s-a
respectat condiția). -3>-4=>v[i]>v[j]. Intrăm în al doilea if (s-a
respectat condiția). aux=v[i]=v[2]=-3. v[i]=v[2]=v[j]=v[6]=-4. v[j]=v[6]=aux=-3.
d=1-d=1-0=1. Încheiem al doilea if. i=i+d=2+1=3, j=j+d-1=6+1-1=6.
(3<6=>i<j).
-4 -4 -1 -1 -4 -3 0 1 3 3 9 10
Continuăm while-ul (s-a respectat condiția).
-1>-3=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția).
aux=v[i]=v[3]=-1. v[i]=v[3]=v[j]=v[6]=-3. v[j]=v[6]=aux=-1. d=1-d=1-1=0. Încheiem
al doilea if. i=i+d=3+0=3, j=j+d-1=6+0-1=5. (3<5=>i<j).
-4 -4 -3 -1 -4 -1 0 1 3 3 9 10
Continuăm while-ul (s-a respectat condiția).
-3>-4=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția).
aux=v[i]=v[3]=-3. v[i]=v[3]=v[j]=v[5]=-4. v[j]=v[5]=aux=-3. d=1-d=1-0=1. Încheiem
al doilea if. i=i+d=3+1=4, j=j+d-1=5+1-1=5. (4<5=>i<j).
-4 -4 -4 -1 -3 -1 0 1 3 3 9 10
Continuăm while-ul (s-a respectat condiția).
-1>-3=>v[i]>v[j]. Intrăm în al doilea if (s-a respectat condiția).
aux=v[i]=v[4]=-1. v[i]=v[4]=v[j]=v[5]=-3. v[j]=v[5]=aux=-1. d=1-d=1-1=0. Încheiem
al doilea if. i=i+d=4+0=4, j=j+d-1=5+0-1=4. (4=4=>i≥j).
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
Ieșim din while (nu s-a respectat condiția).
QuickSort(st,i-1)=QuickSort(2,4-1)=QuickSort(2,3)=>dr=3.
2<3=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(2+3)/2=2,
aux=v[st]=v[2]=-4, v[st]=v[2]=v[m]=v[2]=-4, v[m]=v[2]=aux=-4, i=st=2, j=dr=3,
d=0. (2<3=>i<j).
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
Intrăm în while (s-a respectat condiția).
-4=-4=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=2+0=2, j=j+d-1=3+0-1=2. (2=2=>i≥j). Ieșim din while (nu s-a respectat condiția).
QuickSort(st,i-1)=QuickSort(2,2-1)=QuickSort(2,1)=>dr=1. 2>1=>st≥dr=>(nu
intrăm în primul if)=>încheiem apelul QuickSort(2,1)=>(ne întoarcem cu un
apel, la QuickSort(2,3))=>QuickSort(i+1,dr)=QuickSort(2+1,3)=QuickSort(3,3)=>st=3.
3=3=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(3,3)=>(ne
întoarcem cu un apel, la QuickSort(2,3)). Am încheiat apelul QuickSort(2,3)=>(ne
întoarcem cu un apel, la QuickSort(2,7))=>QuickSort(i+1,dr)=QuickSort(4+1,7)=QuickSort(5,7)=>st=5.
5<7=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(5+7)/2=6,
aux=v[st]=v[5]=-1, v[st]=v[5]=v[m]=v[6]=-1, v[m]=v[6]=aux=-1, i=st=5, j=dr=7,
d=0. (5<7=>i<j).
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
Intrăm în while (s-a respectat condiția).
-1<0=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=5+0=5, j=j+d-1=7+0-1=6. (5<6=>i<j). Continuăm while-ul (s-a
respectat condiția). -1=-1=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a
respectat condiția). i=i+d=5+0=5, j=j+d-1=6+0-1=5. (5=5=>i≥j). Ieșim din
while (nu s-a respectat condiția). QuickSort(st,i-1)=QuickSort(5,5-1)=QuickSort(5,4)=>dr=4.
5>4=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(5,4)=>(ne
întoarcem cu un apel, la QuickSort(5,7))=>QuickSort(i+1,dr)=QuickSort(5+1,7)=QuickSort(6,7)=>st=6.
6<7=>st<dr=>(intrăm în primul if)=>m=(st+dr)/2=(6+7)/2=6, aux=v[st]=v[6]=-1,
v[st]=v[6]=v[m]=v[6]=-1, v[m]=v[6]=aux=-1, i=st=6, j=dr=7, d=0. (6<7=>i<j).
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
Intrăm în while (s-a respectat condiția).
-1<0=>v[i]≤v[j]. Nu intrăm în al doilea if (nu s-a respectat condiția).
i=i+d=6+0=6, j=j+d-1=7+0-1=6. (6=6=>i≥j). Ieșim din while (nu s-a respectat condiția).
QuickSort(st,i-1)=QuickSort(6,6-1)=QuickSort(6,5)=>dr=5. 6>5=>st≥dr=>(nu
intrăm în primul if)=>încheiem apelul QuickSort(6,5)=>(ne întoarcem cu un
apel, la QuickSort(6,7))=>QuickSort(i+1,dr)=QuickSort(6+1,7)=QuickSort(7,7)=>st=7.
7=7=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(7,7)=>(ne
întoarcem cu un apel, la QuickSort(6,7)). Am încheiat apelul QuickSort(6,7)=>(ne
întoarcem cu un apel, la QuickSort(5,7)). Am încheiat apelul QuickSort(5,7)=>(ne
întoarcem cu un apel, la QuickSort(2,7)). Am încheiat apelul
QuickSort(2,7)=>(ne întoarcem cu un apel, la QuickSort(2,9))=>QuickSort(i+1,dr)=QuickSort(8+1,9)=QuickSort(9,9)=>st=9.
9=9=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(9,9)=>(ne
întoarcem cu un apel, la QuickSort(2,9)). Am încheiat apelul
QuickSort(2,9)=>(ne întoarcem cu un apel, la QuickSort(2,10))=>QuickSort(i+1,dr)=QuickSort(10+1,10)=QuickSort(11,10)=>st=11.
11>10=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(11,10)=>(ne
întoarcem cu un apel, la QuickSort(2,10)). Am încheiat apelul
QuickSort(2,10)=>(ne întoarcem cu un apel, la QuickSort(2,12))=>QuickSort(i+1,dr)=QuickSort(11+1,12)=QuickSort(12,12)=>st=12.
12=12=>st≥dr=>(nu intrăm în primul if)=>încheiem apelul QuickSort(12,12)=>(ne
întoarcem cu un apel, la QuickSort(2,12)). Am încheiat apelul
QuickSort(2,12)=>(ne întoarcem cu un apel, la QuickSort(1,12)). Am încheiat
apelul QuickSort(1,12).
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
#include
<iostream>
using namespace std;
int n,v[100005];
void QuickSort(int
st,int dr)
{
if (st<dr)
{
int
m=(st+dr)/2;
int
aux=v[st];
v[st]=v[m];
v[m]=aux;
int
i=st,j=dr,d=0;
while
(i<j)
{
if (v[i]>v[j])
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
d=1-d;
}
i=i+d;
j=j+d-1;
}
QuickSort(st,i-1);
QuickSort(i+1,dr);
}
}
int main()
{
int i;
cin>>n;
for (i=1;i<=n;++i)
cin>>v[i];
QuickSort(1,n);
for (i=1;i<=n;++i)
cout<<v[i]<<' ';
}
Comentarii
Trimiteți un comentariu