Программирование на языке высокого уровня. Марапулец Ю.В. - 51 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

шаг цикла один элемент из входных последовательностей переносится в выходную.
Движение по группам разложено на две составляющие: k - общий индекс начала обеих
групп, a i1, i2 - относительные индексы внутри групп. Здесь же отрабатывается «скачок»
к следующей паре групп: при условии, что обе группы закончились (i1==s && i2==s),
обнуляются относительные индексы в группах, а индекс начала увеличивается на длину
группы. В процессе слияния отрабатываются четыре возможные ситуации: завершение
первой или второй группы и выбор минимального из пары очередных элементов групп -
в противном случае.
void sort_cycle (int A[], int n)
{
int B1[100], B2[100];
int i, i1 ,i2, s, a1 ,a2, a, k;
for (s=1; s!=n; s*=2) // Размер группы кратен 2
{
for (i=0; i<n/2; i++) // Разделить пополам
{
B1[i]=A[i];
B2[i]=A[i+n/2];
}
i1=i2=0;
for (i=0,k=0; i<n; i++) // Слияние с переходом " скачком"
{
if (i1==s && i2==s) // при достижении границ
k+=s, i1=0, i2=0; //обеих групп
//4 условия слияния по окончании групп и по сравнению
if (i1==s)
A[i]=B2[k+i2++];
else if (i2==s)
A[i]=B1[k+i1++];
else if (B1[k+i1] < B2[k+i2 ])
A[i]=B1 [k+i1 ++];
else
A[i]=B2[k+i2++];
}
}
}
Сортировки рекурсивным разделением. Сортировки разделяют массив на две
части относительно некоторого значения, называемого медианой. Медианой может быть
выбрано любое «среднее» значение, например, среднее арифметическое. Сами части не
упорядочены, но обладают таким свойством, что элементы в левой части меньше медиа-
ны, а в правой - больше. Благодаря такому свойству эти части можно сортировать неза-
висимо друг от друга. Для этого нужно вызвать ту же самую функцию сортировки, но
уже по отношению не к массиву, а к его частям. Функции, вызывающие сами себя, на-
зываются рекурсивными и будут рассмотрены далее. Рекурсивный вызов продолжается
до тех пор, пока очередная часть массива не станет содержать единственный элемент:
void sort_recurs(int A[], int a, int b)
{
int i;
if (a>=b)
return;
51
шаг цикла один элемент из входных последовательностей переносится в выходную.
Движение по группам разложено на две составляющие: k - общий индекс начала обеих
групп, a i1, i2 - относительные индексы внутри групп. Здесь же отрабатывается «скачок»
к следующей паре групп: при условии, что обе группы закончились (i1==s && i2==s),
обнуляются относительные индексы в группах, а индекс начала увеличивается на длину
группы. В процессе слияния отрабатываются четыре возможные ситуации: завершение
первой или второй группы и выбор минимального из пары очередных элементов групп -
в противном случае.

void sort_cycle (int A[], int n)
{
        int B1[100], B2[100];
        int i, i1 ,i2, s, a1 ,a2, a, k;
        for (s=1; s!=n; s*=2) // Размер группы кратен 2
        {
                  for (i=0; i=b)
               return;

                                               51

Страницы