Алгоритмы сортировки и поиска
Приступим к анализу некоторых алгоритмов сортировки. Как следует из названия, их целью является сортировка элементов в структуре данных.
Пузырьковая сортировка
Пузырьковая сортировка — самый простой из алгоритмов, предложенных в этой статье. Имея список, он сравнивает два соседних числа, и если большее из них находится на первой позиции, то оно меняется местами на два числа. Таким образом прокручивается весь список. Чтобы получить правильный результат, пузырьковая сортировка должна быть выполнена несколько раз в одном и том же списке и, следовательно, состоит из двух циклов:
● Внутренний, сколько раз необходимо повторить внешний алгоритм в списке;
● Внешний, сравнение между соседними числами.
Этот алгоритм имеет преимущество, когда список уже полуупорядочен, и рекомендуется только для списков небольшого размера, если размер будет слишком большим, время выполнения также может значительно увеличиться.
Пример с изображением:
В примере список из восьми элементов отсортирован, как вы можете видеть, каждый элемент сравнивается со следующим, и если следующий больше, позиция торгуется.
Как видите, конечный результат еще не полностью отсортирован, поэтому вам нужно будет выполнять парные сравнения, пока не будет отсортирован весь список.
Сортировка вставками
Сортировка вставками начинается с выбора первых двух элементов в списке, сравнения и перемещения самого большого элемента в нужное положение. Затем он также выбирает третий элемент, запоминая два предыдущих, и повторяет тот же шаг, поэтому он меняет порядок элементов в соответствии с их значением.
Этот алгоритм также рекомендуется для небольших наборов данных, производительность сильно ухудшается по мере увеличения размера набора данных.
Пример с изображением:
Как видно, в этом случае рассматриваются не только два элемента, но после первых двух сравнение расширяется до трех элементов, а затем расширяется до четырех. Каждый раз, когда количество рассматриваемых элементов увеличивается, список сортируется.
В примере в первом сравнении ничего не меняется, потому что 25 и 26 уже в правильном положении. Однако при выборе 22 список меняется, потому что 22 перемещается на первую позицию, учитывая, что это наименьшее из выбранных чисел.
В этом случае нет необходимости запускать алгоритм несколько раз, как в случае пузырьковой сортировки. Когда все элементы выбраны, список будет отсортирован.
Сортировка слиянием
Производительность сортировки слиянием не зависит от порядка элементов в структуре данных, она работает в два этапа:
● Разбиение, список делится пополам и еще раз пополам, пока не будут созданы небольшие списки длиной 1;
● Объединение, списки длины 1 объединяются, и по мере их сбора элементы сортируются.
Пример с изображением:
Как видите, список всегда делится пополам путем создания меньших списков, состоящих из двух половинок. Этот процесс, Разделение, применяется до тех пор, пока не останутся небольшие списки длины 1. Когда остается только список длины один, начинается слияние, и списки объединяются путем сортировки элементов.
Сортировка Шелла
Список разбит на небольшие списки, состоящие из двух элементов на стандартном расстоянии.
Например, имея список из двенадцати элементов, если первый элемент помещается во второй список с четвертым элементом, тогда второй элемент будет помещен в список со следующим элементом, таким образом, расстояние между элементами, составляющими два списка не различаются.
Этот процесс происходит для всех элементов в списке.
Затем элементы рассматриваются путем рассмотрения пар, которые были созданы.
На втором этапе сравниваться будут уже не пары, а трио, даже в этом случае расстояние в списке каждого элемента должно быть одинаковым во всех создаваемых подсписках.
Это будет продолжаться до тех пор, пока не останется только один список, состоящий из всех элементов исходного, но отсортированного списка.
Сортировку оболочки рекомендуется использовать в списках, содержащих менее десяти тысяч элементов.
Пример с изображением:
Каждый цвет представляет собой список, в каждом из которых элементы всегда находятся на одном и том же расстоянии. Как можно заметить, элементы в каждом списке отсортированы. Сортировка заканчивается, когда остается только один список размером с исходный список, таким образом, список будет уже полуупорядоченным, и окончательное время сортировки будет намного короче.
Сортировка выбором
Она похожа на пузырьковую сортировку, но не выбирает два соседних элемента, при первом взаимодействии выбирает первый и последний элементы, сравнивает их и помещает самый большой элемент вверху списка. При втором взаимодействии он выберет первый элемент и элемент в предпоследней позиции, еще раз выполнив сравнение и обмен.
Опять же, это не рекомендуется для больших списков.
Пример с изображением:
Как видно из примера, это очень похоже на пузырьковую сортировку, но выбранные элементы являются не первыми и последующими, а первыми и последними — по 1 на каждой итерации.
Алгоритмы поиска
Линейный поиск
Он проходит по списку от первого элемента к последнему. Время выполнения зависит от длины списка, но для его работы элементы не обязательно сортировать.
Бинарный поиск
Для этого типа поиска список должен быть отсортирован, а затем список разделен на две точки. Первая точка — это первый элемент, а вторая точка — это элемент в середине списка. Учитывая значения первого и второго элементов, половину списка можно уже исключить. Например, если первый элемент равен 0, а второй (то есть тот, что в середине списка) равен 10, а элемент, который я ищу, равен 17, то я знаю, что не могу рассмотреть все от 0 до 10, потому что список заказывается.
Теперь второй элемент остается прежним, 10, первый станет элементом в середине нового списка, например 15.
Опять же, все элементы от 10 до 15 могут быть исключены, потому что я знаю, что 17 больше 15, поэтому он будет в части с номерами большими, чем 15. Выбор продолжается таким образом, пока не будет найдено искомое значение.
Пример с изображением:
В этом примере список отсортирован, и мы знаем, что должны найти значение 2. Элемент в середине списка равен 5. 2 меньше 5, поэтому искомый элемент будет слева от списка. список, поэтому правая сторона исключена. Затем вы выбираете новую половину рассматриваемого списка, которая в данном случае соответствует искомому значению.
Поиск по интерполяции
Опять же, список должен быть отсортирован, и необходимы два значения: первый элемент в списке и последний элемент в списке. Если искомое значение выше, чем значение элемента в середине списка, то первым значением становится элемент в середине списка.
Например:
Имея список от 0 до 10, в котором я ищу значение 7.
a (первый элемент) будет равен 0
B (второй элемент) будет равен 10.
Половина списка - 5.
Семь больше пяти, поэтому элемент a теперь примет значение 5, и список станет от 5 до 10. Новая половина равна 8. Таким образом, элемент b станет 8, и теперь у вас есть список между 5 и 8. Это деление происходит до тех пор, пока предмет, который вы ищете, найден.
Пример с изображением:
Даже в этом случае список упорядочен и знает, какое значение искать. Выбирается центральное значение и, как и в бинарном поиске, исключается часть списка, которая не может понять искомое значение. При разделении последнего центр не выбирается, но выделяются первое и последнее значение нового списка. Если значения не совпадают, они исключаются и выбираются соседние значения до тех пор, пока одно из них не совпадет с искомым значением.
