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