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

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

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

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

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

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

Общий алгоритм сортировки выбором приведен ниже:

Сортировка выбором (A, N)

Шаг 1: Повторить шаги 2 и 3 для значений от K = 1 до N-1
Шаг 2: Вызов наименьшей процедуры (A, K, N, POS)
Шаг 3: Поменять местами A[K] на A [POS]
[Конец цикла]
Шаг 4: вывод данных

Обычный наименьший (A, K, N, POS)

Шаг 1: [инициализация] установить наименьший элемент = A[K]
Шаг 2: [инициализация] установить POS = K
Шаг 3: для J = K+1 до N-1, повторить,
если наименьший элемент > A [J]
установить наименьший элемент = A [J]
установить POS = J
[если конец]
[конец цикла]

Читать также:  Конструкции принятия решений в C++

Шаг 4: возврат POS

Псевдокод для сортировки выбором

Пример алгоритма сортировки выбором, показан ниже:

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

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

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

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

Приведенные выше схемы можно обобщить в табличной форме:

Несортированный список Наименьший элемент Отсортированный список
{18,10,7,20,2} 2 {}
{18,10,7,20} 7 {2}
{18,10,20} 10 {2,7}
{18,20} 18 {2,7,10)
{20} 20 {2,7,10,18}
{} {2,7,10,18,20}

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

Ниже приведена реализация алгоритма сортировки выбором на C++:

Вывод данных:

Введите список элементов для сортировки:
11 5 2 20 42 53 23 34 101 22
Отсортированный список элементов:
2 5 11 20 22 23 34 42 53 101
Количество проходов, необходимых для сортировки массива: 10

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

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

Читать также:  Структура данных очереди в C++

Далее мы реализуем технику сортировки выбором на языке Java:

Вывод данных:

Список ввода для сортировки…
11 5 2 20 42 53 23 34 101 22
печать отсортированных элементов…
2 5 11 20 22 23 34 42 53 101

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

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

Анализ сложности сортировки выбором

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

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

Читать также:  Безопасность реализации на языке Java

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

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

Итог

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

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

В этой статье мы подробно обсудили сортировку выбором, включая реализацию сортировки выбором с использованием языков C++ и Java. Логика сортировки выбором состоит в многократном поиске наименьшего элемента в списке и размещении его в нужном месте.

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

С Уважением, МониторБанк

Добавить комментарий