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

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

Как работает память

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

Массивы и связанные списки

Что использовать - массив или связанный спи­сок? Для начала попробуем сохранить задачи в массиве, потому что этот способ более по­нятен. При использовании массива все задачи хранятся в памяти непрерывно (то есть рядом друг с другом).

Теперь предположим, что вы захотели добавить четвертую задачу. Но сле­дующий ящик уже занят - там лежат чужие вещи!

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

Если вдруг придет еще один друг, места опять не хватит, и вам всем при­дется перемещаться снова! Сплошная суета. Кроме того, добавление новых элементов в массив станет серьезной проблемой. Если свободного места нет и вам каждый раз приходится перемещаться в новую область в памяти, операция добавления нового элемента будет выполняться очень медленно. Простейшее решение - «бронирование мест»: даже если список состоит всего из 3 задач, вы запрашиваете у компьютера место на 1О позиций." просто на всякий случай. Тогда в список можно будет добавить до 10 за­дач, и ничего перемещать не придется. Это неплохое обходное решение, но у него есть пара недостатков:

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

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

Связанные списки

При использовании связанного списка элементы могут размещаться где угодно в памяти.

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

До­бавить новый элемент в связанный список проще простого: просто разме­стите его по любому адресу памяти и сохраните этот адрес в предыдущем элементе.

Со связанными списками ничего перемещать в памяти не нужно. Также сама собой решается другая проблема: допустим, вы пришли в кино с пя­тью друзьями. Вы пытаетесь найти место на шестерых, но кинотеатр уже забит, и найти шесть соседних мест невозможно. Нечто похожее проис­ходит и с массивами. Допустим, вы пытаетесь найти для массива блок на 1О ООО элементов. В памяти можно найти место для 1О ООО элементов, но только не смежное. Для массива не хватает места! При хранении данных в связанном списке вы фактически говорите: «Ладно, тогда садимся на свободные места и смотрим кино». Если необходимое место есть в памяти, вы сможете сохранить данные в связанном списке.

Массивы

На сайтах со всевозможными хит-парадами и «пер­выми десятками» применяется жульническая такти­ка для увеличения количества просмотров. Вместо того чтобы вывести весь список на одной странице, они размещают по одному элементу на странице и заставляют вас нажимать кнопку Next для пере­хода к следующему элементу.

Например, «десятка лучших злодеев в сериалах» не выводится на одной странице.
Вместо этого вы начинаете с № 10 (Ньюман из «Сайнфелда») и нажимаете Next на каждой странице, пока не доберетесь до № 1 (Густава Фринг из «Во все тяжкие»). В результате сайту удается показать вам рекла­ му на целых 1О страницах, но нажимать Next 9 раз для перехода к первому месту скучно. Было бы гораздо лучше, если бы весь список помещался на одной странице, а вы бы могли просто щелкнуть на имени человека для получения дополнительной информации.

Похожая проблема существует и у связанных списков. Допустим, вы хо­тите получить последний элемент связанного списка. Просто прочитать нужное значение не удастся, потому что вы не знаете, по какому адресу оно хранится. Вместо этого придется сначала обратиться к элементу № 1 и уз­нать адрес элемента № 2, потом обратиться к элементу № 2 и узнать адрес элемента № 3". и так далее, пока не доберетесь до последнего элемента. Связанные списки отлично подходят в тех ситуациях, когда данные должны читаться последовательно: сначала вы читаете один элемент, по адресу переходите к следующему элементу и т. д. Но если вы намерены прыгать по списку туда-сюда, держитесь подальше от связанных списков.

С массивами дело обстоит совершенно иначе. Работая с массивом, вы за­ранее знаете адрес каждого его элемента. Допустим, массив содержит пять элементов и вы знаете, что он начинается с адреса 00. По какому адресу хранится пятый элемент?

Простейшая математика дает ответ: это адрес 04. Массивы прекрасно подхо­дят для чтения элементов в произвольных позициях, потому что обращение к любому элементу в массиве происходит мгновенно. В связанном списке элементы не хранятся рядом друг с другом, поэтому мгновенно определить позицию i-го элемента в памяти невозможно - нужно обратиться к перво­му элементу, чтобы получить адрес второго элемента, затем обратиться ко второму элементу для получения адреса третьего - и так далее, пока вы не доберетесь до i-го.

Вставка в середину списка

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

Что лучше подойдет для вставки элементов в середину: массивы или списки?

• Со списком задача решается изменением указателя в предыдущем элементе.
• А при работе с массивом придется сдвигать вниз все остальные элементы.

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

Удаление

Что, если вы захотите удалить элемент? И снова список лучше подходит для этой операции, потому что в нем достаточно изменить указатель в пре­дыдущем элементе. В массиве при удалении элемента все последующие элементы нужно будет сдвинуть вверх.

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

Ниже приведены примеры времени выполнения основных операций с мас­сивами и связанными списками.

действие	массив	список
Чтение:	Array O(1)	List O(n)
Вставка:	Array O(n)	List O(1)
Удаление:	Array O(n)	List O(1)

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

Какая структура данных используется чаще: массивы или списки? Очевидно, это зависит от конкретного сценария использования. Массивы чрезвычайно популярны из-за того, что они поддерживают произвольный доступ. Всего существуют два вида доступа: произвольный и последовательный. При по­ следовательном доступе элементы читаются по одному, начиная с первого. Связанные списки поддерживают только последовательный доступ. Если вы захотите прочитать 10-й элемент связанного списка, вам придется прочитать первые 9 элементов и перейти по ссылкам к 10-му элементу. Я часто говорю, что массивы обладают более высокой скоростью чтения; это объясняется тем, что они поддерживают произвольный доступ. Многие реальные ситуа­ции требуют произвольного доступа, поэтому массивы часто применяются на практике. Также массивы и списки используются для реализации других структур данных.

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

Допустим, у вас на компьютере записана музы­ка и для каждого исполнителя хранится счет­чик воспроизведений.

Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это сделать? Одно из возможных решений - пройти по списку и найти исполнителя с наибольшим количеством воспроизведений. Этот исполнитель добавля­ется в новый список.

Потом то же самое происходит со следующим по количеству воспроизве­дений исполнителем.

Продолжая действовать так, мы получаем отсортированный список.

Чтобы найти исполнителя с наибольшим значением счетчика воспроиз­ведения, необходимо проверить каждый элемент в списке. Как вы уже видели, это делается за время О(n). Итак, имеется операция, выполняемая за время О(n), и ее необходимо выполнить n раз: Все это требует времени О(n х n), или О(n^2).

Алгоритмы сортировки очень полезны. Например, теперь вы можете отсор­тировать:

• имена в телефонной книге;
• даты путешествий;
• сообщенияэ лектронной почты(от новых к старым).

Алгоритм сортировки выбором легко объясняется, но медленно работает.

Пример кода

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

"""O(n ** 2)"""

def find_smallest(arr):
    """возвращает индекс наименьшего элемента последовательности"""
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


def selection_sort(arr: list):
    """
    при каждом обходе списка находит минимальное значение,
    удаляет это значение из изначального списка и добовляет в
    новый список, который возвращается в результате работы функции
    """
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))
    return new_arr


if __name__ == "__main__":
    assert selection_sort([5, 3, 6, 2, 10]) == [2, 3, 5, 6, 10]

по материалом источника