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

UptoLike

ВУЗ: 

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

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

Рубрика: 

// Разделить массив в интервале a…b на две части а…i-1
// и i…b относительно значения V по принципу <V, >=V
sort_recurs (A, a, i-1);
sort_recurs (A, i, b);
}
Необходимо следить, чтобы разделяемые части содержали хотя бы один элемент.
Разделение лучше всего производить в отдельном массиве, после чего разделенные час-
ти перенести обратно. Ниже приведен алгоритм разделения массива. Разделение легко
сделать, заполняя выходной массив с двух концов, слева и справа от медианы.
int division(int A[], int B[], int n, int middle)
{ //A[] - входной B[] - выходной
int i, j, k;
for (i=0,j=0,k=n-1;i<n;i++)
{
if(A[i]<middle) // в левую часть
B[j++]=A[i];
else B[k--]=A[i]; //в правую часть
}
return j; // вернуть точку разделения
}
«Быстрая» сортировка производит разделение в одном массиве с использованием
оригинального алгоритма на основе обмена. Сравнение элементов производится с кон-
цов массива (i=a, j=b) к середине (i++ или j--), причем «укорочение» происходит только
с одной из сторон. После каждой перестановки меняется тот конец, с которого выполня-
ется «укорочение». В результате этого массив разделяется на две части относительно
значения первого элемента A[a], который и становится медианой.
void sort_quick (int A[], int a, int b)
{
int i, j, mode;
if (a>=b) return; // Размер части =0
for (i=a, j=b, mode=1; i < j; mode > 0 ? j-- : i++)
if (A[i] > A[j])
{ // Перестановка концевой пары
int buf = A[i];
A[i] = A[j];
A[j]=buf;
mode = -mode; // со сменой сокращаемого конца
}
sort_quick (A, a, i-1);
sort_quick (A, i+1, b);
}
Очевидно, что медиана делит массив на две неравные части. Алгоритм разделения
можно выполнить итерационно, применяя его к той части массива, которая содержит его
середину (по аналогии с двоичным поиском). Тогда в каждом шаге итерации медиана
будет сдвигаться к середине массива.
52
        // Разделить массив в интервале a…b на две части а…i-1
        // и i…b относительно значения V по принципу =V
        sort_recurs (A, a, i-1);
        sort_recurs (A, i, b);
}

     Необходимо следить, чтобы разделяемые части содержали хотя бы один элемент.
Разделение лучше всего производить в отдельном массиве, после чего разделенные час-
ти перенести обратно. Ниже приведен алгоритм разделения массива. Разделение легко
сделать, заполняя выходной массив с двух концов, слева и справа от медианы.

int division(int A[], int B[], int n, int middle)
{ //A[] - входной B[] - выходной
        int i, j, k;
        for (i=0,j=0,k=n-1;i=b) return;            // Размер части =0
        for (i=a, j=b, mode=1; i < j; mode > 0 ? j-- : i++)
                  if (A[i] > A[j])
                  {        // Перестановка концевой пары
                          int buf = A[i];
                          A[i] = A[j];
                          A[j]=buf;
                          mode = -mode; // со сменой сокращаемого конца
                 }
        sort_quick (A, a, i-1);
        sort_quick (A, i+1, b);
}

     Очевидно, что медиана делит массив на две неравные части. Алгоритм разделения
можно выполнить итерационно, применяя его к той части массива, которая содержит его
середину (по аналогии с двоичным поиском). Тогда в каждом шаге итерации медиана
будет сдвигаться к середине массива.



                                                52

Страницы