Пожалуй, самый простой алгоритм сортировок – это сортировка выбором. Судя по названию сортировки, необходимо что-то выбирать (максимальный или минимальный элементы массива). Алгоритм сортировки выбором находит в исходном массиве максимальный или минимальный элементы, в зависимости от того как необходимо сортировать массив, по возрастанию или по убыванию. Если массив должен быть отсортирован по возрастанию, то из исходного массива необходимо выбирать минимальные элементы. Если же массив необходимо отсортировать по убыванию, то выбирать следует максимальные элементы.

Допустим необходимо отсортировать массив по возрастанию. В исходном массиве находим минимальный элемент, меняем его местами с первым элементом массива. Уже, из всех элементов массива один элемент стоит на своём месте. Теперь будем рассматривать не отсортированную часть массива, то есть все элементы массива, кроме первого. В неотсортированной части массива опять ищем минимальный элемент. Найденный минимальный элемент меняем местами со вторым элементом массива и т. д. Таким образом, суть алгоритма сортировки выбором сводится к многократному поиску минимального (максимального) элементов в неотсортированной части массива. Отсортируем массив из семи чисел согласно алгоритму «Сортировка выбором».

исходный массив: 3 3 7 1 2 5 0
1)Итак, находим минимальный элемент в массиве. 0 – минимальный элемент
2)Меняем местами минимальный и первый элементы массива.
Текущий массив: 0 3 7 1 2 5 3
3) Находим минимальный элемент в неотсортированной части массива. 1 – минимальный элемент
4) Меняем местами минимальный и первый элементы массива.
Текущий массив: 0 1 7 3 2 5 3
5) min = 2
6) Текущий массив: 0 1 2 3 7 5 3
7)min = 3
8) Текущий массив: 0 1 2 3 7 5 3 в массиве ничего не поменялось, так как 3 стоит на своём месте
9) min = 3
10) Конечный вид массива: 0 1 2 3 3 5 7 – массив отсортирован

Запрограммируем алгоритм сортировки выбором в С++.

// sorting_choices.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include #include #include using namespace std; void choicesSort(int*, int); // прототип функции сортировки выбором int main(int argc, char* argv) { srand(time(NULL)); setlocale(LC_ALL, "rus"); cout << "Введите размер массива: "; int size_array; // длинна массива cin >> size_array; int *sorted_array = new int ; // одномерный динамический массив for (int counter = 0; counter < size_array; counter++) { sorted_array = rand() % 100; // заполняем массив случайными числами cout << setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; choicesSort(sorted_array, size_array); // вызов функции сортировки выбором for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; delete sorted_array; // высвобождаем память system("pause"); return 0; } void choicesSort(int* arrayPtr, int length_array) // сортировка выбором { for (int repeat_counter = 0; repeat_counter < length_array; repeat_counter++) { int temp = arrayPtr; // временная переменная для хранения значения перестановки for (int element_counter = repeat_counter + 1; element_counter < length_array; element_counter++) { if (arrayPtr > arrayPtr) { temp = arrayPtr; arrayPtr = arrayPtr; arrayPtr = temp; } } } }

Алгоритм сортировки выбором основан на алгоритме поиска максимального (минимального) элемента. Фактически алгоритм поиска является важнейшей частью сортировки выбором. Так как основная задача сортировки — упорядочивание элементов массива, необходимо выполнять перестановки. Обмен значений элементов сортируемого массива происходит в строках 48 —50 . Если поменять знак > в строке 46 на знак меньше, то сортироваться массив будет по убыванию. Результат работы программы показан на рисунке 1.

Рисунок 1 — Сортировка выбором

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

Метод поиска минимального элемента

Суть этого метода (имея в виду выбранные ограничения для рассматриваемого нами числового примера) состоит в следующем.

На первом шаге отыскивается и сохраняется в переменной, например, Xmin минимальное число среди всех чисел массива и его индекс, сохраняемый в другой переменной, например, Imin, а затем проводится обмен местами в массиве найденного минимального числа с первым элементом массива: X:=X; X:=Xmin;.

В нашем примере, минимальное число Xmin=15 находится в ячейке Imin=3, и перестановка первого и минимального чисел приведёт к следующему результату

При i=3 получим Xmin=21 и Imin=4, и после перестановки

При i=5 получим Xmin=34 и Imin=5, и после перестановки

Таким образом, внешний цикл должен выполняться n-1 раз, а число выполнений внутреннего цикла будет уменьшаться от n-1 до 1. Чтобы упорядочить массив по убыванию, следует первое найденное минимальное число обменять местами с последним, второе – с предпоследним и так далее.

Метод поиска максимального элемента

Этот метод отличается от предыдущего только тем, что отыскиваются максимальные элементы. При одинаковой организации циклов при реализации этих методов они дадут прямо противоположные результаты: если один приведёт к возрастанию чисел в массиве, то другой – убыванию, и наоборот.

Метод поиска индекса минимального элемента

Этот метод отличается от метод поиска минимального элемента и его индекса тем, что внутренний цикл используется для поиска только индекса минимального элемента, поэтому перестановки чисел в массиве на каждом шаге i, i=1, 2, …,n-1 придется выполнять с привлечением дополнительной переменной, например, R: R:=X[i]; X[i]:=X; X:=R;.

Метод поиска индекса максимального элемента

Этот метод отличается от предыдущего только тем, что отыскиваются индекс максимального элемента. При одинаковой организации циклов при реализации этих методов они дадут прямо противоположные результаты: если один приведёт к возрастанию чисел в массиве, то другой – убыванию, и наоборот.

Урок из серии: «Программирование на языке Паскаль»

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

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

Сортировка массива методом простого выбора

При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.

Алгоритм сортировки массива методом выбора:

1. Для исходного массива выбрать максимальный элемент.
2. Поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте).
3. Повторить п.п. 1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в нем максимальный элемент и поменять его местамис предпоследним (n-1)- м элементом массива, затем с оставшиеся (n-2)-мя элементами и так далее, пока не останется один элемент, уже стоящий на своем месте.

Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.

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

Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.

Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var ).

В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет изменяться от n до 2.

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

Программный код процедуры:

Программный код основной программы:

program primer_1; const n = 10; type myarray = array of integer; var a:myarray; Procedure sorting1(var a:myarray); {Линейная сортировка (сортировка отбором)} ... begin {main} writeln("Введите исходный массив:"); for i:=1 to n do read(a[i]); sorting1(a); writeln("Отсортированный массив:"); for i:=1 to 10 do write(a[i]," "); writeln; end.

Процесс упорядочения элементов в массиве по возрастанию методом отбора:

Номер элемента	1	2	3	4	5
Исходный массив	8	7	5	4	2
Первый просмотр	2	7	5	4	8
Второй просмотр	2	4	5	7	8
Третий просмотр	2	4	5	7	8
Четвертый просмотр	2	4	5	7	8

При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме нахождения максимального элемента достаточно знак «>» поменять на знак «<«.

Сортировка массива методом простого обмена (методом пузырька)

Наиболее известным методом сортировки является сортировка пузырьковым методом. Его популярность объясняется запоминающимся названием и простым алгоритмом.

Метод основан на том, что в процессе исполнения алгоритма более «легкие» элементы массива постепенно «всплывают».

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

Алгоритм сортировки массива по возрастанию методом простого обмена:

1. Начнем просмотр с первой пары элементов (a и a). Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов (a и a), если второй больше третьего, то также меняем их, далее сравниваем третий и четвертый, и если третий больше четвертого, меняем их местами, и т.д. Последними сравниваем (n-1)-ый и n-ый элементы.При первом обходе массива будут просмотрены все пары элементов массива a[i] и a для i от 1 до (n-1). В результате максимальный элемент массива переместится в конец массива.
2. Поскольку самый большой элемент находится на своем месте, рассмотрим часть массива без него, то есть с первого до (n-1) — го элемента.Повторим предыдущие действия для этой части массива, в результате чего второй по величине элемент массива переместится на последнее место рассматриваемой части массива, то есть на (n-1) — е место во всем массиве.
3. Эти действия продолжают до тех пор, пока количество элементов в текущей части массива не уменьшится до двух. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента.

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

Ниже приведен текст процедуры сортировки массива по возрастанию методом пузырька.

Для упорядочения элементов массива по убыванию их значений необходимо при сравнении элементов массива знак «>» заменить на «<«.

Процесс упорядочения элементов в массиве по возрастанию методом обмена:

Номер элемента	1	2	3	4	5
Исходный массив	8	7	5	4	2
Первый просмотр	7	5	4	2	8
Второй просмотр	5	4	2	7	8
Третий просмотр	4	2	5	7	8
Четвертый просмотр	2	4	5	7	8

В чём идея сортировок выбором?

1. В неотсортированном подмассиве ищется локальный максимум (минимум).
2. Найденный максимум (минимум) меняется местами с последним (первым) элементом в подмассиве.
3. Если в массиве остались неотсортированные подмассивы - смотри пункт 1.

Небольшое лирическое отступление. Изначально в своей серии статей я планировал последовательно излагать материал о классах сортировок в порядке строгой очереди. После планировались статьи о прочих вставочных алгоритмах: пасьянсная сортировка, сортировка таблицей Юнга, сортировка выворачиванием и т.д.

Однако, сейчас в тренде нелинейность, поэтому, не написав ещё все публикации про сортировки вставками, сегодня начну параллельную ветку про сортировки выбором. То же самое потом сделаю для других алгоритмических классов: сортировок слиянием, сортировок распределением и т.п. Это в целом позволит писать публикации то по одной теме, то по другой. С таким тематическим чередованием будет веселее.

Сортировка выбором:: Selection sort

Просто и незатейливо - проходим по массиву в поисках максимального элемента. Найденный максимум меняем местами с последним элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает последний элемент, куда мы переставили найденный максимум). К этой неотсортированной части применяем те же действия - находим максимум и ставим его на последнее место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента.

Def selection(data): for i, e in enumerate(data): mn = min(range(i, len(data)), key=data.__getitem__) data[i], data = data, e return data

Сортировка простым выбором представляет из себя грубый двойной перебор. Можно ли её улучшить? Разберём несколько модификаций.

Двухсторонняя сортировка выбором:: Double selection sort

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

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

Отличие сортировок выбором от сортировок вставками

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

Главное отличие: в сортировке вставками мы извлекаем из неотсортированной части массива любой элемент и вставляем его на своё место в отсортированной части. В сортировке выбором мы целенаправленно ищем максимальный элемент (или минимальный), которым дополняем отсортированную часть массива. Во вставках мы ищем куда вставить очередной элемент, а в выборе - мы заранее уже знаем в какое место поставим, но при этом требуется найти элемент, этому месту соответствующий.

Это делает оба класса алгоритмов совершенно отличными друг от друга по своей сути и применяемым методам.

Бинго-сортировка:: Bingo sort

Интересной особенностью сортировки выбором является независимость скорости от характера сортируемых данных.

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

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

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

Здесь фокус в том, что в неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации. Это позволяет при повторяющихся максимумах не искать их заново каждый раз, а ставить на своё место сразу как только этот максимум в очередной раз встретили в массиве.

Алгоритмическая сложность осталась та же. Но если массив состоит из повторяющихся чисел, то бинго-сортировка справится в десятки раз быстрее, чем обычная сортировка выбором.

# Бинго-сортировка def bingo(data): # Первый проход. max = len(data) - 1 nextValue = data for i in range(max - 1, -1, -1): if data[i] > nextValue: nextValue = data[i] while max and data == nextValue: max -= 1 # Последующие проходы. while max: value = nextValue nextValue = data for i in range(max - 1, -1, -1): if data[i] == value: data[i], data = data, data[i] max -= 1 elif data[i] > nextValue: nextValue = data[i] while max and data == nextValue: max -= 1 return data

Цикличная сортировка:: Cycle sort

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

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

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

И здесь алгоритмическая сложность так же остаётся в пределах O(n 2 ). На практике цикличная сортировка работает даже в несколько раз медленнее, чем обычная сортировка выбором, так как приходится больше бегать по массиву и чаще сравнивать. Это цена за минимально возможное количество перезаписей.

# Цикличная сортировка def cycle(data): # Проходим по массиву в поиске циклических круговоротов for cycleStart in range(0, len(data) - 1): value = data # Ищем, куда вставить элемент pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i] < value: pos += 1 # Если элемент уже стоит на месте, то сразу # переходим к следующей итерации цикла if pos == cycleStart: continue # В противном случае, помещаем элемент на своё # место или сразу после всех его дубликатов while value == data: pos += 1 data, value = value, data # Циклический круговорот продолжается до тех пор, # пока на текущей позиции не окажется её элемент while pos != cycleStart: # Ищем, куда переместить элемент pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i] < value: pos += 1 # Помещаем элемент на своё место # или сразу после его дубликатов while value == data: pos += 1 data, value = value, data return data

Блинная сортировка

Алгоритм, который освоили все уровни жизни - от до .

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

Подобные кордибалеты, вообще говоря, приводят к алгоритмической сложности в O(n 3 ). Это дрессированные инфузории кувыркаются одним махом (поэтому в их исполнении сложность O(n 2 )), а при программировании разворот части массива - это дополнительный цикл.

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

# Блинная сортировка def pancake(data): if len(data) > 1: for size in range(len(data), 1, -1): # Позиция максимума в неотсортированной части maxindex = max(range(size), key = data.__getitem__) if maxindex + 1 != size: # Если максимум не слова, то нужно развернуть if maxindex != 0: # Переворачиваем так, # чтобы максимум оказался слева data[:maxindex+1] = reversed(data[:maxindex+1]) # Переворачиваем неотсортированную часть массива, # максимум становится на своё место data[:size] = reversed(data[:size]) return data

Сортировка выбором эффективна настолько, насколько эффективно организован поиск минимального/максимального элемента в неотсортированной части массива. Во всех разобранных сегодня алгоритмах поиск осуществляется в виде двойного перебора. А у двойного перебора, как ни крути, алгоритмическая сложность будет всегда не лучше чем O(n 2 ). Значит ли это, что все сортировки выбором обречены на средне-квадратичную сложность? Вовсе нет, если процесс поиска организовать принципиально по-другому. Например рассмотреть набор данных как кучу и производить поиск именно в куче. Однако тема кучи - это даже не на статью, а на целую сагу, о кучах поговорим обязательно, но в другой раз.

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

Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.

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

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

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

Сортировка выбором (Selection sort)

Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.

Код C++

void SortAlgo::selectionSort(int data, int lenD) { int j = 0; int tmp = 0; for (int i=0; idata[k]){ j = k; } } tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }

Пузырьковая сортировка (Bubble sort)

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

Код C++

void SortAlgo::bubbleSort(int data, int lenD) { int tmp = 0; for (int i = 0;i=(i+1);j--){ if (data[j]

Сортировка вставками (Insertion sort)

При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.

На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.

Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i].

Код C++

void SortAlgo::insertionSort(int data, int lenD) { int key = 0; int i = 0; for (int j = 1;j=0 && data[i]>key){ data = data[i]; i = i-1; data=key; } } }

Сортировка слиянием (Merge sort)

Код C++

void SortAlgo::mergeSort(int data, int lenD) { if (lenD>1){ int middle = lenD/2; int rem = lenD-middle; int * L = new int ; int * R = new int ; for (int i=0;i

Быстрая сортировка (Quick sort)

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

Код C++

void SortAlgo::quickSort(int * data, int const len) { int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1){ int * L = new int ; int * R = new int ; pivot = data; for (i=0;i