1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза..

Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N²), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N² свидетельствует о том, что алгоритм неэффективен при большом N , т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.

Независимо от отсортированности массива, количество перестановок равно длине массива N. То есть эффективность алгоритма по перестановкам имеет линейную сложность.

Число перестановок: min=0, max= N² , med= N²/2

Число сравнений:  N²

Пример

К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

С 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

С1 6 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1

К1 сравнивается с остальными, если больше Сn, то 1, если меньше – 0, потом количество нулей вписывается в С1.

Считаем, сколько элементов меньше первого элемента массива (503), затем – сколько элементов меньше второго числа(087), и т.д. Число 503 по значению превышает только шесть чисел. и.т.д

С2 6 1 2 0 2 1 2 1 1 1 1 2 2 2 2 2

С3 6 1 6 0 3 1 3 1 2 1 1 2 3 3 3 3

С4 6 1 8 0 4 2 4 …

…

С15 6 1 8 0 15 3 14 4 10 5 2 7 9 11 13 12

Фрагмент программы:

For (i=0; i<n-1; i++)

For (i=i+1; j<n; j++)

{ if (k[i]>k[j]) c[i]++;

Else c[j]++;

}

2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Этот метод – один из простейших, и он работает очень хорошо для небольших

файлов. Кроме того, хотя сортировка выбором является методом «грубой силы», он имеет

очень важное применение: поскольку каждый элемент передвигается не более чем

раз, то он очень хорош для больших записей с маленькими ключами.

Идея сортировки выбором заключается в поиске максимального элемента и вставки его в конец массива. Затем длина массива уменьшается на один элемент («водворенный на свое место» исключается) и процедура повторяется снова. Алгоритм сортировки выполняется до тех пор, пока длина сортируемого массива не станет равна двум элементам.

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

Число сравнений: N²

Число перестановок: N

Пример

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	1 23 5 65 44 33 8 6
Шаг 2	1 5 23 65 44 33 8 6
Шаг 3	1 5 6 65 44 33 8 23
Шаг 4	1 5 6 8 44 33 65 23
Шаг 5	1 5 6 8 33 44 65 23
Шаг 6	1 5 6 8 23 44 65 33
Шаг 7	1 5 6 8 23 33 65 44
Шаг 8	1 5 6 8 23 33 44 65

Фрагмент программы:

For (i=n; i>1; i--)

{nmax=n

For(j=i-1; i>0; j--)

{if(k[j]>k[nmax])

Nmax=j;

}

{ktemp=k[i];

K[i]=k[nmax]

K[nmax]=ktemp;

}

}