Архив форумов ЦИТФорума

[Настя]

не могли бы вы мне помочь написать функции сортировки целочисленного массива размером n:
центрированной вставкой;
двоичной вставкой.
?
заранее большое спасибо.

центрированная вставка:
представим рабочий массив состоящим из 2х ветвей-нисходящей(левой) и восходящй(правой). Центральный элемент этого массива - медиана.
в позицию, расположенную в середине рабочего массива, помещается первый элемент(он и будет медианой). Нисходящая и восходящая ветви имеют указатели, кот. показываеют на ближайшие к началу и концу занятые позиции. После загрузки первого элемента в центральную позицию оба указателя совпадают и показывают на него. Следующий элемент исходного массива сравнивается с медианой. Если новый элемент меньше, то он размещается на нисходящей ветви, в противном случае - на ворсходящей ветви. Кроме того соответствующий концевой ук-ль продвигается на единицу вниз(нисходящая ветвь) или единицу вверх(восходящая ветвь).
Каждый последующий элемент исходного массива сравнив-ся вначале с медианой, а затем с элементами на соответствующей ветви до тех пор, пока не займет нужную позицию. Если область памяти, выделенная для одной ветви, будет исчерпана, то все элементы рабочего массива сдвигаются в противоположном направлении. Величина сдвига может варьироваться.

двоичная вставка:
использует для отыскания места вставки алгоритм двоичного поиска, т.е. при вставке j-го элемента, он сравнивается вначале с элементом [j/2], затем, если он меньше, сравниваеться с элементом [j/4], а если больше - с [j/2]+[j/4] и.т.д. до тех пор, пока он не найдет свое место.
Все элементы рабочего массива, начиная с позиции вставки и ниже, сдвигаются на одну позицию вниз, освобождая место для j-го элемента.

[ValeraGhost]

void sortCEN(int *array,int n)
{
int i,j,*arab,med,left,right,k=0,l=0;
arab=(int*)calloc(n,sizeof(int));
(n%2==0)?med=n/2:med=n/2+1;
arab[med]=array[0];
right=left=med;
k=0;
l=0;
for(i=1;i<n;i++)
{

if(array[i]<arab[med])
{
left--;
j=med;
while(array[i]<=arab[j]&&j>=left)
{
j--;
// if(j==1) {arab[0]=array[i];break;}
}
if(array[i]>arab[j])
{
for(k=0;k<j;k++)
{
arab[k]=arab[k+1];
}
}
arab[j]=array[i];

//printf("j %d arab[j] %d \n",j,arab[j]);

}

if(array[i]>=arab[med])
{
right++;
j=med;
while(array[i]>=arab[j]&&j<right)
{
j++;
//if(j==n-2) { arrab[n-1]=array[i]; break;}
}
if(array[i]<arab[j])
{
for(l=right;l>j;l--)
{
arab[l]=arab[l-1];
}
}
arab[j]=array[i];

//printf("j %d arab[j] == %d\n",j,arab[j]);

}

if(left==0)
{
int temp,perem;
for(perem=right;perem>0;perem--)
{
arab[perem]=arab[perem-1];
}
left=left+1;
right=right+1;

}
if(right==n)
{
int temp,perem;
for(perem=0;perem<right;perem++)
{
arab[perem]=arab[perem+1];
}
left=left-1;
right=right-1;
}


}

for(i=0;i<n;i++)
{
printf("%3d ",arab[i]);
}


}

[бинарная]

void Binsort(int *PtrMass, int count)
{
int i, j, pos, a, b, middle, num;

for (i=1; i < count; i++)
{
a=0; /* Hижняя граница поиска = 1-му эл-ту */
b=i; /* Верхняя = со 2 по count */
EXCHANGES++;
num=PtrMass[i]; /* Число для кот. нужно найти место */

while ( a!=b ) /* ...пока границы не слились... */
{
middle=(a+b)/2; /* Целая часть ср.арифм. суммы границ */

if (num > PtrMass[middle]) /* ..если число >числа стоящ.под */
{ /* номером middle то: */
a=middle+1; /* ниж. гран. = центру+1 */
} /* */
else /* или */
{ /* */
b = middle; /* верхняя граница = центру... */
}
CONDITIONS++;
ITERATION++;
}
pos=a; /* Содержит найденную позицию на кот. */
/* нужно поставить число */

for (j=i; j > pos; j--)
{ /* Подвигаем (на 1 вправо) эл-ты */
PtrMass[j]=PtrMass[j-1]; /* массива лежащие перед элементом, */
EXCHANGES++;
ITERATION++; /* для которого ищется место осво-
*/
} /* бождая 1 место */

PtrMass[pos]=num; /* Устанавливаем элемент на место */
}
}

[ValeraGhost]

void Binsort(int *PtrMass, int count)
{
int i, j, pos, a, b, middle, num;

for (i=1; i < count; i++)
{
a=0; /* Hижняя граница поиска = 1-му эл-ту */
b=i; /* Верхняя = со 2 по count */
EXCHANGES++;
num=PtrMass[i]; /* Число для кот. нужно найти место */

while ( a!=b ) /* ...пока границы не слились... */
{
middle=(a+b)/2; /* Целая часть ср.арифм. суммы границ */

if (num > PtrMass[middle]) /* ..если число >числа стоящ.под */
{ /* номером middle то: */
a=middle+1; /* ниж. гран. = центру+1 */
} /* */
else /* или */
{ /* */
b = middle; /* верхняя граница = центру... */
}
CONDITIONS++;
ITERATION++;
}
pos=a; /* Содержит найденную позицию на кот. */
/* нужно поставить число */

for (j=i; j > pos; j--)
{ /* Подвигаем (на 1 вправо) эл-ты */
PtrMass[j]=PtrMass[j-1]; /* массива лежащие перед элементом, */
EXCHANGES++;
ITERATION++; /* для которого ищется место осво-
*/
} /* бождая 1 место */

PtrMass[pos]=num; /* Устанавливаем элемент на место */
}
}