Доброго времени суток, уважаемые знатоки.
Необходима Ваша помощь в реализации метода сортировки.
При решении задачи:
Провести сравнительный анализ эффективности следующих методов сортировки:
1) линейный выбор с обменом, челночная сортировка, двоичная вставка;
2) сортировка Шелла, центрированная вставка;
3) стандартный обмен, быстрая сортировка, линейная вставка.
Предлагаемый тест: сортировка целочисленного массива размера n, элементы которого - случайные величины, распределенные в интервале (0, N-1).
возникла проблема. Не получается найти более менее вменяемого объяснения принципов сортировки двоичной вставкой, и примеров реализации.
Первый сегмент, в котором необходимо так же реализовать метод двоичной вставки я решил так:
| Код |
/**/
_1: system("cls");
reset(A,A_backup,n);
printf("Линейный выбор с обменом.\n-------------------\nИсходный массив:\n");
show(A,n);
/**/
j=0;
index=-1;
koof[0]=0;
perest[0]=0;
for(j=0;j!=n;j++)
{
min_=16000;
for(int i=j;i<n;i++)
{
if(A[i]<min_)
{
min_=A[i];
index=i;
}
koof[0]++;
}
if(index!=-1)
{
buf=A[j];
A[j]=A[index];
A[index]=buf;
perest[0]++;
}
}
printf("Отсортированный массив:\n");
show(A,n);
printf("\nПроверок - %d Перестановок - %d\n",koof[0],perest[0]);
/**/
reset(A,A_backup,n); //восстановление массива
printf("\nЧелночная сортировка.\n-------------------\nИсходный массив:\n");
show(A,n);
/**/
koof[1]=0;
perest[1]=0;
k=n-1;
// границы неотсортированной части массива
niz=1;
verh=n-1;
do
{
for (j=niz;j<=verh;j++)
{
koof[1]++;
if (A[j-1]>A[j])
{
swap(A,j-1,j);
perest[1]++;
k=j;
}
}
verh=k-1;
for (j=verh;j>=niz;j--)
{
koof[1]++;
if (A[j-1]>A[j])
{
swap(A,j-1,j);
perest[1]++;
k=j;
}
}
niz=k+1;
} while (niz<verh); // если низ и верх встретятся - сортировка закончена
printf("Отсортированный массив:\n");
show(A,n);
printf("\nПроверок - %d Перестановок - %d\n",koof[1],perest[1]);
/**/
reset(A,A_backup,n); //восстановление массива
printf("\nДвоичная вставка.\n-------------------\nИсходный массив:\n");
show(A,n);
/**/
koof[2]=0;
perest[2]=0;
//
// двоичная вставка
// двоичная вставка
// двоичная вставка
// двоичная вставка
//
//
printf("Отсортированный массив:\n");
show(A,n);
printf("\nПроверок - %d Перестановок - %d\n",koof[2],perest[2]);
getch();
goto end;
/**/
|
Пользовался ли кто-нибудь этим способом сортировки? Каков его принцип? Ну и было бы просто замечательно взглянуть на пример реализации.
Заранее большое спасибо за помощь. |