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

7.1 Определение сортировки выбором

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

Принцип работы:

1. Начинаем с первого элемента массива.
2. Находим наименьший элемент в оставшейся неотсортированной части массива.
3. Меняем местами наименьший элемент и первый элемент неотсортированной части.
4. Повторяем процесс для следующего элемента, пока не будет отсортирован весь массив.

Пошаговый процесс

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

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

Временная сложность:

• В худшем случае: O(n^2) — происходит, когда элементы изначально упорядочены в обратном порядке или случайным образом.
• В среднем случае: O(n^2) — происходит для случайного расположения элементов.
• В лучшем случае: O(n^2) — даже если массив уже отсортирован, алгоритм всё равно выполняет те же самые сравнения.

Пространственная сложность:

O(1) — так как алгоритм использует постоянное количество дополнительной памяти (только несколько переменных для хранения временных значений).

7.2 Реализация алгоритма сортировки выбором

Реализация алгоритма очень простая:

Шаг 1: находим минимальный элемент среди всех элементов и меняем его местами с первым.

Шаг 2: находим минимальный элемент среди всех элементов, кроме первого, и меняем его местами со вторым.

Шаг 3: находим минимальный элемент среди всех элементов, кроме первого и второго, и меняем его местами с третьим.

Реализация на Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Находим минимальный элемент в оставшейся неотсортированной части массива min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # Меняем найденный минимальный элемент с первым элементом неотсортированной части arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Возвращаем отсортированный массив

# Пример использования:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Отсортированный массив:", sorted_arr)
# Вывод: Отсортированный массив: [11, 12, 22, 25, 64]

Пример работы алгоритма:

1. Первый проход (i = 0):
   1. Находим минимальный элемент (11) в неотсортированной части массива [64, 25, 12, 22, 11].
   2. Меняем 11 с 64.
   3. Массив: [11, 25, 12, 22, 64]
2. Второй проход (i = 1):
   1. Находим минимальный элемент (12) в неотсортированной части массива [25, 12, 22, 64].
   2. Меняем 12 с 25.
   3. Массив: [11, 12, 25, 22, 64]
3. Третий проход (i = 2):
   1. Находим минимальный элемент (22) в неотсортированной части массива [25, 22, 64].
   2. Меняем 22 с 25.
   3. Массив: [11, 12, 22, 25, 64]
4. Четвёртый проход (i = 3):
   1. Находим минимальный элемент (25) в неотсортированной части массива [25, 64].
   2. 25 уже на своём месте, обмен не требуется.
   3. Массив: [11, 12, 22, 25, 64]

Алгоритм завершается, так как все элементы отсортированы.

2

Задача

Модуль 1: Python Core, 18 уровень, 6 лекция

Недоступна

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

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

Открыть

2

Задача

Модуль 1: Python Core, 18 уровень, 6 лекция

Недоступна

Сортировка чисел

Сортировка чисел

Открыть