Сортировка методом квадратичного выбора

Разделим n элементов в файле на групп по элементов в каждой группе. Найдем наибольший элемент в каждой группе и поместим его в некоторый вспомогательный массив. Найдем наибольший элемент в этом вспомогательном массиве. Этот элемент является наибольшим элементом в данном файле. Затем заменим этот элемент в массиве на следующий по величине элемент в той группе, из которой он поступил. Снова найдем наибольший элемент во вспомогательном массиве. Этот элемент — второй по величине в данном файле. Повторим этот процесс до тех пор, пока файл не будет отсортирован. Напишите программу, которая реализует сортировку методом квадратичного выбора.

Простой обмен (пузырьковая сортировка)

Попарно сравниваются (и при необходимости меняются местами) соседние элементы;

процесс повторяется для оставшихся n – 1 элемента с конца массива; каждый раз наименьший элемент оставшейся части "прогоняется" через эту часть.

Пример (символом # обозначен элемент, занявший окончательное место).

Сортировка методом подсчета

Эта сортировка выполняется следующим образом. Заводится некоторый массив count и элементу count[i] присваивается значение числа элементов, которые меньше или равны a[i]. Затем элемент a[i] помещается в позицию count[i] в выходном массиве. Напишите программу для сортировки массива a размером n, используя этот метод.

Сортировка методом распределяющего подсчета

Предположим, что некоторый массив mas содержит целые числа в диапазоне от а до b, причем многие числа повторяются несколько раз. Сортировка методом распределяющего подсчета выполняется следующим образом. Заводится вспомогательный массив number размером b–а + 1 и элементу number[i – a + 1] присваивается значение, равное тому, сколько раз число i появляется в исходном массиве. Затем значения в массиве соответственно переустанавливаются. Напишите программу для сортировки некоторого массива mas размером n, содержащего целые числа в диапазоне от а до b, используя этот метод.

Сортировка методом четных и нечетных транспозиций

Выполняются несколько раз просмотры исходного массива mas. На первом просмотре сравнивайте mas[i] с mas [i + 1] для всех нечетных i. На втором просмотре сравнивайте mas[i] с mas[i + 1] для всех четных i. Каждый раз, когда mas[i] > mas [i + 1] выполняйте транспозицию этих двух элементов. Продолжайте эти просмотры до тех пор, пока массив не будет отсортирован.

Что является условием окончания этой сортировки?

Напишите программу, реализующую эту сортировку.

Сортировка слиянием

Слияние является процессом объединения двух или более отсортированных массивов в некоторый третий отсортированный массив.