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[st]>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=st=1. (1=1=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[1+1]=a[2]=a[j]=a[1]=10. Postincrementăm j. (2>1=>j>i-1).
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. 0>-1=>a[st]>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=st=1. (1<2=>j≤i-1). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=0. Postincrementăm j.
(2=2=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=0. Postincrementăm j. (3>2=>j>i-1). Ieșim
din for (nu s-a respectat condiția). a[st]=a[1]=aux=-1.
-1 0 0 -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. -1>-3=>a[st]>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[st]>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=st=1. (1<3=>j≤i-1). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-1. Postincrementăm j.
(2<3=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-1. Postincrementăm j. (3=3=>j≤i-1). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-1. Postincrementăm
j. (4>3=>j>i-1). Ieșim din for (nu s-a respectat condiția).
a[st]=a[1]=aux=-3.
-3 -1 -1 -1 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. -3<1=>a[st]≤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[st]≤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=st=1. (1<4=>j≤i-1). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-3.
Postincrementăm j. (2<4=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-3. Postincrementăm j.
(3<4=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-3. Postincrementăm j. (4=4=>j≤i-1). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-3. Postincrementăm
j. (5>4=>j>i-1). Ieșim din for (nu s-a respectat condiția).
a[st]=a[1]=aux=1.
1 -3 -3 -3 -3 -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. 1>-4=>a[st]>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>-4=>a[st]>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=st=1. (1<5=>st≤i-1). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=1. Postincrementăm j. (2<5=>st≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=1.
Postincrementăm j. (3<5=>st≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=1. Postincrementăm j. (4<5=>st≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=1.
Postincrementăm j. (5=5=>st≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[5+1]=a[6]=a[j]=a[5]=1. Postincrementăm j. (6>5=>st>i-1).
Ieșim din for (nu s-a respectat condiția). a[st]=a[1]=aux=-4.
-4 1 1 1 1 1 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. -4<9=>a[st]≤aux=>(intrăm în
else)=>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<9=>a[st]≤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=st=1. (1<6=>st≤i-1). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-4.
Postincrementăm j. (2<6=>st≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-4. Postincrementăm j. (3<6=>st≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-4.
Postincrementăm j. (4<6=>st≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-4. Postincrementăm j. (5<6=>st≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=-4.
Postincrementăm j. (6=6=>st≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[6+1]=a[7]=a[j]=a[6]=-4. Postincrementăm j. (7>6=>st>i-1).
Ieșim din for (nu s-a respectat condiția). a[st]=a[1]=aux=9.
9 -4 -4 -4 -4 -4 -4 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. 9>3=>a[st]>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. 9>3=>a[st]>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. 9>3=>a[st]>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=st=1. (1<7=>j≤i-1). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=9. Postincrementăm j.
(2<7=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=9. Postincrementăm j. (3<7=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=9.
Postincrementăm j. (4<7=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=9. Postincrementăm j. (5<7=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=9.
Postincrementăm j. (6<7=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=9. Postincrementăm j. (7=7=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[7+1]=a[8]=a[j]=a[7]=9.
Postincrementăm j. (8>7=>j>i-1). Ieșim din for (nu s-a respectat
condiția). a[st]=a[1]=aux=3.
3 9 9 9 9 9 9 9 -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. 3>-1=>a[st]>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. 3>-1=>a[st]>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[st]>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=st=1. (1<8=>j≤i-1). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=3. Postincrementăm j.
(2<8=>j≤i-1). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=3.
Postincrementăm j. (3<8=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=3. Postincrementăm j. (4<8=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=3.
Postincrementăm j. (5<8=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=3. Postincrementăm j. (6<7=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=3.
Postincrementăm j. (7=7=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[7+1]=a[8]=a[j]=a[7]=3. Postincrementăm j. (8>7=>j>i-1). Ieșim
din for (nu s-a respectat condiția). a[st]=a[1]=aux=-1.
-1 3 3 3 3 3 3 3 3 -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. -1>-4=>a[st]>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. -1>-4=>a[st]>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>-4=>a[st]>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=st=1. (1<9=>j≤i-1). Continuăm for-ul (s-a
respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-1. Postincrementăm j.
(2<9=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-1. Postincrementăm j. (3<9=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-1.
Postincrementăm j. (4<9=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-1. Postincrementăm j.
(5<9=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[5+1]=a[6]=a[j]=a[5]=-1. Postincrementăm j. (6<9=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=-1.
Postincrementăm j. (7<9=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[7+1]=a[8]=a[j]=a[7]=-1. Postincrementăm j.
(8<9=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[8+1]=a[9]=a[j]=a[8]=-1. Postincrementăm j. (9=9=>j≤i-1). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[9+1]=a[10]=a[j]=a[9]=-1.
Postincrementăm j. (10>9=>j>i-1). Ieșim din for (nu s-a respectat
condiția). a[st]=a[1]=aux=-4.
-4 -1 -1 -1 -1 -1 -1 -1 -1 -1 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. -4<3=>a[st]≤aux=>(intrăm în
else)=>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<3=>a[st]≤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. -4<3=>a[st]≤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=st=1. (1<10=>j≤i-1). Continuăm
for-ul (s-a respectat condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=-4.
Postincrementăm j. (2<10=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[2+1]=a[3]=a[j]=a[2]=-4. Postincrementăm j.
(3<10=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[3+1]=a[4]=a[j]=a[3]=-4. Postincrementăm j. (4<10=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=-4.
Postincrementăm j. (5<10=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=-4. Postincrementăm j.
(6<10=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[6+1]=a[7]=a[j]=a[6]=-4. Postincrementăm j. (7<10=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[7+1]=a[8]=a[j]=a[7]=-4.
Postincrementăm j. (8<10=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[8+1]=a[9]=a[j]=a[8]=-4. Postincrementăm j.
(9<10=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[9+1]=a[10]=a[j]=a[9]=-4. Postincrementăm j. (10=10=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[10+1]=a[11]=a[j]=a[10]=-4.
Postincrementăm j. (11>10=>j>i-1). Ieșim din for (nu s-a respectat
condiția). a[st]=a[1]=aux=3.
3 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -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. 3>-4=>a[st]>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. 3>-4=>a[st]>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[st]>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=st=1. (1<11=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[1+1]=a[2]=a[j]=a[1]=3. Postincrementăm j.
(2<11=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[2+1]=a[3]=a[j]=a[2]=3. Postincrementăm j. (3<11=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[3+1]=a[4]=a[j]=a[3]=3.
Postincrementăm j. (4<11=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[4+1]=a[5]=a[j]=a[4]=3. Postincrementăm j.
(5<11=>j≤i-1). Continuăm for-ul (s-a respectat condiția). a[j+1]=a[5+1]=a[6]=a[j]=a[5]=3.
Postincrementăm j. (6<11=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[6+1]=a[7]=a[j]=a[6]=3. Postincrementăm j.
(7<11=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[7+1]=a[8]=a[j]=a[7]=3. Postincrementăm j. (8<11=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[8+1]=a[9]=a[j]=a[8]=3.
Postincrementăm j. (9<11=>j≤i-1). Continuăm for-ul (s-a respectat
condiția). a[j+1]=a[9+1]=a[10]=a[j]=a[9]=3. Postincrementăm j.
(10<11=>j≤i-1). Continuăm for-ul (s-a respectat condiția).
a[j+1]=a[10+1]=a[11]=a[j]=a[10]=3. Postincrementăm j. (11=11=>j≤i-1).
Continuăm for-ul (s-a respectat condiția). a[j+1]=a[11+1]=a[12]=a[j]=a[11]=3.
Postincrementăm j. (12>11=>j>i-1). Ieșim din for (nu s-a respectat
condiția). a[st]=a[1]=aux=-4.
-4 3 3 3 3 3 3 3 3 3 3 3
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[st]>aux)
dr=m-1;
else
dr=m-1;
}
for (j=st;j<=i-1;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