Сортировка выбора: алгоритм, объясненный на примере кода Python

Содержание:

Anonim

Что такое сортировка по выбору?

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

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

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

В этом руководстве по алгоритму вы узнаете:

  • Что такое сортировка по выбору?
  • Как работает сортировка по выбору?
  • Определение проблемы
  • Решение (алгоритм)
  • Визуальное представление
  • Программа сортировки выбора с использованием Python 3
  • Код Пояснение
  • Сложность выбора сортировки по времени
  • Когда использовать сортировку по выбору?
  • Преимущества селекционной сортировки
  • Недостатки сортировки по выбору

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

Первый элемент в несортированном разделе сравнивается со всеми значениями справа, чтобы проверить, является ли это минимальным значением. Если это не минимальное значение, то его позиция меняется на минимальное значение.

Пример:

  • Например, если индекс минимального значения равен 3, то значение элемента с индексом 3 помещается в индекс 0, а значение, которое было в индексе 0, помещается в индекс 3. Если первым элементом в несортированном разделе является минимальное значение, затем он возвращает свои позиции.
  • Элемент, который был определен как минимальное значение, затем перемещается в раздел с левой стороны, который представляет собой отсортированный список.
  • Разделенная сторона теперь имеет один элемент, а неразделенная сторона имеет (n - 1) элементов, где n - общее количество элементов в списке. Этот процесс повторяется снова и снова, пока все элементы не будут сравнены и отсортированы на основе их значений.

Определение проблемы

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

[21,6,9,33,3]

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

[3,6,9,21,33]

Решение (алгоритм)

Шаг 1) Получите значение n, которое является общим размером массива

Шаг 2) Разделите список на отсортированные и несортированные разделы. Сортированный раздел изначально пуст, а несортированный раздел содержит весь список.

Шаг 3) Выберите минимальное значение из неразмеченного раздела и поместите его в отсортированный раздел.

Шаг 4) Повторите процесс (n - 1) раз, пока все элементы в списке не будут отсортированы.

Визуальное представление

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

На следующем изображении показан несортированный список

Шаг 1)

Первое значение 21 сравнивается с остальными значениями, чтобы проверить, является ли оно минимальным значением.

3 - минимальное значение, поэтому позиции 21 и 3 меняются местами. Значения с зеленым фоном представляют отсортированный раздел списка.

Шаг 2)

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

Значение 6 - это минимальное значение, поэтому оно сохраняет свою позицию.

Шаг 3)

Первый элемент несортированного списка со значением 9 сравнивается с остальными значениями, чтобы проверить, является ли это минимальным значением.

Значение 9 - это минимальное значение, поэтому оно сохраняет свою позицию в отсортированном разделе.

Шаг 4)

Значение 33 сравнивается с остальными значениями.

Значение 21 меньше 33, поэтому позиции меняются местами для создания указанного выше нового списка.

Шаг 5)

В неразмеченном списке осталось только одно значение. Следовательно, он уже отсортирован.

Окончательный список похож на тот, что показан на изображении выше.

Программа сортировки выбора с использованием Python 3

В следующем коде показана реализация сортировки выбора с использованием Python 3.

def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))

Выполнение приведенного выше кода дает следующие результаты

[3, 6, 9, 21, 33]

Код Пояснение

Пояснение к коду выглядит следующим образом

Вот объяснение кода:

  1. Определяет функцию с именем selectionSort
  2. Получает общее количество элементов в списке. Нам нужно это, чтобы определить количество проходов, которые необходимо сделать при сравнении значений.
  3. Внешняя петля. Использует цикл для перебора значений списка. Количество итераций (n - 1). Значение n равно 5, поэтому (5 - 1) дает нам 4. Это означает, что внешние итерации будут выполнены 4 раза. На каждой итерации значение переменной i присваивается переменной minValueIndex
  4. Внутренняя петля. Использует цикл для сравнения крайнего левого значения с другими значениями справа. Однако значение j не начинается с индекса 0. Оно начинается с (i + 1). Это исключает значения, которые уже были отсортированы, поэтому мы сосредоточимся на элементах, которые еще не были отсортированы.
  5. Находит минимальное значение в несортированном списке и помещает его в нужное место
  6. Обновляет значение minValueIndex, когда условие подкачки истинно
  7. Сравнивает значения индексов minValueIndex и i, чтобы убедиться, что они не равны.
  8. Крайнее левое значение хранится во временной переменной
  9. Нижнее значение с правой стороны занимает позицию первой позиции.
  10. Значение, которое было сохранено во временном значении, сохраняется в позиции, которая ранее удерживалась минимальным значением.
  11. Возвращает отсортированный список как результат функции
  12. Создает список el со случайными числами
  13. Распечатайте отсортированный список после вызова функции selection Sort, передав el в качестве параметра.

Сложность выбора сортировки по времени

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

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

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

Следовательно, количество выполнений равно (n * n), что также может быть выражено как O (n 2 ).

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

  • В худшем случае - это список в порядке убывания. Алгоритм выполняет максимальное количество выполнений, которое выражается как [Big-O] O (n 2 ).
  • В лучшем случае - это происходит, когда предоставленный список уже отсортирован. Алгоритм выполняет минимальное количество выполнений, которое выражается как [Big-Omega] Ω (n 2 ).
  • Средний случай - это происходит, когда список находится в случайном порядке. Средняя сложность выражается как [Big-theta] ⊝ (n 2 )

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

Когда использовать сортировку по выбору?

Сортировку выбора лучше всего использовать, когда вы хотите:

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

Преимущества селекционной сортировки

Ниже приведены преимущества сортировки по выбору.

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

Недостатки сортировки по выбору

Ниже перечислены недостатки сортировки по выбору.

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

Резюме:

  • Сортировка по выбору - это алгоритм сравнения на месте, который используется для сортировки случайного списка в упорядоченный список. Он имеет временную сложность O (n 2 )
  • Список разделен на два раздела: отсортированный и несортированный. Минимальное значение выбирается из несортированного раздела и помещается в отсортированный раздел.
  • Это повторяется до тех пор, пока все элементы не будут отсортированы.
  • Реализация псевдокода в Python 3 включает использование двух циклов for и операторов if для проверки необходимости подкачки
  • Сложность по времени измеряет количество шагов, необходимых для сортировки списка.
  • Наихудшая временная сложность возникает, когда список находится в порядке убывания. Его временная сложность [Big-O] O (n 2 )
  • Оптимальная временная сложность возникает, когда список уже находится в порядке возрастания. Его временная сложность [Big-Omega] Ω (n 2 )
  • Средняя временная сложность возникает, когда список находится в случайном порядке. Его временная сложность [Big-theta] ⊝ (n 2 )
  • Сортировку по выбору лучше всего использовать, когда у вас есть небольшой список элементов для сортировки, стоимость замены значений не имеет значения, а проверка всех значений является обязательной.
  • Сортировка выбора не работает в огромных списках
  • Другие алгоритмы сортировки, такие как быстрая сортировка, имеют лучшую производительность по сравнению с сортировкой по выбору.