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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Если просмотр делать попеременно в двух направлениях и фиксировать нижнюю и
верхнюю границы неупорядоченной части, то в результате получим классическую Шей-
кер-сортировку.
Сортировка подсчетом - сортировка, требующая обязательного выходного масси-
ва, поскольку элементы в нем размещаются не подряд. Идея алгоритма: число элемен-
тов, меньше текущего, определяет его позицию (индекс) в выходном массиве. Наличие
переменной - счетчика и использование его в качестве индекса в выходном массиве яв-
ляются хорошо заметными программными контекстами. Трудоемкость алгоритма -
N*N/2.
void sort_calc (int A[],int B[], int n)
{
int i, j , k; // k - счетчик элементов, больших текущего
for (i=0; i< n; i++)
{
for ( k=0, j=0; j<n; j++)
if (A[j] < A[i])
k++;
B[k]=A[i]; // Место элемента в выходном массиве
}
}
Этот фрагмент некорректно работает, если в массиве имеются равные элементы.
Сортировка слиянием. Первоначально рассмотрим алгоритм слияния упорядо-
ченных последовательностей. Каждый шаг слияния включает выбор минимального из
двух очередных элементов и перенос его в выходную последовательность. Каждый мас-
сив имеет собственный индекс, но только индекс выходного массива меняется линейно,
поскольку за один шаг производится одно перемещение. Переход к следующему эле-
менту во входной последовательности происходит только в одной из них (где выбран
минимальный элемент), поэтому индексы изменяются неравномерно внутри условной
конструкции. Кроме этого, любая последовательность может закончится раньше, чем
противоположная, что необходимо отслеживать.
void sleave(int B[], intA1[], int A2[])
{
int i, j, k;
for(i=j=k=0;i<2*n;i++)
{
if(k==n)
B[i]=A1[j++]; //Второй кончился, сливать только 1
else if(j==n)
B[i]=A2[k++]; //Первый кончился, сливать только 2
else if(A1[j]<A2[k]) //Сливать меньший элемент
B[i]=A1[j++];
else B[i]=A2[k++];
}
}
49
     Если просмотр делать попеременно в двух направлениях и фиксировать нижнюю и
верхнюю границы неупорядоченной части, то в результате получим классическую Шей-
кер-сортировку.

      Сортировка подсчетом - сортировка, требующая обязательного выходного масси-
ва, поскольку элементы в нем размещаются не подряд. Идея алгоритма: число элемен-
тов, меньше текущего, определяет его позицию (индекс) в выходном массиве. Наличие
переменной - счетчика и использование его в качестве индекса в выходном массиве яв-
ляются хорошо заметными программными контекстами. Трудоемкость алгоритма -
N*N/2.

void sort_calc (int A[],int B[], int n)
{
        int i, j , k; // k - счетчик элементов, больших текущего
        for (i=0; i< n; i++)
        {
                  for ( k=0, j=0; j

Страницы