Сортировка данных в информатике: что это такое, как исполняется
Содержание:
Для упрощения восприятия, анализа, выборки данных в таблицах или проводнике их целесообразно структурировать определённым образом. Рассмотрим, что такое сортировка данных в информатике. Разберёмся, как происходит организация информации, какие типы данных существуют, как работать с диапазонами.
Сортировка информации в информатике: что это
Табличные данные человеку легче воспринимать, анализировать, выявлять закономерности и т. д., когда они расположены в определённом порядке. Сортировка записей в базе данных – это процесс упорядочивания её элементов по определённому критерию, в указанной последовательности. Поле, которое используется для изменения структуры БД, называют ключом сортировки.
История упорядочивания информации начинается с конца XIX века с создания электромеханического табулятора, способного автоматически обрабатывать поступающие на перфокартах сведения. За
130 лет развития разработаны десятки методов сортировки:
Для выбора оптимального алгоритма для текущей задачи оценивается ряд параметров претендентов. Основные критерии:
Различают устойчивую и неустойчивую сортировки, внутреннюю и внешнюю. Отдельно стоят алгоритмы, в которых не заложено сравнение поступающих сведений: подсчётом, блочная, поразрядная.
Зачем и как проводится сортировка данных в информатике
Дана таблица средней нагрузки на ресурсы компьютера за месяц.
Для обработки полученных сведений их необходимо отсортировать по какому-то критерию (в исходном варианте это дата). Например, выявим, в какие дни компьютер потреблял больше всего электрической энергии. Для этого упорядочим сведения по столбику CPU – чем сильнее нагружен процессор, тем больше он потребляет энергии – по убыванию – от большего значения к меньшему.
В таком виде таблица более полезна для анализа, выборки информации человеком. Из неё, например, можно понять, в какие дни модельер больше работал, какими программами (Soft-1 – Soft-5) пользовался, когда активнее эксплуатировал интернет и т. д.
В офисных программах предусмотрены функции упорядочивания с условиями, многоуровневой сортировки. Пример последней – размещение информации в порядке убывания сначала по значениям ячеек в столбике «CPU», затем – «Ethernet». На практике это значит: если два-три дня средняя нагрузка на процессор была одинаковой, выше в таблице будет запись, когда активнее использовалось интернет-соединение (Ethernet).
Опция фильтра позволяет исключить из упорядочивания (не отображать) без удаления из таблицы ненужные сведения.
Схожие функции, кроме сложного упорядочивания, доступны для Проводника и десятков иных приложений.
Возможна сортировка в пределах указанного выделения – затрагиваются только выделенные ячейки, столбики либо строки. На примере информация отсортирована только в столбике «Space», в остальных не затронута.
Расскажите, с какой целью используется процедура сортировки данных в компьютерных и мобильных приложениях.
Зачем нужна сортировка в программировании
И почему это любят спрашивать на собеседовании.
Приходишь такой на собеседование, а тебе говорят: «Расскажи про алгоритмы сортировок?» А зачем? А нельзя просто отсортировать и всё?
Что такое сортировка
Сортировка данных — это когда мы их упорядочиваем по какому-то признаку.
Например, в школе есть классный журнал, в котором все ученики отсортированы по фамилии. Или товары в интернет-магазине могут выводиться сначала дешёвые, потом дорогие. Или бывает сортировка товаров по популярности: используют внутреннюю переменную «популярность товара» и смотрят на её значение.
Почему нельзя просто отсортировать
Если у вас небольшой и понятный массив, то ничто не мешает взять встроенную функцию языка программирования типа sort() в JavaScript. Она пошуршит каким-то своим алгоритмом и вернёт отсортированный массив.
Сложности с сортировкой начинаются, когда:
❌ массивы данных большие — на тысячи, десятки и сотни тысяч элементов;
❌ может быть затруднён доступ к данным (например, они идут потоком);
❌ возможностей железа не хватает и нужны более экономные алгоритмы, чем те, которые встроены в язык программирования.
Тогда нужно выбирать специализированные алгоритмы сортировки, а то и оптимизировать их под свои задачи.
Какие бывают сортировки
Существуют десятки алгоритмов сортировки, каждый из которых хорош в чём-то своём. На одних легко объяснять принципы сортировки, другие хороши при работе с большими массивами, третьи оптимизированы по скорости, четвёртые — по числу процессорных циклов, компактности кода и т. д.
Самые популярные, которые вы встретите:
В ближайших статьях покажем примеры.
Почему про это любят спрашивать на собеседованиях
На собеседовании вам могут предложить либо выбрать сортировочный алгоритм под задачу, либо реализовать его для конкретных данных. Зачем это:
В целом ничто не мешает натренироваться в вопросах сортировки и показать через это свою эрудированность.
Что дальше
Впереди много разных видов сортировок — как работают, чем отличаются, где применяются. А главное — мы наглядно покажем, что делают популярные сортировки и почему их назвали именно так.
Алгоритмы сортировки
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.
Виды алгоритмов сортировки
Сортировка пузырьком / Bubble sort
Сортировка пузырьком — это простейший и один из самых известных алгоритмов сортировки. Идея заключается в последовательном сравнении значений соседних элементов. Если текущий элемент больше следующего, меняем их местами. Алгоритм необходимо повторять до тех пор, пока массив не будет отсортирован.
Плюсы и минусы
Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.
Пример реализации на Kotlin:
Сортировка перемешиванием / Shaker (cocktail, ripple, shuffle, shuttle) sort
Также известна как шейкерная или коктейльная сортировка.
Общая идея алгоритма:
Пример реализации на Kotlin:
Сложность у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше (обычно менее чем в два раза быстрее).
Сортировка расчёской / Comb sort
Достигается это тем, что вместо сравнения соседних элементов, сравниваются элементы на достаточно большом расстоянии друг от друга, постепенно уменьшая это расстояние. Сначала разрыв между элементами берётся максимальный, т.е. на единицу меньше, чем размер массива. Затем на каждой итерации расстояние уменьшается путём деления расстояния на фактор уменьшения. Так продолжается до тех пор, пока разность индексов сравниваемых элементов не достигнет единицы. Тогда сравниваются уже соседние элементы как и в сортировке пузырьком, но эта итерация будет последней.
Пример реализации на Kotlin:
Сортировка вставками / Insertion sort
Общая идея алгоритма:
Пример реализации на Kotlin:
Сортировка Шелла / Shell sort
Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:
Существуют и другие последовательности.
Пример реализации на Kotlin:
| Сложность | Лучшее | Среднее | Худшее |
|---|---|---|---|
| Время | O(n log n) | зависит от выбранных шагов (d) | O(n 2 ) или O(n log 2 n) (зависит от выбранных шагов) |
| Память | O(1) |
Сортировка выбором / Selection Sort
Общая идея алгоритма:
Пример реализации на Kotlin:
| Сложность | Лучшее | Среднее | Худшее |
|---|---|---|---|
| Время | O(n 2 ) | O(n 2 ) | O(n 2 ) |
| Память | O(1) |
Быстрая сортировка / Quick Sort
Общая идея алгоритма:
Пример реализации на Kotlin:
| Сложность | Лучшее | Среднее | Худшее |
|---|---|---|---|
| Время | O(n) | O(n log n) | O(n 2 ) |
| Память | O(n) |
Сортировка слиянием / Merge sort
Общая идея алгоритма:
Пример реализации на Kotlin:
| Сложность | Лучшее | Среднее | Худшее |
|---|---|---|---|
| Время | O(n log n) | O(n log n) | O(n log n) |
| Память | O(n) |
Пирамидальная сортировка / Heap sort
Общая идея алгоритма:
| Сложность | Лучшее | Среднее | Худшее |
|---|---|---|---|
| Время | O(n log n) | O(n log n) | O(n log n) или O(n) (при одинаковых ключах) |
| Память | O(1) |
Сортировка подсчётом / Counting sort
Общая идея алгоритма (простой вариант):
Пример реализации на Kotlin:
Блочная (карманная, корзинная) сортировка / Bucket sort
Общая идея алгоритма:
Пример реализации на Kotlin:
Поразрядная (цифровая) сортировка / Radix sort
Перед началом сортировки необходимо знать:
Общая идея алгоритма:
Пример реализации на Kotlin:
Битонная сортировка / Bitonic sort
Общая идея алгоритма:
Чтобы превратить произвольную последовательность в битонную, нужно:
Пример реализации на Kotlin:
| Сложность | Лучшее | Среднее | Худшее |
|---|---|---|---|
| Время | O(log 2 (n) | O(log 2 (n) | O(log 2 (n) |
| Память | O(log 2 (n) |
Timsort
Общая идея алгоритма:
Пример реализации на Kotlin:
Алгоритмы и структуры данных для начинающих: сортировка
Авторизуйтесь
Алгоритмы и структуры данных для начинающих: сортировка
В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого — сортировки пузырьком — и закончим «быстрой сортировкой» (quicksort).
Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае.
Метод Swap
Пузырьковая сортировка
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n) | O(n 2 ) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Сортировка пузырьком — это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива.
Например, у нас есть массив целых чисел:
При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:
Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:
Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6.
И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.
При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу.
Сортировка вставками
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n) | O(n 2 ) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.
Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса — уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом:
Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.
Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:
Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным.
Далее мы переходим к числу 7. Поскольку 7 больше, чем любое значение в отсортированной части, мы переходим к следующему элементу.
На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.
Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:
Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.
Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.
Сортировка выбором
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n) | O(n 2 ) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Сортировка выбором — это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.
При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.
Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение — 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход — на этот раз по индексам от 1 до n — 1.
На втором проходе мы определяем, что наименьшее значение — 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию.
Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.
После еще двух проходов алгоритм завершает свою работу:
Сортировка слиянием
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n·log n) | O(n·log n) | O(n·log n) |
| Память | O(n) | O(n) | O(n) |
Разделяй и властвуй
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer).
Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге — один из примеров такого алгоритма.
Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много — до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную.
Насколько эффективны эти алгоритмы?
Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.
Сортировка слиянием
При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.
Давайте посмотрим на такой массив:
Разделим его пополам:
И будем делить каждую часть пополам, пока не останутся части с одним элементом:
Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.
Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.
Для работы алгоритма мы должны реализовать следующие операции:
Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием — не самое лучшее решение, когда надо отсортировать частично упорядоченный массив.
Быстрая сортировка
| Сложность | Наилучший случай | В среднем | Наихудший случай |
| Время | O(n·log n) | O(n·log n) | O(n 2 ) |
| Память | O(1) | O(1) | O(1) |
Быстрая сортировка — это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:
Давайте посмотрим на работу алгоритма на следующем массиве:
Сначала мы случайным образом выбираем ключевой элемент:
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого — в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре).
На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.
Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное — помнить, что нам важно именно ключевое значение, а не его индекс.
Снова применяем быструю сортировку:
У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу.
Заключение
На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#.
Основные виды сортировок и примеры их реализации
Памятка для тех, кто готовится к собеседованию на позицию разработчика
На собеседованиях будущим стажёрам-разработчикам дают задания на знание структур данных и алгоритмов — в том числе сортировок. Академия Яндекса и соавтор специализации «Искусство разработки на современном C++» Илья Шишков составили список для подготовки с методами сортировки, примерами их реализации и гифками, чтобы лучше понять, как они работают.
Пузырьковая сортировка и её улучшения
Сортировка пузырьком
Сортировка пузырьком — один из самых известных алгоритмов сортировки. Здесь нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.
Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.
Сортировка перемешиванием (шейкерная сортировка)
Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.
Сортировка расчёской
Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.
Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.
Простые сортировки
Сортировка вставками
При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.
Сортировка выбором
Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.
Быстрая сортировка
Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.
Быструю сортировку изобрели в 1960 году для машинного перевода: тогда словари хранились на магнитных лентах, а сортировка слов обрабатываемого текста позволяла получить переводы за один прогон ленты, без перемотки назад.
Сортировка слиянием
Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). Здесь массив разбивается на две примерно равные части и каждая из них сортируется по отдельности. Затем два отсортированных подмассива сливаются в один.
Пирамидальная сортировка
При этой сортировке сначала строится пирамида из элементов исходного массива. Пирамида (или двоичная куча) — это способ представления элементов, при котором от каждого узла может отходить не больше двух ответвлений. А значение в родительском узле должно быть больше значений в его двух дочерних узлах.
Пирамидальная сортировка похожа на сортировку выбором, где мы сначала ищем максимальный элемент, а затем помещаем его в конец. Дальше нужно рекурсивно повторять ту же операцию для оставшихся элементов.
