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