Структуры данных и алгоритмы
(Вторая часть — сортировка)
В первой части нашего исследования структур данных и алгоритмов мы узнали, что использование отсортированного массива обеспечивает большую гибкость, когда речь идет о таких задачах, как поиск, изменение или удаление элементов. Это становится ценным при работе со многими элементами, которые являются общими в нашей повседневной деятельности. Поскольку эти действия используются часто, необходимо уделить некоторое время обсуждению алгоритмов сортировки, особенно при работе с неупорядоченными массивами.
Статья будет структурирована следующим образом:
Как бы вы это сделали?
Пузырьковая сортировка
Сортировка выбором
Сортировка вставками
Как бы вы это сделали?
Как личность вы имеете преимущества перед компьютерной программой. Вы можете посмотреть на всех детей сразу и быстро выбрать самого высокого, не измеряя и не сравнивая каждого.
После некоторой неформальной перестановки вы можете легко выстроить всех детей в линию, как показано на рисунке.
Однако компьютерная программа не может обрабатывать данные таким же образом. Он может сравнивать только двух детей одновременно из-за того, как работают операторы сравнения. Эта ограниченная перспектива является общей темой алгоритмов. Хотя людям все может показаться простым, алгоритмы не могут видеть общую картину. Вместо этого они сосредотачиваются на конкретных деталях и следуют простым правилам.
Три алгоритма в этой главе повторяют два шага до тех пор, пока данные не будут отсортированы.
Пузырьковая сортировка
Пузырьковая сортировка — это простой алгоритм сортировки, который многократно проходит по списку элементов и сравнивает соседние элементы, меняя их местами, если они расположены в неправильном порядке. Это называется «пузырьковой сортировкой», потому что элементы меньшего размера «всплывают» вверх списка, а элементы большего размера «опускаются» вниз.
Вот как работает пузырьковая сортировка:
- Начните со сравнения первых двух элементов списка. Если первый элемент больше второго, поменяйте их местами.
- Перейдите к следующей паре элементов и сравните их. Опять же, поменяйте местами, если это необходимо.
- Продолжайте этот процесс для всего списка, многократно сравнивая и меняя местами соседние элементы до тех пор, пока перестановки не понадобятся.
- После одного прохода по списку самый большой элемент «поднимется» на последнюю позицию. Повторите процесс для оставшихся несортированных элементов.
- Продолжайте повторять шаги 1–4, пока весь список не будет отсортирован.
Пузырьковую сортировку легко понять и реализовать, но она не очень эффективна для больших списков. Его средняя и наихудшая временная сложность составляет O(n²), где «n» — количество элементов в списке. Это делает его непрактичным для сортировки больших наборов данных. Тем не менее, это может быть отличным выбором для небольших списков или в качестве учебного упражнения для понимания алгоритмов сортировки.
Сортировка выбором
Сортировка выбором — это простой алгоритм сортировки, который работает, многократно выбирая минимальный (или максимальный) элемент из несортированной части массива и помещая его в начало (или конец) отсортированной части. Он имеет временную сложность O(n²) для среднего и наихудшего сценариев, что делает его неэффективным для больших списков.
Вот как работает алгоритм сортировки выбором:
- Найдите минимальный (или максимальный) элемент в несортированной части массива.
- Поменяйте местами его с первым элементом несортированной части.
- Повторите вышеуказанные шаги для оставшейся несортированной части массива, исключая элемент, который только что был помещен в отсортированную часть.
Сортировка выбором называется так потому, что она «выбирает» наименьший (или самый большой) элемент и «пузырьками» доводит его до нужного положения в отсортированной части массива. Несмотря на свою простоту, сортировка выбором неэффективна для больших массивов из-за ее квадратичной временной сложности.
В отличие от некоторых других алгоритмов сортировки, таких как сортировка пузырьком, сортировка выбором не постоянно обменивается элементами при сканировании массива. Эта характеристика может быть полезной в ситуациях, когда замена элементов обходится дорого.
Сортировка вставками
Сортировка вставками — это простой алгоритм сортировки, который строит окончательный отсортированный массив по одному элементу за раз. Это алгоритм сортировки на основе сравнения, в котором массив делится на отсортированную и несортированную части. На каждой итерации алгоритм берет элемент из несортированной части и вставляет его в правильную позицию в отсортированной части.
Вот как работает сортировка вставками:
- Начните со второго элемента (индекс 1) и сравните его с первым элементом (индекс 0).
- Если второй элемент меньше (или больше, в зависимости от порядка сортировки), чем первый элемент, поменяйте их местами.
- Перейдите к третьему элементу (индекс 2) и сравните его с предыдущими элементами в отсортированной части. Вставьте его в правильное положение внутри отсортированной части, сдвинув большие элементы вправо.
- Повторите процесс для оставшихся несортированных элементов, каждый раз вставляя текущий элемент в правильное положение внутри отсортированной части.
Сортировка вставками эффективна для небольших наборов данных или частично отсортированных массивов. Он имеет линейную временную сложность O (n) для отсортированных массивов. Однако его временная сложность в наихудшем случае является квадратичной, что делает его менее подходящим для больших массивов.
Таким образом, сортировка вставками — это простой алгоритм сортировки, который легко понять и реализовать. Хотя это может быть не самый эффективный выбор для больших наборов данных, он может быть практичным вариантом для небольших или отсортированных массивов.
