Сортировка методом выбора анализ

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

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

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

Метод Swap

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

Пузырьковая сортировка

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n)	O(n 2 )	O(n 2 )
Память	O(1)	O(1)	O(1)

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

Например, у нас есть массив целых чисел:

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

Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:

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

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

5 июля в 13:00, Онлайн, Беcплатно

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

Сортировка вставками

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n)	O(n 2 )	O(n 2 )
Память	O(1)	O(1)	O(1)

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.

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

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.

Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным.

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

На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.

Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

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

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

Сортировка выбором

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n)	O(n 2 )	O(n 2 )
Память	O(1)	O(1)	O(1)

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

Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.

При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.

Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение — 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход — на этот раз по индексам от 1 до n — 1.

На втором проходе мы определяем, что наименьшее значение — 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию.

Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.

После еще двух проходов алгоритм завершает свою работу:

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

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n·log n)	O(n·log n)	O(n·log n)
Память	O(n)	O(n)	O(n)

Разделяй и властвуй

До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer).

Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге — один из примеров такого алгоритма.

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

Насколько эффективны эти алгоритмы?

Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

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

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

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

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

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

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

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

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

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

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

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

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n·log n)	O(n·log n)	O(n 2 )
Память	O(1)	O(1)	O(1)

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

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

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

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

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

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

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

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

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

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

Заключение

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

Источник



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

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

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

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

Зависимость выбора алгоритмов от структуры данных – настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка (последовательных) файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ; для этой памяти характерен быстрый произвольный доступ, а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающихся устройствах с механическим передвижением (дисках и лентах). Это существенное различие можно наглядно показать на примере сортировки пронумерованных карточек.

Рис.1.1. Сортировка массива

Представление карточек в виде массива соответствует тому, что все они располагаются перед сортирующим так, что каждая карточка видна и доступна (см. рис. 1). Представление карточек в виде файла предполагает, что видна только верхняя карточка из каждой стопки (см. рис. 2). Очевидно, что такое ограничение приведет к существенному изменению методов сортировки, но оно неизбежно, если карточек так много, что их число на столе не уменьшается.

Рис.1.2. Сортировка файла

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

Сортировка означает перестановку этих элементов в таком порядке:

что при заданной функции упорядочения f справедливо решение

Обычно функция упорядочения не вычисляется по какому-то специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называется ключом элемента. Следовательно, для представления элемента ai особенно хорошо подходит структура записи. Поэтому мы определяем тип item (элемент), который будет использоваться в последующих алгоритмах сортировки следующим образом:

type item = record key: integer;

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

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает правильна, если элементы упорядочены (рассортированы) по каким-то вторичным ключам, т. е. по свойствам, не отраженным в первичном ключе.

Сортировка массивов.

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива a в массив b, не представляет для нас интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии сих эффективностью, т. е. экономией времени или быстродействием. Удобная мера эффективности получается при подсчете числа С – необходимых сравнений ключей и М – пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n log n сравнений, мы обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка n 2 сравнений ключей. Рассмотрим простые методы по следующим трем причинам:

1. Простые методы особенно хорошо подходят для разъяснения свойств большинства принципов сортировки.

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

3. Хотя сложные методы требуют меньшего числа операций, эти операции более сложны; поэтому при достаточно малых n простые методы работают быстрее, но их не следует использовать при больших n.

Методы, сортирующие элементы in situ, можно разбить на три основных класса в зависимости от лежащего в их основе приема:

Рассмотрим и сравним эти три принципа. Программы работают с переменной-массивом а, который нужно рассортировать in situ. В этих программах используются типы данных item (2) и index , определенные так:

type index = 0 . . n;

var a: array [1 . . n] of item (3)

Сортировка простыми включениями

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

Таблица 1.1. Пример сортировки простыми включениями

Начальные ключи 44 55 12 42 94 18 06 67

i = 2 44 55 12 42 94 18 06 67

i = 3 12 44 55 42 94 18 06 67

i = 4 12 42 44 55 94 18 06 67

i = 5 12 42 44 55 94 18 06 67

i = 6 12 18 42 44 55 94 06 67

i = 7 06 12 18 42 44 55 94 67

i = 8 06 12 18 42 44 55 67 94

Процесс сортировки включениями показан на примере восьми случайно взятых чисел (см. табл. 1). Алгоритм сортировки простыми включениями выглядит следующим образом:

for i := 1 to n do

begin x := a[i];

«вставить x на подходящее место в »

При поиске подходящего места удобно чередовать сравнения и пересылки, т. е. как бы «просеивать» x, сравнивая с очередным элементом и либо вставляя x, либо передается вправо и продвигаясь налево. Заметим, что «процесс просеивания » закончится при двух различных условиях:

1. Найден элемент с ключом меньшим, чем ключ у x.

2. Достигнут левый конец.

Такой повтор процесса с двумя условиями позволяет нам воспользоваться хорошо известным приемом фиктивного элемента («барьера»). Его можно легко приметить в этом случае. Установив барьер = x. (Заметим, что для этого нужно расширить диапазон индексов в описании a до 0, …, n.) Окончательно алгоритм представлен в виде программы 1.

procedure straightinsertion;

var i, j: index; x: item;

for i:=2 to n do

begin x := a[i]; a[0] := x; j := i-1;

while x.key < a[j].key do

begin a[j+1] := a[j]; j := j—1;

a[j+1]:= x

Программа 1.1. Сортировка простыми включениями

Анализ сортировки простыми включениями. Общее число сравнений С и пересылок М есть

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

Сортировка бинарными включениями

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

procedure binaryinsertion;

var i, j, l, r, m: index; x: item;

for i := 2 to n do

begin x := a[i]; l := 1; r := i;

while l < r do

begin m := (l + r) div 2;

if x.key >= a[m].key then l := m + 1 else r := m

for j := i downto r+1 do a[j] := a[j-1];

a[r] := x;

Программа 1.2. Сортировка бинарными включениями

Анализ сортировки бинарными включениями.

Количество сравнений не зависит от исходного порядка элементов. Но из-за округления при делении интервала поиска пополам действительное число сравнений для i элементов может быть на 1 больше ожидаемого. Природа этого «перекоса» такова, что в результате места включения в нижней части находятся в среднем несколько быстрее, чем в верхней части. Это дает преимущество в тех случаях, когда элементы изначально далеки от правильного порядка. На самом же деле минимальное число сравнений требуется, если элементы вначале расположены в обратном порядке, а максимальное – если они уже упорядочены. Следовательно, это случай неестественного поведения алгоритма сортировки:

К сожалению, улучшение, которое мы получаем, используя метод бинарного поиска, касается только числа сравнений, а не числа необходимых пересылок. В действительности поскольку пересылка элементов, т. е. ключей и сопутствующей информации, обычно требует значительно больше времени, чем сравнение двух ключей, то это улучшение ни в коей мере не является решающим: важный показатель М по-прежнему остается порядка n 2 . И в самом деле, пересортировка уже рассортированного массива занимает больше времени, чем при сортировке простыми включениями с последовательным поиском! Этот пример показывает, что «очевидное улучшение» часто оказывается намного менее существенным, чем кажется в начале, и в некоторых случаях (которые действительно встречаются) может на самом деле оказаться ухудшением. В конечном счете сортировка включениями оказывается не очень подходящим методом для цифровых вычислительных машин: включение элемента с последующим сдвигом всего ряда элементов на одну позицию неэкономна. Лучших результатов можно ожидать от метода, при котором пересылки элементов выполняются только для отдельных элементов и на большие расстояния. Эта мысль приводит к сортировке выбором.

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

Этот метод основан на следующем правиле:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом a₁.

Эти операции затем повторяются с оставшимися n — 1 элементами, затем с n — 2 элементами, пока не останется только один элемент – наибольший. Этот метод продемонстрирован на тех же восьми ключах в табл. 2.

Таблица 1.2. Пример сортировки простым выбором

Начальные ключи 44 55 12 42 94 18 06 67

06 55 12 42 94 18 44 67

06 12 55 42 94 18 44 67

06 12 18 42 94 55 44 67

06 12 18 42 94 55 44 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 67 94

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

for i := 1 to n-1 do

begin «присвоить k индекс наименьшего элемента из a[i]. . . a[n] »;

«поменять местами a_i и a_k»

End

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

procedurestraightselection;

vari, j, k: index; x: item;

begin for i :=1 to n — 1 do

begin k := i; x := a[i];

for j := i+ 1 to n do

if a[j].key < x.key then

begin k := j; x := a[j]

end;

a[k] := a[i]; a[i] := x;

End

End

Программа 1.3. Сортировка простым выбором

Анализ сортировки простым выбором. Очевидно, что число С сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что сортировка простым выбором ведет себя менее естественно, чем сортировка простыми включениями. Мы получаем

Минимальное число пересылок равно

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

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

где – эйлерова константа.

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

Источник

Сортировка методом выбора анализ

• Вы здесь:  
• Главная
• Статьи
• Программирование и сеть
• Алгоритмы и структуры данных
• Сортировка и поиск
• Сортировка Выбором (Selection-sort)

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

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

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;
2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;
3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key?1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;
4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

О(n) всего, O(1) дополнительно

Реализация алгоритма на различных языках программирования:

Паскаль

Компонентный Паскаль

Python

TurboBasic 1.1

CLS RANDOMIZE TIMER DEFINT X, Y, N, I, J, D N = 10 ‘ 32 766 — 62.7 SEC DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] ‘FRE(-1)=21440-21456 PRINT » ZAPOLNENIE MASSIVA ELEMENTAMI» FOR X = 1 TO N Y[X] = X PRINT Y[X]; NEXT X:PRINT PRINT » PEREMESHIVANIJE ELEMENTOV MASSIVA» PRINT » SLUCHAINYE CHISLA» FOR X = 1 TO N YD=Y[X] XS=INT(RND*N)+1 PRINT XS; Y[X]=Y[XS] Y[XS]=YD NEXT X:PRINT PRINT » PEREMESHANNYJ MASSIV» FOR X=1 TO N PRINT Y[X]; NEXT X:PRINT ‘ALGORITM «SORTIROVKA VYBOROM» O(N^2) L=1 R=N MTIMER FOR J=1 TO R-1 STEP 1 MIN=J FOR I=J+1 TO R STEP 1 IF Y[I] < Y[MIN] THEN MIN=I NEXT I IF MIN<>J THEN SWAP Y[J],Y[MIN] LOCATE 7,1 REM FOR I=1 TO N:PRINT Y[I];:NEXT I:PRINT REM ANIMATION BLOCK DELAY 1 REM NEXT J T1=MTIMER PRINT » OTSORTIROVANNYJ MASSIV» FOR X=1 TO N ‘PRINT «Y[X]=»;Y[X] PRINT Y[X]; NEXT X:PRINT PRINT «ELAPSED TIME font-family: comic sans ms,sans-serif; font-size: 14pt;»>Сортировка выбором проста в реализации, и в некоторых ситуациях стоит предпочесть ее наиболее сложным и совершенным методам. Но в большинстве случаев данный алгоритм уступает в эффективности последним, так как в худшем, лучшем и среднем случае ей потребуется О(n2) времени.

При написании статьи были использованы открытые источники сети интернет :

Источник

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

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

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

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

СОДЕРЖАНИЕ

Пример

Вот пример этого алгоритма сортировки пяти элементов:

Отсортированный подсписок	Несортированный подсписок	Наименьший элемент в несортированном списке
()	(11, 25, 12, 22, 64)	11
(11)	(25, 12, 22, 64)	12
(11, 12)	(25, 22, 64)	22
(11, 12, 22)	(25, 64)	25
(11, 12, 22, 25)	(64)	64
(11, 12, 22, 25, 64)	()

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

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

Реализации

Ниже приводится реализация в C .

Сложность

Сортировку выбора нетрудно анализировать по сравнению с другими алгоритмами сортировки, поскольку ни один из циклов не зависит от данных в массиве. Для выбора минимума требуется сканировать элементы (проводить сравнения), а затем переставлять их в первую позицию. Чтобы найти следующий самый низкий элемент, необходимо просканировать оставшиеся элементы и так далее. Таким образом, общее количество сравнений равно п <\ displaystyle n>п — 1 <\ displaystyle n-1>п — 1

( п — 1 ) + ( п — 2 ) + . . . + 1 знак равно ∑ я знак равно 1 п — 1 я <\ Displaystyle (п-1) + (п-2) + . + 1 = \ сумма _ <я = 1>^ <п-1>я>

что является сложным с точки зрения количества сравнений. Для каждого из этих сканирований требуется одна замена элементов (последний элемент уже на месте). О ( п 2 ) <\ Displaystyle О (п ^ <2>)> п — 1

Сравнение с другими алгоритмами сортировки

Среди алгоритмов квадратичной сортировки (алгоритмы сортировки с простым средним случаем ( n 2 ) ) сортировка по выбору почти всегда превосходит пузырьковую сортировку и сортировку гномов . Сортировка вставкой очень похожа на то, что после k- й итерации первые элементы в массиве находятся в отсортированном порядке. Преимущество сортировки вставкой состоит в том, что она сканирует только столько элементов, сколько нужно для размещения элемента st, в то время как сортировка выбора должна сканировать все оставшиеся элементы, чтобы найти элемент st. k <\ displaystyle k>k + 1 <\ displaystyle k + 1>k + 1

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

Хотя сортировка по выбору предпочтительнее сортировки вставкой с точки зрения количества операций записи ( свопы по сравнению с перестановками, при этом каждый своп составляет две записи), это примерно вдвое больше теоретического минимума, достигаемого с помощью циклической сортировки , которая выполняет не более n операций записи. Это может быть важно, если запись значительно дороже чтения, например, с EEPROM или флэш-памятью , где каждая запись сокращает срок службы памяти. п — 1 <\ displaystyle n-1>п ( п — 1 ) / 2 <\ Displaystyle п (п-1) / 2>

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

Наконец, сортировка по выбору значительно уступает по производительности на больших массивах алгоритмами «разделяй и властвуй», такими как сортировка слиянием . Однако сортировка вставкой или сортировка по выбору обычно быстрее для небольших массивов (т.е. менее 10–20 элементов). На практике полезной оптимизацией рекурсивных алгоритмов является переключение на сортировку вставкой или сортировку по выбору для «достаточно маленьких» подсписок. Θ ( п бревно ⁡ п )

Варианты

Heapsort значительно улучшает базовый алгоритм за счет использования неявной структуры данных кучи для ускорения поиска и удаления самых низких данных. При правильной реализации куча позволит найти следующий самый низкий элемент по времени вместо внутреннего цикла при нормальной сортировке выбора, уменьшив общее время работы до . Θ ( бревно ⁡ п ) <\ Displaystyle \ Theta (\ журнал п)>Θ ( п ) <\ Displaystyle \ Theta (п)>Θ ( п бревно ⁡ п )

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

Сортировка выбора может быть реализована как стабильная сортировка, если вместо замены на шаге 2 минимальное значение вставлено в первую позицию, а промежуточные значения сдвинуты вверх. Однако для этой модификации либо требуется структура данных, поддерживающая эффективные вставки или удаления, например связанный список, либо она приводит к выполнению операций записи. Θ ( п 2 ) <\ Displaystyle \ Theta (п ^ <2>)>

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

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

Источник