Алгоритм сортировки выбором с Python Code Пример

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

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

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

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

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

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

Пример

• Например, если индекс минимального значения равен 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 = 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))

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

[3, 6, 9, 21, 33]

Code объяснение

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

Вот Code объяснение:

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

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

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

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

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

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

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

• Худший случай – здесь представленный список расположен в порядке убывания. Алгоритм выполняет максимальное количество выполнений, которое выражается как [Big-O] O(n²)
• лучший случай – это происходит, когда предоставленный список уже отсортирован. Алгоритм выполняет минимальное количество итераций, которое выражается как [Большая Омега] Ω(n).²)
• Средний случай – это происходит, когда список расположен в случайном порядке. Средняя сложность выражается как [Биг-тета] Θ(n)²)

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

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

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

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

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

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

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

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

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

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

Часто задаваемые вопросы (FAQ)