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

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

исходный массив: 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 — Сортировка выбором

Алгоритмы и структуры данных для начинающих: сортировка

Никита Прияцелюк

В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого - сортировки пузырьком - и закончим «быстрой сортировкой» (quicksort) .

Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае.

Также смотрите другие материалы этой серии: , и .

Метод Swap

Для упрощения кода и улучшения читаемости мы введем метод 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% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

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

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

Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

1. Операцию для рекурсивного разделения массива на группы (метод Sort).
2. Слияние в правильном порядке (метод Merge).

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

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--; } }

Быстрая сортировка

Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:

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

Давайте посмотрим на работу алгоритма на следующем массиве:

Сначала мы случайным образом выбираем ключевой элемент:

Int pivotIndex = _pivotRng.Next(left, right);

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

Перемещение значений осуществляется методом partition .

На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.

Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное - помнить, что нам важно именно ключевое значение, а не его индекс.

Снова применяем быструю сортировку:

И еще раз:

У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу.

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#.

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

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

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

На первом шаге отыскивается и сохраняется в переменной, например, 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 000 000 элементов, используя всего лишь 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно затратное, и оно точно не выполняется ради одного поискового запроса.

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

Сортировка обычно выполняется путём повторного сравнения пар элементов массива и замены значений, если они отвечают определённым критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).

Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в algorithm. В C++11 std::swap() был перенесён в заголовочный файл utility:

#include #include int main() { int a = 3; int b = 5; std::cout << "Before swap: a = " << a << ", b = " << b << "\n"; std::swap(a, b); // меняем местами значения переменных a и b std::cout << "After swap: a = " << a << ", b = " << b << "\n"; }

Результат выполнения программы выше:

Before swap: a = 3, b = 5
After swap: a = 5, b = 3

После выполнения операции замены значения переменных a и b поменялись местами.

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

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

Для сортировки массива методом выбора от наименьшего до наибольшего элемента выполняются следующие шаги:

Начиная с элемента под индексом 0, ищем в массиве наименьшее значение.

Найденное значение меняем местами с нулевым элементом.

Повторяем шаги №1 и №2 уже для следующего индекса в массиве.

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

Вот пример работы этого алгоритма в массиве с 5-ью элементами:

{ 30, 50, 20, 10, 40 }

Сначала ищем наименьший элемент, начиная с индекса 0:

{ 30, 50, 20, 10 , 40 }

Затем меняем местами наименьший элемент с элементом под индексом 0:

{ 10 , 50, 20, 30 , 40 }

Теперь, когда первый элемент массива отсортирован, мы его игнорируем. Ищем следующий наименьший элемент, но уже начиная с индекса 1:

{ 10 , 50, 20 , 30, 40 }

И меняем его местами с элементом под индексом 1:

{ 10 , 20 , 50 , 30, 40 }

Теперь мы можем игнорировать первые два элемента. Ищем следующий наименьший элемент, начиная с индекса 2:

{ 10 , 20 , 50, 30 , 40 }

И меняем его местами с элементом под индексом 2:

{ 10 , 20 , 30 , 50 , 40 }

Ищем следующий наименьший элемент, начиная с индекса 3:

{ 10 , 20 , 30 , 50, 40 }

И меняем его местами с элементом под индексом 3:

{ 10 , 20 , 30 , 40 , 50 }

Ищем следующий наименьший элемент, начиная с индекса 4:

{ 10 , 20 , 30 , 40 , 50 }

И меняем его местами с элементом под индексом 4 (выполняется самозамена, т.е. ничего не делаем):

{ 10 , 20 , 30 , 40 50 }

{ 10, 20, 30, 40, 50 }

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

Сортировка массивов методом выбора в C++

Вот как этот алгоритм реализован в C++:

#include #include // для std::swap. В C++11 используйте заголовок int main() { const int length = 5; int array = { 30, 50, 20, 10, 40 }; // Перебираем каждый элемент массива // (кроме последнего, он уже будет отсортирован к тому времени, когда мы до него доберёмся) for (int startIndex = 0; startIndex < length - 1; ++startIndex) { // В переменной smallestIndex хранится индекс наименьшего значения, которое мы нашли в этой итерации // Начинаем с того, что наименьший элемент в этой итерации - это первый элемент (индекс 0) int smallestIndex = startIndex; // Затем ищем элемент поменьше в остальной части массива for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Если мы нашли элемент, который меньше нашего наименьшего элемента, if (array < array) // то запоминаем его smallestIndex = currentIndex; } // smallestIndex теперь наименьший элемент // Меняем местами наше начальное наименьшее число с тем, которое мы обнаружили std::swap(array, array); } // Теперь, когда весь массив отсортирован - выводим его на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

Наиболее запутанной частью этого алгоритма является внутри другого цикла (так называемый вложенный цикл). Внешний цикл (startIndex) перебирает элементы один за другим (поочерёдно). В каждой итерации внешнего цикла внутренний цикл (currentIndex) используется для поиска наименьшего элемента среди элементов, которые остались в массиве (начиная со startIndex + 1). smallestIndex отслеживает индекс наименьшего элемента, найденного внутренним циклом. Затем smallestIndex меняется значением со startIndex . И, наконец, внешний цикл (startIndex) передаёт этот элемент, и процесс повторяется.

Подсказка: Если у вас возникли проблемы с пониманием того, как работает программа выше, то попробуйте записать её выполнение на листке бумаги. Запишите начальные (неотсортированные) элементы массива горизонтально в строке в верхней части листа. Нарисуйте стрелки, указывающие, какие элементы являются startIndex , currentIndex и smallestIndex на данный момент. Прокрутите выполнение программы вручную и перерисуйте стрелки по мере изменения индексов. После каждой итерации внешнего цикла нарисуйте новую строку, показывающую текущее состояние массива (расположение его элементов).

Сортировка текста выполняется с помощью того же алгоритма. Просто измените тип массива из -а в и инициализируйте его с помощью соответствующих значений.

std::sort()

Поскольку операция сортировки массивов очень распространена, то стандартная библиотека C++ предоставляет встроенную функцию сортировки — std::sort() . Она находится в заголовочном файле algorithm и вызывается следующим образом:

#include #include // для std::sort int main() { const int length = 5; int array = { 30, 50, 20, 10, 40 }; std::sort(array, array+length); for (int i=0; i < length; ++i) std::cout << array[i] << " "; return 0; }

Тест

Задание №1

Напишите на листке бумаги выполнение сортировки следующего массива методом выбора (так как мы это делали выше):

{30, 60, 20, 50, 40, 10}

Ответ №1

30 60 20 50 40 10
10 60 20 50 40 30
10 20 60 50 40 30
10 20 30 50 40 60
10 20 30 40 50 60
10 20 30 40 50 60 (самозамена)
10 20 30 40 50 60 (самозамена)

Задание №2

Перепишите код программы из подзаголовка «Сортировка массивов методом выбора в C++» так, чтобы сортировка выполнялась в порядке убывания (от наибольшего числа к наименьшему). Хотя это может показаться сложным на первый взгляд, но, на самом деле, это очень просто.

Ответ №2

Просто измените:

If (array < array)

If (array > array)

Также smallestIndex следует переименовать в largestIndex:

#include #include // для std::swap. В C++11 используйте заголовок int main() { const int length= 5; int array = { 30, 50, 20, 10, 40 }; // Перебираем каждый элемент массива, кроме последнего for (int startIndex = 0; startIndex < length - 1; ++startIndex) { // largestIndex - это индекс наибольшего элемента, который мы обнаружили до сих пор int largestIndex = startIndex; // Перебираем каждый элемент массива начиная со startIndex + 1 for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Если текущий элемент больше нашего наибольшего элемента, if (array > array) // то это новый наибольший элемент в этой итерации largestIndex = currentIndex; } // Меняем местами наше стартовое число с обнаруженным наибольшим элементом std::swap(array, array); } for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

Задание №3

Это задание уже немного сложнее.

Ещё одним простым методом сортировки элементов является «сортировка пузырьком» (или ещё «пузырьковая сортировка» ). Суть заключается в сравнении пары значений, которые находятся рядом, и, если удовлетворены заданные критерии, значения из этой пары меняются местами. И таким образом элементы «скачут пузырьком» до конца массива. Хотя есть несколько способов оптимизировать сортировку пузырьком, в этом задании мы будем придерживаться неоптимизированной версии, так как она проще.

При неоптимизированной версии сортировки пузырьком выполняются следующие шаги для сортировки массива от наименьшего до наибольшего значения :

Сравнивается элемент массива под индексом 0 с элементом массива под индексом 1. Если элемент под индексом 0 больше элемента под индексом 1, то значения меняются местами.

Затем мы перемещаемся к следующей пары значений: элемент под индексом 1 и элемент под индексом 2 и так до тех пор, пока не достигнем конца массива.

Повторяем шаг №1 и шаг №2 до тех пор, пока весь массив не будет отсортирован.

Напишите программу, которая отсортирует следующий массив методом пузырька в соответствии с правилами выше:

const int length(9); int array = { 7, 5, 6, 4, 9, 8, 2, 1, 3 };

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

Подсказка: Если мы можем отсортировать только один элемент за одну итерацию, то это означает, что нам нужно будет повторить выполнение цикла столько раз, сколько есть чисел в нашем массиве (его длина), дабы гарантировать выполнение сортировки всего массива.

Ответ №3

#include #include // для std::swap. В C++11 используйте заголовок int main() { const int length(9); int array = { 7, 5, 6, 4, 9, 8, 2, 1, 3 }; for (int iteration = 0; iteration < length-1; ++iteration) { // Перебираем каждый элемент массива до последнего элемента (не включительно) // Последний элемент не имеет пары для сравнения for (int currentIndex = 0; currentIndex < length - 1; ++currentIndex) { // Если текущий элемент больше элемента после него, то меняем их местами if (array > array) std::swap(array, array); } } // Выводим отсортированный массив на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

Задание №4

Реализуйте следующие два решения оптимизации алгоритма сортировки пузырьком, который вы написали в предыдущем задании:

Обратите внимание, с каждым выполнением сортировки пузырьком наибольшее значения в массиве «пузырится» до конца. После первой итерации последний элемент массива уже отсортирован. После второй итерации отсортирован предпоследний элемент массива и т.д. С каждой новой итерацией нам не нужно перепроверять элементы, которые уже были отсортированы. Измените свой цикл так, чтобы не перепроверять элементы, которые уже были отсортированы.

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

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

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

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

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

Сортировка выбором (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