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

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

ВЫБОР СОРТИРОВКИ — это алгоритм сравнительной сортировки, который используется для сортировки случайного списка элементов в порядке возрастания. Сравнение не требует много дополнительного места. Для временной переменной требуется только одно дополнительное пространство памяти.

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

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

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

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

Пример

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

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

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

[21,6,9,33,3]

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

[3,6,9,21,33]

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

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

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

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

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

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

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

Фоллоwing на изображении показан несортированный список

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

Шаг 1)

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

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

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

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

Шаг 2)

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

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

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

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

Шаг 3)

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

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

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

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

Шаг 4)

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

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

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

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

Шаг 5)

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

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

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

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

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

Фоллоwing код показывает реализацию сортировки выбором с использованием Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

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

[3, 6, 9, 21, 33]

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

Объяснение кода следующее

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

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

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

Время КомplexСортировка выбором

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

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

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

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

Сортировка выбором имеет три категории товаров.plexа именно;

  • Худший случай – здесь представленный список расположен в порядке убывания. Алгоритм выполняет максимальное количество выполнений, которое выражается как [Big-O] O(n2)
  • Лучший случай – это происходит, когда предоставленный список уже отсортирован. Алгоритм выполняет минимальное количество выполнений, которое выражается как [Big-Omega] ?(н2)
  • Средний случай – это происходит, когда список находится в случайном порядке. Средний комplexity выражается как [Big-theta] ?(n2)

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

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

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

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

Преимущества сортировки выбором

Фоллоwing преимущества сортировки выбором

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

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

Фоллоwing недостатки сортировки выбором.

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

Итоги

  • Сортировка выбором — это алгоритм сравнения на месте, который используется для сортировки случайного списка в упорядоченный список. У него есть время, комplexность O(n2)
  • Список разделен на два раздела: отсортированный и несортированный. Минимальное значение выбирается из несортированного раздела и помещается в отсортированный раздел.
  • Это повторяется до тех пор, пока все элементы не будут отсортированы.
  • Реализация псевдокода в Python 3 включает использование двух циклов for и оператора if для проверки необходимости замены.
  • время комplexity измеряет количество шагов, необходимых для сортировки списка.
  • Самое худшее время complexЭто происходит, когда список расположен в порядке убывания. У него есть время, комplexность [Big-O] O(n2)
  • Время в лучшем случае complexЭто происходит, когда список уже находится в порядке возрастания. У него есть время, комplexность [Big-Omega] ?(н2)
  • Среднее время complexЭто происходит, когда список находится в случайном порядке. У него есть время, комplexность [Большой тэты] ?(n2)
  • Сортировку выбором лучше всего использовать, когда у вас есть небольшой список элементов для сортировки, стоимость замены значений не имеет значения и проверка всех значений обязательна.
  • Сортировка выбором не очень хорошо работает с огромными списками.
  • Другие алгоритмы сортировки, такие как быстрая сортировка, имеют более высокую производительность по сравнению с сортировкой выбором.