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

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

Что нужно знать прежде? В статье ранее про бинарный поиск было рассмотрено такое понятие как "О-большое"(время выполнения алгоритма или объём используемой памяти который растёт с увеличением размера входных данных). Чтобы лучше понять эту статью, необходимо понимать смысл "О-большого" и логарифмов.

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

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

Представьте, что вы пришли в кинотеатр и хотите оставить свою верхнюю одежду в гардеробе. Для хранения верхней одежды существуют специальные вешалки в гардеробе. На каждой вешалке помещается только одна вещь. Вы хотите сдать к примеру две куртки, поэтому требуется выделить вам две вешалки(конечно можно попробовать обе куртки повесить на одну вешалку, но для примера представим что нельзя). Вы оставляете свои две куртки, получаете два "номера" от вешалок и идёте смотреть кино. В сущности, точно также работает память компьютера. Она представляет собой нечто вроде огромного гардероба со множеством вешалок и у каждой вешалки свой адрес. Например: fc0addeb – адрес ячейки памяти. Каждый раз, когда вы хотите сохранить в памяти отдельное значение, вы запрашиваете у компьютера(процессор это делает за вас) место в памяти, а он выдаёт адрес для сохранения значения. Если же вам понадобится сохранить несколько элементов, это можно сделать двумя способами: воспользоваться массивом или списком. Далее рассмотрим массивы и списки, их достоинства и недостатки. Не существует единого мнения или единственно верного способа сохранения данных на все случаи жизни, поэтому нужно понимать различия между массивами и списками.

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

Есть про списки в Python и как их использовать статьи: Списки в циклы, Использование списков ч.1, Использование списков ч.2, Использование списков ч.3

Предположим вы хотите написать приложение для списка дел и управления ими. Описание дел должны храниться в виде списка или массива в памяти. Что использовать — массив или связанный список? Для начала попробуем сохранить дела в массиве. При использовании массива все дела хранятся в памяти непрерывно(то есть рядом друг с другом). Теперь предположим, что мы хотим добавить новое дело, но следующее место в памяти для него - занято(там уже что-нибудь есть)! Представьте, что вы пошли в кинотеатр вместе с друзьями и нашли места для всей своей компании, но тут вдруг приходит ещё один друг, и ему уже сесть некуда. Приходится искать новые места, где смогли бы разместиться все сразу! В нашем случае вам придётся запросить у компьютера другой блок памяти, в котором смогут поместиться сразу все дела. Если вдруг придёт ещё один друг, места опять не хватит и вам всем придётся снова перемещаться в поиске новых мест! Сплошная суета получается! Выходит, что добавление новых элементов в массив – серьёзная проблема. Если свободного места нет и вам каждый раз приходится перемещаться всей компанией друзей в новые места(делам приходится перемещаться каждый раз в новую область памяти), операция добавление нового элемента или элементов будет выполниться крайне медленно. Простейшее решение — это "бронирование мест" заранее! Таким образом, если ваш список состоит всего из 4 дел, вы запрашиваете у компьютера заранее памяти на 10 дел... просто на всякий случай "про запас". Тогда в массив можно будет добавить до 10 дел и ничего перемещать не придётся. Это неплохое обходное решение проблемы с массивами, но у него есть пара недостатков:

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

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

При использовании связанного списка элементы могут размещаться где угодно в памяти. В каждом элементе хранится адрес следующего элемента списка. Таким образом, набор произвольных адресов памяти объединяется в цепочку. Всё происходит как в игре "Найди сокровище". Нужно прийти по первому адресу, там записка: "Следующий элемент находится по адресу 2". Идём по второму адресу, там снова написано: "Следующий элемент находится по адресу 3" и т.д. Добавить элемент в связанный список не составляет труда: просто размещаем его по любому адресу в памяти(на любое свободное место) и сохраняем этот адрес в предыдущем элементе списка.

Со связанными списками ничего перемещать в памяти не нужно. Также сама собой решается проблема, допустим вы прешли в кино с тремя друзьями. Вы пытаетесь найти место на пятерых, но места в кинотеатре уже забиты, и найти соседних друг с другом пять мест невозможно. Похожая ситуация происходит также когда мы используем массив. Допустим мы пытаемся найти места на 10000 элементов. В памяти можно найти места для 10000 элементов, но только не смежные друг с другом! И для создания массива уже не хватает места! Но при хранении данных в связанном списке вы фактически скажите: "Окей, тогда садимся на любые свободные места и смотрим кино". Если любое необходимое количество мест есть в памяти компьютера, вы сможете сохранить все данные в связанном списке. В случае с массивом, если не можете разместить всё рядом друг с другом — "вынуждены будите покинуть кинотеатр"!

Если связанные списки так хороши, то зачем тогда массивы и чем они остаются также хороши?

Массивы

На сайтах со всевозможными рейтингами, тестами и хит-парадами применяется хитрая тактика для увеличения количества просмотров. Вместо того чтобы вывести весь список на одной странице, такие сайты размещают информацию по одному элементу на страницу и заставляют пользователей нажимать на кнопку "Далее" для перехода к следующему элементу. Может быть так, например, что рейтинг новостей не выводится на одной странице. В результате просмотра всего списка новостей сайту удаётся показать вам рекламу на всех страницах пока вы нажимаете "Далее" или "Показать ещё". Было бы гораздо лучше в таких случаях увидеть сразу весь список.

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

Терминология

Элементы массива пронумерованы, причём нумерация начинается с 0, а не с 1. Новичков этот факт может запутывать. Тем не менее выбор нулевой начальной позиции упрощает написание кода при работе с массивом, поэтому программисты остановились на этом варианте. Почти во всех языках программирования нумерация элементов массива начинается с 0. Позиция элемента называется его индексом. Таким образом, вместо того чтобы говорить, например, "Значение 20 находится в позиции 1", правильно сказать "Значение 20 имеет индекс 1". Термин "индекс" означает то же, что и "позиция" в случае с массивами. Предположим, вы хотите вставить элемент в начало массива. Сколько времени на это потребуется?

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

Предположим, вы хотите чтобы список дел напоминал календарь. Прежде данные добавлялись только в конец списка, а теперь они должны добавляться в порядке их выполнения. Что лучше подойдёт для вставки элементов в середину: массив или список? Со списком задача решается изменением указателя в предыдущем элементе. А при работе с массивом придётся перемещать или сдвигать все элементы. Если свободного места не осталось, все данные придётся скопировать в новую область памяти! В общем случае получается что списки больше подходят для вставки элементов в середину.

Указатели. Именно с помощью указателей каждый элемент связанного списка указывает на следующий элемент списка. В каждом элементе связанного списка выделяется некоторый объём памяти для хранения адреса следующего элемента. Эта часть элемента называется указателем. Если вы будите писать программы на низкоуровневом языке программирования очень полезно понимать что значит указатель на объект данных в памяти.

Удаление

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

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

O(n) – линейное время; O(1) – постоянное время.

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

Массивы или списки?

Массивы используются часто, поскольку имеют множество преимуществ перед списками. Во-первых, данные из них проще читать. Во-вторых, массивы поддерживают произвольный доступ. Всего существует два вида доступа: произвольный и последовательный. При последовательном доступе элементы читаются по одному, начиная с первого. Связанные списки поддерживают только последовательный доступ. Если вы захотите прочитать 10-й элемент связанного списка, нам придётся прочитать первые 9 его элементов и перейти по ссылкам к 10-му элементу. Многие реальные ситуации требуют произвольного доступа, поэтому массивы часто применяются на практике. Однако даже безотносительно произвольного доступа массивы работают быстрее, поскольку могут использовать такой принцип как "кэширование". Возможно, вы представляете себе процесс чтения как восприятие одного элемента за раз. Но на самом деле компьютеры читают целыми разделами, поскольку это значительно ускоряет переход к следующему элементу. С массивами можно сделать то, что не получится со связанными списками. С помощью массива можно прочитать целый раздел элементов. В связанном списке местоположение следующего элемента неизвестно. Придётся прочитать элемент, узнать, где находится следующий, а затем прочитать и его. Таким образом, массивы обеспечивают не только произвольный, но и более быстрый доступ к данным!

А как насчёт эффективного использования памяти? Помните, что в случае с массивами обычно выделяют больше памяти, чем нужно, и если в конечном итоге она окажется не нужна, то получается, ресурс расходуется впустую? На деле конечно же(особенно сегодня и думаю в будущем) объём такой неиспользованной памяти получается не очень то большим(в сравнении с памятью современных устройств). С другой стороны, когда вы применяете связанный список, вы выделяете дополнительную память для каждого элемента, поскольку в ней сохраняется адрес следующего элемента. Таким образом данные в связанном списке занимают больше места, при аналогичной размерности массива, если их элементы относительно невелики. Конечно, если элементы массива крупные, то даже один слот неиспользованной памяти может оказаться очень большим, а объём дополнительной памяти, используемой для хранения указателей(адресов на последующий элемент), по сравнению с ним будет совсем незначительным. Таким образом, массивы используются чаще, чем связанные списки, за исключением особых случаев.

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

Объединим все знания выше для построения алгоритма: сортировка выбором. Чтобы понять этот алгоритм, представьте, у вас на компьютере хранится музыка и для каждого исполнителя хранится счётчик воспроизведений его звукозаписей. Вы хотели бы отсортировать список по убыванию счётчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это реализовать? Одно из возможных решений — пройти по списку, найти исполнителя с наибольшим количеством воспроизведений и добавить его в новый список. Потом нужно сделать те же действия, но уже со следующим по количеству воспроизведений исполнителем. Продолжаем действовать так до конца, пока последнего исполнителя не перенесём в новый отсортированный список. А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время O(n) означает, что вы по одному разу обращаетесь к каждому элементу списка(или массива). Например, при простом поиске по списку исполнителей каждый исполнитель будет проверен один раз. Чтобы найти исполнителя с наибольшим значением счётчика воспроизведений, необходимо проверить каждый элемент в списке. Это получается сделать за время O(n). Итак, имеется операция, выполняемая за время O(n), и её необходимо выполнить n раз: всё это потребует времени O(n * n) или

Алгоритмы сортировки очень полезны. Например, вы можете отсортировать: имена или фамилии в телефонной книге; даты; сообщения электронной почты и т.п. Алгоритм сортировки выбором легко объясняется, но медленно работает. Быстрая сортировка — более эффективный алгоритм сортировки, который выполняется за время: Но об этом в следующей статье.

Пример кода

Напишем две функции. Выполним сортировку массива по возрастанию. Сначала напишем функцию для поиска наименьшего значения элемента массива:

def findSmallestEl(arr):
  smaller = arr[0]  # Для хранения наименьшего значения
  smaller_i = 0  # Для хранения индекса наименьшего значения
  for i in range(1, len(arr)):
    if arr[i] < smaller:
      smaller = arr[i]
      smaller_i = i
  return smaller_i

Затем напишем основную функцию алгоритма сортировки выбором:

# Сортируем массив
def selectionSort(arr):
  newArr = []  # Новый массив, как для результат сортировки
  for i in range(len(arr)):
      # Находим наименьший элемент в массиве с помощью вспомогательной функции
      smallest = findSmallestEl(arr)
      newArr.append(arr.pop(smallest))  # Добавляем наименьший элемент в новый массив
  return newArr
  
print(selectionSort([8, 1, 5, 2, 9, 4]))  # Пример работы функции

P.S. Подробнее об остальных алгоритмов будет в следующих статьях.

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.