Методы сортировки в программировании: сортировка "пузырьком". Методы внешней сортировки
Не только не считается самым быстрым методом, более того, она замыкает перечень самых медленных способов упорядочивания. Однако и у нее есть свои плюсы. Так, сортировка методом пузырька - самое что ни на есть логичное и естественное решение проблемы, если необходимо расставить элементы в определенном порядке. Обычный человек вручную, к примеру, воспользуется именно им - просто по интуиции.
Откуда взялось такое необычное название?
Название метода придумали, используя аналогию с воздушными пузырьками в воде. Это метафора. Подобно тому, как маленькие пузыри воздуха поднимаются наверх - ведь их плотность больше, чем какой-либо жидкости (в данном случае - воды), так и каждый элемент массива, чем меньше он по значению, тем больше он постепенно пробирается к началу перечня чисел.
Описание алгоритма
Сортировка пузырьком выполняется следующим образом:
- первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
- следовательно, попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
- поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений - минус один;
- у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
- подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.
Еще короче алгоритм будущей программы можно записать так:
- массив чисел проверяется до тех пор, пока не будут найдены какие-либо два числа, причем второе из них обязано быть больше первого;
- неправильно расположенные по отношению друг к другу элементы массива программа меняет местами.
Псевдокод на основе описанного алгоритма
Самая простая реализация выполняется так:
Процедура Sortirovka_Puzirkom ;
Начало
цикл для j от nachalnii_index до konechii_index ;
цикл для i от nachalnii_index до konechii_index-1 ;
если massiv[i]>massiv
(меняем значения местами);
Конец
Конечно, здесь простота только усугубляет ситуацию: чем проще алгоритм, тем более в нем проявляются все недостатки. Затратность времени слишком велика даже для небольшого массива (тут вступает в дело относительность: для обывателя количество времени может казаться маленьким, но в деле программиста каждая секунда или даже миллисекунда на счету).
Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами:
Процедура Sortirovka_Puzirkom ;
Начало
sortirovka = истина;
цикл пока sortirovka = истина;
sortirovka = ложь;
цикл для i от nachalnii_index до konechii_index-1 ;
если massiv[i]>massiv (первый элемент больше второго), то:
(меняем элементы местами);
sortirovka = истина; (обозначили, что обмен был произведен).
Конец.
Недостатки метода
Основной минус - продолжительность процесса. Сколько же времени выполняется пузырьком?
Время выполнения рассчитывается из квадрата количества чисел в массиве - конечный результат ему пропорционален.
При наихудшем варианте массив будет пройден столько же раз, сколько в нем имеется элементов минус одно значение. Так происходит потому, что в конечном итоге остается только один элемент, который не с чем сравнивать, и последний проход по массиву становится бесполезным действом.
Кроме того, эффективен метод сортировки простыми обменами, как его еще называют, только для массивов небольшого размера. Большие объемы данных с его помощью обработать не получится: результатом станут либо ошибки, либо сбой работы программы.
Достоинства
Сортировка пузырьком весьма проста для понимания. В учебных программах технических ВУЗов при изучении упорядочивания элементов массива ее проходят в первую очередь. Метод легко реализуется как на языке программирования Delphi (Д (Делфи), так и на C/C++ (Си/Си плюс плюс), невероятно простой алгоритм расположения значений в верном порядке и на Сортировка пузырьком идеально подходит для начинающих.
По причине недостатков алгоритм не применяют во внеучебных целях.
Наглядный принцип сортировки
Изначальный вид массива 8 22 4 74 44 37 1 7
Шаг 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Шаг 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Шаг 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Шаг 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 7 1 4 7 8 22 37 44 74
Пример сортировки пузырьком на языке Pascal
Пример:
const kol_mas=10;
var massiv:array of integer;
a, b, k: integer;
writeln ("input", kol_mas, "elements of array");
for a:=1 to kol_mas do readln(massiv[a]);
for a:=1 to kol_mas-1 do begin
for b:=a+1 to kol_mas do begin
if massiv[a]>massiv[b] then begin
k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;
end;
writeln ("after sort");
for a:=1 to kol_mas do writeln(massiv[a]);
Пример сортировки пузырьком на языке С (Си)
#include
#include
int main(int argc, char* argv)
int massiv = {36, 697, 73, 82, 68, 12, 183, 88},i, ff;
for (; ;){
ff = 0;
for (i = 7; i>0; i--){
if (massiv[i] < massiv) {
swap (massiv[i],massiv);
if (ff == 0) break;
getch(); // задержка экрана
Сортировка Шелл.
Представляет собой модификацию метода вставок. Используются сравнения и перестановки элементов, но в отличие от метода вставок, в сравнении участвуют не соседние, а отстоящие друг от друга на определенном расстоянии элементы. При необходимости перестановки, элементы перемещаются скачком на данное расстояние, а не на одну позицию.
В одной из модификаций метода (в случае, предложенном Д. Шеллом) шаг кратен степеням двойки. Вначале последовательность из N элементов делится на N/2 групп, если N – четно, и на (N-1)/2 групп, если N – нечетно. Каждая группа содержит по два элемента, если количество элементов было нечетным, одна из групп содержит три элемента. Элементы каждой группы отстоят друг от друга на расстоянии N/2 или (N-1)/2. В течение первого прохода осуществляется упорядочение элементов каждой группы методом вставок. Для осуществления следующего прохода шаг уменьшается вдвое (как и число групп), по отношению к предыдущему шагу (у дробных чисел берется целая часть). Процесс повторяется до тех пор, пока шаг не станет равным единице. В этом случае методом вставок сортируется весь список (одна группа). С точки зрения программной реализации потребуется неоднократный вызов сортировки вставками с указанием, в качестве параметров (помимо исходного списка и числа элементов), индекса начального элемента группы и шага. Приблизительное число сравнений составляет N log 2 N.
// Функция сортировки Шелла целочисленного массива
// Аргументы:
// arr - сортируемый массив
// size - размер сортируемого массива
void SortShell(int* arr, int size) {
int step = size / 2;
while (step != 0) {
// Сортируем группы элементов отстоящих друг от друга на значение шага вставками
for (int i = step; i < size; ++i) {
int tmp = arr[i];
for (j = i - step; j >= 0 && arr[j] > tmp; j -= step)
arr = arr[j];
arr = tmp;
Сортировка выбором
В процессе первого прохода в исходном массиве находятся минимальный элемент, который помещается на место первого элемента. Первый элемент помещается на место минимального. На втором и последующих проходах поиск и обмен повторяются для оставшихся после предыдущего прохода элементов (с позициями: на втором проходе – со второй по последнюю, на третьем проходе – с третьей по последнюю и т.д.) до тех пор, пока не будет отсортирована вся последовательность. Общее число сравнений составляет приблизительно 0,5 N 2 , N – здесь и далее число элементов.
void selectSort(int a, long size) {
for(i=0; i < size; i++) { // i - номер текущего шага
for(j=i+1; j < size; j++) // цикл выбора наименьшего элемента
if (a[j] < x) {
k=j; x=a[j]; // k - индекс наименьшего элемента
a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]
Сортировка пузырьком
В процессе сортировки производится попарное сравнение соседних элементов. Если порядок следования соседних элементов нарушен, то они меняются местами. В процессе первого прохода максимальный элемент попадает на последнее место и, следовательно, в последующих сравнениях не участвует. Остальные элементы "всплывают" на одну позицию вверх (поэтому метод часто называют сортировкой "пузырьком"). На каждом следующем проходе рассматривается последовательность для N-1, N-2 и т.д. элементов. Если при каком-либо проходе не было произведено ни одной перестановки, последовательность отсортирована. Максимальное число сравнений составляет приблизительно 0,5 N 2 , среднее число сравнений пропорционально 0,25 N 2 , среднее число обменов – 0,25 N 2 .
void bubbleSort(int a, long size) {
for(i=0; i < size; i++) { // i - номер прохода
for(j = size-1; j > i; j--) { // внутренний цикл прохода
if (a > a[j]) {
x=a; a=a[j]; a[j]=x;
Сортировка вставками
Первый элемент исходного списка считается отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. В целом, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Среднее число сравнений пропорционально N 2 .
void insertSort(int a, long size) {
for (i=0; i < size; i++) { // цикл проходов, i - номер прохода
// поиск места элемента в готовой последовательности
for (j=i-1; j>=0 && a[j] > x; j--)
a = a[j]; // сдвигаем элемент направо, пока не дошли
// место найдено, вставить элемент
Метод подсчёта
Метод основан на том, что k+1-ый элемент упорядоченной последовательности превышает ровно k элементов, и следовательно занимает k+1-ую позицию. В процессе сортировки на каждом i-ом проходе i-ый элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Инициализированный нулем перед началом прохода счетчик k увеличивается, если i-ый элемент оказался больше текущего. Таким образом, порядковый номер i-го элемента, по окончанию i-го прохода, равен k+1. Для сортировки последовательности из N элементов требуется N проходов, на каждом из которых выполняется N сравнений. Число сравнений равно N 2 . Приведенный метод подсчета можно использовать,
void insertSort(int a, long size)
int *b=new int;
for
(int
i=0;i for
(int
j=0;j if
(a[i]>a[j]){ Сортировка
по дереву (6)
Процесс
сортировки состоит из: фазы построения
двоичного дерева поиска и фазы обхода.
Структура двоичного дерева задается с
помощью связного списка, каждый элемент
которого может иметь, максимум, двух
потомков (две ссылки). Двоичное дерево
формируется по всем исходным элементам,
по следующему правилу. Первый элемент
исходной последовательности является
первым узлом дерева. Следующий элемент
последовательности сравнивается со
значениями в узлах строящегося дерева,
начиная с корня. Если значение текущего
элемента больше значения элемента в
узле дерева, следует переместиться вниз
по правой ссылке от текущего узла, в
противном случае – по левой ссылке.
Перемещение по дереву продолжается до
тех пор, пока не будет достигнута
свободная ссылка, после чего осуществляется
вставка элемента в дерево. После
формирования дерева необходимо провести
процедуру смешанного обхода. Он
заключается в рекурсивном посещении
(чтении) узлов, начиная с корня: левого
поддерева, узла, правого поддерева. В
результате получается отсортированная
последовательность. Среднее число
сравнений aN log 2
N, 1 < a < 2. Сбалансированное
N-ленточное слияние
Общей
формой внешней сортировки является
N-ленточное слияние. Для N-ленточного
слияния потребуется 2N магнитных лент
и 2N лентопротяжных устройств (которые
можно заменить 2N файлами на устройстве
внешней памяти). Исходная неупорядоченная
последовательность размещается на
первой магнитной ленте. Затем она
разносится на N магнитных лент по
следующему правилу: первая запись – на
первую из N лент, вторая – на вторую,
(N+1)-ая – снова на первую из N лент. Сбалансированное
N-ленточное слияние осуществляется в
два этапа. На первом этапе из записей,
хранящихся на каждой магнитной ленте,
формируются упорядоченные цепочки. Так
как все цепочки имеют одинаковую длину,
слияние называется сбалансированным.
Упорядочение цепочки происходит в
оперативной памяти одним из методов
внутренней сортировки. Упорядоченные
цепочки размещаются на N свободных
магнитных лентах, после чего начинается
второй этап сортировки – слияние.
Процесс слияния осуществляется в
несколько циклов. После каждого цикла
слияния длина упорядоченных цепочек
увеличивается на N.
В конечном итоге, формируется упорядоченная
последовательность из N составляющих.
Собственно слияние осуществляется
следующим образом. Пусть имеются две
цепочки длиной l
,
изначально упорядоченные. Необходимо
получить одну упорядоченную цепочку.
Для этого: сравниваются первые элементы
двух цепочек, меньшая переписывается
в результирующую цепочку; операция
осуществляется с помощью трех счетчиков;
после записи в результирующую
последовательность увеличивается на
единицу счетчик результирующей
последовательности и счетчик
последовательности, в которой был
обнаружен меньший элемент; действие
повторяется до тех пор, пока один из
счетчиков исходной последовательности
не достигнет значения конца
последовательности, после чего оставшиеся
элементы другой последовательности
дописываются в конец результирующей.
Таким образом, будут упорядочены каждая
из N магнитных лент. МЕТОДЫ СОРТИРОВКИ При разработке программного обеспечения очень распространенной операцией является сортировка значений, т.е. расположение списка элементов в некотором порядке (например, слова по алфавиту или числа в возрастающем или убывающем порядке). Существует множество алгоритмов сортировки элементов. Наиболее простой из них - метод «пузырька». Алгоритм реализуется в виде двух вложенных циклов. Во внутреннем цикле просматриваются по порядку все элементы массива, попарно сравниваются рядом стоящие элементы, и если второй больше первого (при сортировке по убыванию) элементы меняются местами. Параметром внутреннего цикла является индекс(номер) элемента массива. Для полной сортировки такая перестановка должна быть выполнена n-1 раз, где n - количество элементов в массиве. Для этого организуется внешний цикл, параметром которого является шаг сортировки. Пример. Отсортировать элементы одномерного массива целых чисел по возрастанию. На рисунке 1 приведена последовательность перестановки элементов. Рисунок 1. Сортировка методом «пузырька» Хотя в предложенном примере сортировка выполнилась за четыре шага, проверка элементов будет продолжаться еще две итерации, т.к. полное число итераций на единицу меньше размерности массива. На рисунке 2 приведена блок-схема рассмотренного алгоритма. Рисунок 2. Блок-схема алгоритма сортировки методом «пузырька» Переменная m введена для возможности обмена значениями между двумя переменными, k отвечает за шаги сортировки. Программа на языке С++ по данному алгоритму будет выглядеть следующим образом. Рисунок 3. Программа сортировки элементов массива методом «пузырька» Сортировка пузырьковым методом является неэффективным методом, вследствие большого числа сравнений. Более эффективным является метод прямого выбора На первом шаге последовательно происходит просмотр всего списка значений и выбор из него минимального или максимального (в зависимости от порядка сортировки), далее расположение его в первой позиции обменом с элементом, стоявшим там ранее. Затем эта процедура повторяется, но поиск минимального (максимального) значения происходит уже со второй позиции и т.д. Схема этого алгоритм представлена на рисунке 4. сортировка значение программный обеспечение Рисунок 4. Сортировка методом прямого выбора Фрагмент программы, с помощью которого реализуется сортировка методом прямого выбора, приведен ниже. // сортируем элементы массива по возрастанию int temp;//переменная для временного хранения при обмене значениями int i;//переменная управления циклом (номер элемента массива) int k;//переменная управления циклом (номер шага сортировки) int nmin;//номер минимального значения for (к=0; i < к 1; i++) // ищем номер минимального элемента среди значений list [ i … n -1] for (i = k+1; i< n; i++) if (list[i] < list[ nmin ]) nmin = i; //меняем местами list[ nmin ] и list[ k ] temp = list[ nmin ]; list[ nmin ]= list[ k ]; list[ k ] = temp; Следует отметить, что поиск минимального значения во внутреннем цикле происходит в оставшейся части списка. Чтобы произвести сортировку по убыванию, нужно на каждом шаге вместо минимального значения находить максимальное значение. Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу. Void Swap(T items, int left, int right)
{
if (left != right)
{
T temp = items;
items = items;
items = temp;
}
}
Сортировка пузырьком - это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива. Например, у нас есть массив целых чисел: При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так: Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так: Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6. И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз. При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу. Public void Sort(T items)
{
bool swapped;
do
{
swapped = false;
for (int i = 1; i < items.Length; i++) {
if (items.CompareTo(items[i]) > 0)
{
Swap(items, i - 1, i);
swapped = true;
}
}
} while (swapped != false);
}
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее - нет. Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса - уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом: Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным. Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать: Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным. На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно. Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки. Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так: Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки. Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена. Public void Sort(T items)
{
int sortedRangeEndIndex = 1;
while (sortedRangeEndIndex < items.Length)
{
if (items.CompareTo(items) < 0)
{
int insertIndex = FindInsertionIndex(items, items);
Insert(items, insertIndex, sortedRangeEndIndex);
}
sortedRangeEndIndex++;
}
}
private int FindInsertionIndex(T items, T valueToInsert)
{
for (int index = 0; index < items.Length; index++) {
if (items.CompareTo(valueToInsert) > 0)
{
return index;
}
}
throw new InvalidOperationException("The insertion index was not found");
}
private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom)
{
// itemArray = 0 1 2 4 5 6 3 7
// insertingAt = 3
// insertingFrom = 6
//
// Действия:
// 1: Сохранить текущий индекс в temp
// 2: Заменить indexInsertingAt на indexInsertingFrom
// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1
// Сдвинуть элементы влево на один.
// 4: Записать temp на позицию в массиве + 1.
// Шаг 1.
T temp = itemArray;
// Шаг 2.
itemArray = itemArray;
// Шаг 3.
for (int current = indexInsertingFrom; current > indexInsertingAt; current--)
{
itemArray = itemArray;
}
// Шаг 4.
itemArray = temp;
}
Сортировка выбором - это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце. Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве. При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало. Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n — 1. На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию. Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован. После еще двух проходов алгоритм завершает свою работу: Public void Sort(T items)
{
int sortedRangeEnd = 0;
while (sortedRangeEnd < items.Length)
{
int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd);
Swap(items, sortedRangeEnd, nextIndex);
sortedRangeEnd++;
}
}
private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd)
{
T currentSmallest = items;
int currentSmallestIndex = sortedRangeEnd;
for (int i = sortedRangeEnd + 1; i < items.Length; i++)
{
if (currentSmallest.CompareTo(items[i]) > 0)
{
currentSmallest = items[i];
currentSmallestIndex = i;
}
}
return currentSmallestIndex;
}
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer)
. Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма. Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много - до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную. Насколько эффективны эти алгоритмы? Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске. При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке. Давайте посмотрим на такой массив: Разделим его пополам: И будем делить каждую часть пополам, пока не останутся части с одним элементом: Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке. Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив. Для работы алгоритма мы должны реализовать следующие операции: Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием - не самое лучшее решение, когда надо отсортировать частично упорядченный массив. Public void Sort(T items)
{
if (items.Length <= 1)
{
return;
}
int leftSize = items.Length / 2;
int rightSize = items.Length - leftSize;
T left = new T;
T right = new T;
Array.Copy(items, 0, left, 0, leftSize);
Array.Copy(items, leftSize, right, 0, rightSize);
Sort(left);
Sort(right);
Merge(items, left, right);
}
private void Merge(T items, T left, T right)
{
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
int remaining = left.Length + right.Length;
while(remaining > 0)
{
if (leftIndex >= left.Length)
{
items = right;
}
else if (rightIndex >= right.Length)
{
items = left;
}
else if (left.CompareTo(right) < 0)
{
items = left;
}
else
{
items = right;
}
targetIndex++;
remaining--;
}
}
Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги: Давайте посмотрим на работу алгоритма на следующем массиве: Сначала мы случайным образом выбираем ключевой элемент: Int pivotIndex = _pivotRng.Next(left, right);
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого - в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре). Перемещение значений осуществляется методом partition . На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива. У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу. Random _pivotRng = new Random();
public void Sort(T items)
{
quicksort(items, 0, items.Length - 1);
}
private void quicksort(T items, int left, int right)
{
if (left < right)
{
int pivotIndex = _pivotRng.Next(left, right);
int newPivot = partition(items, left, right, pivotIndex);
quicksort(items, left, newPivot - 1);
quicksort(items, newPivot + 1, right);
}
}
private int partition(T items, int left, int right, int pivotIndex)
{
T pivotValue = items;
Swap(items, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++)
{
if (items[i].CompareTo(pivotValue) < 0)
{
Swap(items, i, storeIndex);
storeIndex += 1;
}
}
Swap(items, storeIndex, right);
return storeIndex;
}
На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#. В данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы. Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения). В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36. Selection sort (сортировка выбором)
– суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2). Bubble sort (сортировка пузырьком)
– данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2). Insertion sort (сортировка вставками)
– алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2). Quick sort (быстрая сортировка)
– суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n). Comb sort (сортировка расческой)
– идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n). Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм. Полностью неотсортированный массив: Частично отсортированный массив (половина элементов упорядочена): Результаты, предоставленые в графиках: В результате проведенного исследования и полученных данных, для сортировки неотсортированного массива, наиболее оптимальным из представленных алгоритмов для сортировки массива является быстрая сортировка. Несмотря на более длительное время выполнения алгоритм потребляет меньше памяти, что может быть важным в крупных проектах. Однако такие алгоритмы как сортировка выбором, обменом и вставками могут лучше подойти для научных целей, например, в обучении, где не нужно обрабатывать огромное количество данных. При частично отсортированном массиве результаты не сильно отличаются, все алгоритмы сортировки показывают время примерно на 2-3 миллисекунды меньше. Однако при сортировке частично отсортированного массива быстрая сортировка срабатывает намного быстрее и потребляет меньшее количество памяти.
Пузырьковая сортировка
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Разделяй и властвуй
Сортировка слиянием
Быстрая сортировка
Заключение
Для проведения исследования были выбраны следующие алгоритмы сортировки:
