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

Как работает сортировка?

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

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

Не секрет, что есть алгоритмы поиска внутри отсортированных массивов и получше. Используя простой алгоритм, мы можем искать определённый элемент в отсортированном массиве, содержащем 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"; }

#include #include // для std::swap. В C++11 используйте заголовок 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; }

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

#include #include // для std::sort int main () const int length = 5 ; int array [ length ] = { 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 [ currentIndex ] < array [ smallestIndex ] )

If (array > array)

if (array [ currentIndex ] > array [ smallestIndex ] )

Также 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; }

#include #include // для std::swap. В C++11 используйте заголовок int main () const int length = 5 ; int array [ length ] = { 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 [ currentIndex ] > array [ largestIndex ] ) // то это новый наибольший элемент в этой итерации largestIndex = currentIndex ; // Меняем местами наше стартовое число с обнаруженным наибольшим элементом std :: swap (array [ startIndex ] , array [ largestIndex ] ) ; // Выводим отсортированный массив на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; 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 };

const int length (9 ) ;

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

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

Ответ №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; }

#include #include // для std::swap. В C++11 используйте заголовок int main () const int length (9 ) ; int array [ length ] = { 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 [ currentIndex ] > array [ currentIndex + 1 ] ) std :: swap (array [ currentIndex ] , array [ currentIndex + 1 ] ) ; } } // Выводим отсортированный массив на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; }

Задание №4

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

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

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

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

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

На первом шаге отыскивается и сохраняется в переменной, например, 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;.

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

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

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

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

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

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

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

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

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

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 ). Значит ли это, что все сортировки выбором обречены на средне-квадратичную сложность? Вовсе нет, если процесс поиска организовать принципиально по-другому. Например рассмотреть набор данных как кучу и производить поиск именно в куче. Однако тема кучи - это даже не на статью, а на целую сагу, о кучах поговорим обязательно, но в другой раз.

Для сортировки (упорядочения) по возрастанию или убыванию значений в массиве разработано множество методов [Вирт, Кнут. т 3].Рассмотрим три из них, считая, для определённости, что первые n, n=6, элементов массива Х

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

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

В нашем примере:

При i=2 число 15 из ячейки Х 3 последовательно обменяется местами с числом 34 из ячейки Х 2 , а затем с числом 21 из ячейки Х 1 ,

При i=4 число 25 из ячейки Х 5 обменяется местами с числом 34 из ячейки Х 3 ,

Ниже представлен фрагмент программы упорядочения по возрастанию первых n элементов массива X методом прямоговключения (включения с сохранением упорядоченности) .

for i:=1 to n-1 do

2. while (X0) do

3. R:=X[j];

   X[j]:=X;

   X:=R;

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

Метод прямого обмена (метод пузырька).

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

На первом шаге последовательно, для j = n, n-1, …,2, сравниваются значения соседних ячеек массива, и при выполнении условия Х j <Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

В нашем примере после выполнения первого шага данные в массиве расположатся так:

На каждом следующем шаге число проверяемых пар ячеек будет уменьшаться на 1. В общем случае, на любом шаге i, i=1, 2, 3, …, n-1, процесс будет выполняться для j от n до i+1, в частности, при i= n-1 – только один раз для n-ой и (n-1)-вой ячеек.

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

Происхождение термина “метод пузырька” объясняется так: если представить вертикальное расположение ячеек массива с ростом индекса сверху вниз, то самое маленькое число из рассматриваемых будет подниматься вверх подобно пузырьку в воде.

В нашем примере

При i=3 перестановки приведут к следующему состоянию массива

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

Модифицированный метод прямого обмена (модифицированный метод пузырька).

Как видно из приведенного выше числового примера массив оказался упорядоченным уже после четвёртого шага, то есть возможновыполнение внешнего цикла не n-1 раз, а меньше, когда станет известно, что массив уже упорядочен. Такая проверка основывается на следующем: если при выполнении внутреннего цикла не было ни одной перестановки, значит массив уже упорядочен и можно выйти из внешнего цикла. В качестве признака, выполнялась ли перестановка, используют переменную булевского типа: до входа во внутренний цикл ей дают одно значение, например, False, а при выполнении перестановки – другое, например, True.

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