10 0 -1 -3 1 -4 9 3 -1 -4 3 -4
Am apelat în main() BinaryInsertionSort(a,12).
Intrăm în for. i=2. (2<12=>i≤n). Continuăm for-ul (s-a respectat
condiția). aux=a[i]=a[2]=0. st=1. dr=i-1=2-1=1. (1=1=>st≤dr). Intrăm în
while (s-a respectat condiția). m=(st+dr)/2=(1+1)/2=2/2=1.
10>0=>a[dr]>aux=>(intrăm în if)=>dr=m-1=1-1=0. (1>0=>st>dr).
Ieșim din while (nu s-a respectat condiția). Intrăm în for. j=i-1=1. (1=1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=10. Postdecrementăm
j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția). a[st]=a[1]=aux=0.
0 10 -1 -3 1 -4 9 3 -1 -4 3 -4
Postincrementăm i. (3<12=>i≤n). Continuăm
for-ul (s-a respectat condiția). aux=a[i]=a[3]=-1. st=1. dr=i-1=3-1=2.
(1<2=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+2)/2=3/2=1. 10>-1=>a[dr]>aux=>(intrăm în
if)=>dr=m-1=1-1=0. (1>0=>st>dr). Ieșim din while (nu s-a respectat condiția).
Intrăm în for. j=i-1=2. (2>1=>j≥st). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=10. Postdecrementăm j. (1=1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=0. Postdecrementăm
j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția). a[st]=a[1]=aux=-1.
-1 0 10 -3 1 -4 9 3 -1 -4 3 -4
Postincrementăm i. (4<12=>i≤n). Continuăm
for-ul (s-a respectat condiția). aux=a[i]=a[4]=-3. st=1. dr=i-1=4-1=3.
(1<3=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+3)/2=4/2=2. 10>-3=>a[dr]>aux=>(intrăm în if)=>dr=m-1=2-1=1.
(1=1=>st≤dr). Continuăm while-ul (s-a respectat condiția). m=(st+dr)/2=(1+1)/2=2/2=1.
-1>-3=>a[dr]>aux=>(intrăm în if)=>dr=m-1=1-1=0. (1>0=>st>dr).
Ieșim din while (nu s-a respectat condiția). Intrăm în for. j=i-1=3. (3>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=10. Postdecrementăm
j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=0. Postdecrementăm j. (1=1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-1. Postdecrementăm
j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția).
a[st]=a[1]=aux=-3.
-3 -1 0 10 1 -4 9 3 -1 -4 3 -4
Postincrementăm i. (5<12=>i≤n). Continuăm
for-ul (s-a respectat condiția). aux=a[i]=a[5]=1. st=1. dr=i-1=5-1=4.
(1<4=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+4)/2=5/2=2. 10>1=>a[dr]>aux=>(intrăm în if)=>dr=m-1=2-1=1.
(1=1=>st≤dr). Continuăm while-ul (s-a respectat condiția).
m=(st+dr)/2=(1+1)/2=2/2=1. -3<1=>a[dr]≤aux=>(intrăm în else)=>dr=m-1=1-1=0.
(1>0=>st>dr). Ieșim din while (nu s-a respectat condiția). Intrăm în
for. j=i-1=4. (4>1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=10.
Postdecrementăm j. (3>1=>j≥st). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=0. Postdecrementăm j. (2>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-1. Postdecrementăm
j. (1=1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-3. Postdecrementăm j. (0<1=>j<st). Ieșim
din for (nu s-a respectat condiția). a[st]=a[1]=aux=1.
1 -3 -1 0 10 -4 9 3 -1 -4 3 -4
Postincrementăm i. (6<12=>i≤n). Continuăm
for-ul (s-a respectat condiția). aux=a[i]=a[6]=-4. st=1. dr=i-1=6-1=5.
(1<5=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+5)/2=6/2=3. 10>-4=>a[dr]>aux=>(intrăm în
if)=>dr=m-1=3-1=2. (1<2=>st≤dr). Continuăm while-ul (s-a respectat
condiția). m=(st+dr)/2=(1+2)/2=3/2=1. -3>-4=>a[dr]>aux=>(intrăm în
if)=>dr=m-1=1-1=0. (1>0=>st>dr). Ieșim din while (nu s-a respectat
condiția). Intrăm în for. j=i-1=5. (5>1=>j≥st). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=10. Postdecrementăm j.
(4>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[4+1]=a[5]=a[j]=a[4]=0. Postdecrementăm j. (3>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-1. Postdecrementăm
j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-3. Postdecrementăm j. (1=1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=1. Postdecrementăm
j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția). a[st]=a[1]=aux=-4.
-4 1 -3 -1 0 10 9 3 -1 -4 3 -4
Postincrementăm i. (7<12=>i≤n). Continuăm
for-ul (s-a respectat condiția). aux=a[i]=a[7]=9. st=1. dr=i-1=7-1=6.
(1<6=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+6)/2=7/2=3.
10>9=>a[dr]>aux=>(intrăm în if)=>dr=m-1=3-1=2. (1<2=>st≤dr).
Continuăm while-ul (s-a respectat condiția). m=(st+dr)/2=(1+2)/2=3/2=1.
1<9=>a[dr]≤aux=>(intrăm în else)=>dr=m-1=1-1=0.
(1>0=>st>dr). Ieșim din while (nu s-a respectat condiția). Intrăm în
for. j=i-1=6. (6>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[6+1]=a[7]=a[j]=a[6]=10. Postdecrementăm j. (5>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=0. Postdecrementăm
j. (4>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-1. Postdecrementăm j. (3>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-3. Postdecrementăm
j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=1. Postdecrementăm j. (1=1=>j≥st). Continuăm for-ul
(s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-4. Postdecrementăm j.
(0<1=>j<st). Ieșim din for (nu s-a respectat condiția).
a[st]=a[1]=aux=9.
9 -4 1 -3 -1 0 10 3 -1 -4 3 -4
Postincrementăm i. (8<12=>i≤n).
Continuăm for-ul (s-a respectat condiția). aux=a[i]=a[8]=3. st=1. dr=i-1=8-1=7.
(1<7=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+7)/2=8/2=4. 10>3=>a[dr]>aux=>(intrăm în if)=>dr=m-1=4-1=3.
(1<3=>st≤dr). Continuăm while-ul (s-a respectat condiția).
m=(st+dr)/2=(1+3)/2=4/2=2. 1<3=>a[dr]≤aux=>(intrăm în
else)=>dr=m-1=2-1=1. (1=1=>st≤dr). Continuăm while-ul (s-a respectat
condiția). m=(st+dr)/2=(1+1)/2=2/2=1. 9>3=>a[dr]>aux=>(intrăm în if)=>dr=m-1=1-1=0.
(1>0=>st>dr). Ieșim din while (nu s-a respectat condiția). Intrăm în for.
j=i-1=7. (7>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[7+1]=a[8]=a[j]=a[7]=10. Postdecrementăm j. (6>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=0. Postdecrementăm
j. (5>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[5+1]=a[6]=a[j]=a[5]=-1. Postdecrementăm j. (4>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-3. Postdecrementăm
j. (3>1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=1.
Postdecrementăm j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-4. Postdecrementăm j. (1=1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=9. Postdecrementăm
j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția). a[st]=a[1]=aux=3.
3 9 -4 1 -3 -1 0 10 -1 -4 3 -4
Postincrementăm i. (9<12=>i≤n).
Continuăm for-ul (s-a respectat condiția). aux=a[i]=a[9]=-1. st=1.
dr=i-1=9-1=8. (1<8=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+8)/2=9/2=4. 10>-1=>a[dr]>aux=>(intrăm în if)=>dr=m-1=4-1=3.
(1<3=>st≤dr). Continuăm while-ul (s-a respectat condiția).
m=(st+dr)/2=(1+3)/2=4/2=2. -4<-1=>a[dr]≤aux=>(intrăm în
else)=>dr=m-1=2-1=1. (1=1=>st≤dr). Continuăm while-ul (s-a respectat
condiția). m=(st+dr)/2=(1+1)/2=2/2=1. 3>-1=>a[dr]>aux=>(intrăm în
if)=>dr=m-1=1-1=0. (1>0=>st>dr). Ieșim din while (nu s-a respectat
condiția). Intrăm în for. j=i-1=8. (8>1=>j≥st). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[8+1]=a[9]=a[j]=a[8]=10. Postdecrementăm j.
(7>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[7+1]=a[8]=a[j]=a[7]=0. Postdecrementăm j. (6>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=-1. Postdecrementăm
j. (5>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[5+1]=a[6]=a[j]=a[5]=-3. Postdecrementăm j. (4>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=1. Postdecrementăm
j. (3>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-4. Postdecrementăm j. (2>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=9. Postdecrementăm
j. (1=1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[1+1]=a[2]=a[j]=a[1]=3. Postdecrementăm j. (0<1=>j<st). Ieșim
din for (nu s-a respectat condiția). a[st]=a[1]=aux=-1.
-1 3 9 -4 1 -3 -1 0 10 -4 3 -4
Postincrementăm i. (10<12=>i≤n).
Continuăm for-ul (s-a respectat condiția). aux=a[i]=a[10]=-4. st=1.
dr=i-1=10-1=9. (1<9=>st≤dr). Intrăm în while (s-a respectat condiția).
m=(st+dr)/2=(1+9)/2=10/2=5. 10>-4=>a[dr]>aux=>(intrăm în if)=>dr=m-1=5-1=4.
(1<4=>st≤dr). Continuăm while-ul (s-a respectat condiția). m=(st+dr)/2=(1+4)/2=5/2=2.
-4=-4=>a[dr]≤aux=>(intrăm în else)=>dr=m-1=2-1=1. (1=1=>st≤dr).
Continuăm while-ul (s-a respectat condiția). m=(st+dr)/2=(1+1)/2=2/2=1.
-1>-4=>a[dr]>aux=>(intrăm în if)=>dr=m-1=1-1=0. (1>0=>st>dr).
Ieșim din while (nu s-a respectat condiția). Intrăm în for. j=i-1=9. (9>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[9+1]=a[10]=a[j]=a[9]=10. Postdecrementăm
j. (8>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[8+1]=a[9]=a[j]=a[8]=0. Postdecrementăm j. (7>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[7+1]=a[8]=a[j]=a[7]=-1. Postdecrementăm
j. (6>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[6+1]=a[7]=a[j]=a[6]=-3. Postdecrementăm j. (5>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=1. Postdecrementăm
j. (4>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-4. Postdecrementăm j. (3>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=9. Postdecrementăm
j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=3. Postdecrementăm j. (1=1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-1. Postdecrementăm
j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția). Postdecrementăm
j. a[st]=a[1]=aux=-4.
-4 -1 3 9 -4 1 -3 -1 0 10 3 -4
Postincrementăm i. (11<12=>i≤n).
Continuăm for-ul (s-a respectat condiția). aux=a[i]=a[11]=3. st=1.
dr=i-1=11-1=10. (1<10=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+10)/2=11/2=5.
10>3=>a[dr]>aux=>(intrăm în if)=>dr=m-1=5-1=4. (1<4=>st≤dr).
Continuăm while-ul (s-a respectat condiția). m=(st+dr)/2=(1+4)/2=5/2=2. 9>3=>a[dr]>aux=>(intrăm
în if)=>dr=m-1=2-1=1. (1=1=>st≤dr). Continuăm while-ul (s-a respectat
condiția). m=(st+dr)/2=(1+1)/2=2/2=1. -4<3=>a[dr]≤aux=>(intrăm în
else)=>dr=m-1=1-1=0. (1>0=>st>dr). Ieșim din while (nu s-a
respectat condiția). Intrăm în for. j=i-1=10. (10>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[10+1]=a[11]=a[j]=a[10]=10. Postdecrementăm
j. (9>1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[9+1]=a[10]=a[j]=a[9]=0.
Postdecrementăm j. (8>1=>j≥st). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[8+1]=a[9]=a[j]=a[8]=-1. Postdecrementăm j. (7>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[7+1]=a[8]=a[j]=a[7]=-3. Postdecrementăm
j. (6>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[6+1]=a[7]=a[j]=a[6]=1. Postdecrementăm j. (5>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=-4. Postdecrementăm
j. (4>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[4+1]=a[5]=a[j]=a[4]=9. Postdecrementăm j. (3>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=3. Postdecrementăm
j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-1. Postdecrementăm j. (1=1=>j≥st). Continuăm for-ul
(s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-4. Postdecrementăm j.
(0<1=>j<st). Ieșim din for (nu s-a respectat condiția).
a[st]=a[1]=aux=3.
3 -4 -1 3 9 -4 1 -3 -1 0 10 -4
Postincrementăm i. (12=12=>i≤n).
Continuăm for-ul (s-a respectat condiția). aux=a[i]=a[12]=-4. st=1.
dr=i-1=12-1=11. (1<11=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+11)/2=12/2=6.
10>-4=>a[dr]>aux=>(intrăm în if)=>dr=m-1=6-1=5. (1<5=>st≤dr).
Continuăm while-ul (s-a respectat condiția). m=(st+dr)/2=(1+5)/2=6/2=3. 9>-4=>a[dr]>aux=>(intrăm
în if)=>dr=m-1=3-1=2. (1<2=>st≤dr). Continuăm while-ul (s-a respectat
condiția). m=(st+dr)/2=(1+2)/2=3/2=1. -4=-4=>a[dr]≤aux=>(intrăm în
else)=>dr=m-1=1-1=0. (1>0=>st>dr). Ieșim din while (nu s-a
respectat condiția). Intrăm în for. j=i-1=11. (11>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[11+1]=a[12]=a[j]=a[11]=10. Postdecrementăm
j. (10>1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[10+1]=a[11]=a[j]=a[10]=0.
Postdecrementăm j. (9>1=>j≥st). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[9+1]=a[10]=a[j]=a[9]=-1. Postdecrementăm j. (8>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[8+1]=a[9]=a[j]=a[8]=-3. Postdecrementăm
j. (7>1=>j≥st). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[7+1]=a[8]=a[j]=a[7]=1. Postdecrementăm j. (6>1=>j≥st). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=-4. Postdecrementăm
j. (5>1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=9.
Postdecrementăm j. (4>1=>j≥st). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=3. Postdecrementăm j. (3>1=>j≥st).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-1. Postdecrementăm
j. (2>1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-4.
Postdecrementăm j. (1=1=>j≥st). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=3.
Postdecrementăm j. (0<1=>j<st). Ieșim din for (nu s-a respectat condiția).
a[st]=a[1]=aux=-4.
-4 3 -4 -1 3 9 -4 1 -3 -1 0 10
Postincrementăm i. (13>12=>i>n).
Ieșim din for (nu s-a respectat condiția). Am încheiat apelul BinaryInsertionSort(a,12).
#include <iostream>
using namespace std;
int n,a[50];
void BinaryInsertionSort(int a[],int n)
{
int st,dr,m,i,j,aux;
for (i=2;i<=n;i++)
{
aux=a[i];
st=1;
dr=i-1;
while (st<=dr)
{
m=(st+dr)/2;
if (a[dr]>aux)
dr=m-1;
else
dr=m-1;
}
for (j=i-1;j>=st;j--)
a[j+1]=a[j];
a[st]=aux;
}
}
int main()
{
int i;
cin>>n;
for (i=1;i<=n;++i)
cin>>a[i];
BinaryInsertionSort(a,n);
for (i=1;i<=n;++i)
cout<<a[i]<<' ';
}
Comentarii
Trimiteți un comentariu