Обработка списков. Двоичный поиск и сортировка

Вопросы:

·     Алгоритмы сортировки элементов списка.

·     Алгоритм двоичного поиска.

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

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

Как же мы можем отсортировать листы в стопке? Например, по возрастанию чисел, которые на них написаны. Тогда после сортировки должно выполняться правило, согласно которому число на листе с порядковым номером i + 1 всегда будет больше числа на листе с порядковым номером i. Или же мы можем отсортировать листы по убыванию чисел на них, тогда после сортировки на листе с номером i + 1 число должно быть меньше числа на листе с номером i. Однако по возрастанию и по убыванию чисел листы можно отсортировать только в том случае, если среди них нет листов с равными числами. Если же такие листы есть, то как бы мы их не перемещали, для всех листов эти правила выполняться не будут. Тогда сортировка по возрастанию превратится в сортировку по неубыванию, а сортировка по убыванию в сортировку по невозрастанию. Возможен и другой порядок.

Как же можно отсортировать листы бумаги в стопке, например, по неубыванию. Мы можем последовательно проверять все пары идущих подряд листов бумаги и отыскивать среди них те, в которых правило, указанное для такой сортировки, не выполняется, то есть в них следующий элемент меньше предыдущего. И мы будем менять местами листы в таких парах. Очевидно, что после некоторого количества таких замен правило сортировки будет выполняться для всех листов стопки. Такая сортировка была названа методом «пузырька».

Напишем функцию сортировки элементов списка методом «пузырька» в модуле, в котором у нас хранятся функции обработки списка ListProcessing. Назовём нашу функцию BubbleSort. У неё будет один аргумент – список a, который нужно отсортировать. Напишем в теле функции бесконечный цикл while. В теле цикла объявим логическую переменную p, в которой будем хранить истинность высказывания о том, что элементы списка уже отсортированы по неубыванию. Предположим, что так и есть, и присвоим p значение «истина». Цикл будет работать до тех пор, пока не подтвердится, что все элементы списка отсортированы по неубыванию. Запишем ветвление для завершения работы цикла. В нём вместо условия будет значение логической переменной p. Если её значение всё ещё будет истинно, то завершим работу цикла с помощью инструкции break. Таким образом мы получили цикл с постусловием.

Перед ветвлением в цикле запишем вложенный цикл для перебора пар элементов. Это будет цикл с параметром i, который изменяется в диапазоне от 0 до предпоследнего индекса списка a и равен его длине, уменьшенной на 2. В теле этого цикла напишем ветвление с условием, что элементы списка a с индексами i и i + 1 расположены по убыванию, то есть условие сортировки не выполняется. Если мы нашли такую пару элементов, значит список уже не отсортирован по неубыванию, поэтому присвоим переменной p значение «ложь». Также поменяем местами элементы в паре. Для этого запишем оператор присваивания элементам списка a с индексами i и i + 1 соответственно значений элементов списка a с индексами i + 1 и i. Мы описали цикл сортировки списка. По завершении сортировки значение списка возвращать не нужно. Так как в функцию список передаётся в виде ссылки на область оперативной памяти, а не в виде копии исходного списка, то функция изменяет непосредственно исходный список, и его значение возвращать необязательно.

def BubbleSort (a):

    while True:

        p = True

        for i in range (0, len (a) - 1):

            if a[i + 1] < a[i]:

                p = False

                a [i], a[i + 1] = a[i + 1], a[i]

        if p:

            break

Протестируем описанную функцию. Для этого сохраним модуль и запустим его на выполнение. Создадим список a из 15 элементов, заполненный случайными числами на промежутке от 1 до 100. Просмотрим созданный список. В нём элементы расположены вразнобой. Теперь вызовем описанную функцию для этого списка и снова просмотрим его. Теперь элементы в нём расположены по неубыванию. Чтобы получить список, отсортированный по невозрастанию, можно использовать метод reverse для списка, отсортированного по неубыванию.

Вернёмся к примеру со стопкой листов бумаги. Допустим, что мы их отсортировали по возрастанию чисел, которые на них написаны. Теперь наши возможности для поиска конкретных листов расширились. Листы с минимальным и максимальным числами расположены соответственно вверху и внизу стопки. Также теперь для поиска листа с заданным числом мы можем использовать не только линейный поиск. Мы можем разделить стопку листов на две равные части и проверить число на верхнем листе в нижней части. Если оно больше искомого, то лист с искомым числом находится в верхней части стопки, в противном случае – в нижней. Мы можем отбросить ненужную часть стопки и над оставшейся частью проделать те же действия. Так будет продолжаться до тех пор, пока на определённом этапе не останется один-единственный лист. После этого нам необходимо проверить, равно ли число на нём искомому.

Для поиска нужного листа мы делим стопку на части, то есть используем принцип, о котором вы наверняка слышали, – «Разделяй и властвуй». Этот принцип распространён в программировании. За счёт того, что на каждом шаге алгоритма мы сокращаем область поиска сразу наполовину, а не на один лист, как при линейном поиске, такой алгоритм работает намного эффективнее. Он был назван двоичным поиском.

Напишем в нашем модуле функцию двоичного поиска элемента в списке. Назовём её SearchInSortedList для того, чтобы подчеркнуть, что она работает лишь в отсортированном списке. Функция будет иметь 2 аргумента: значение искомого элемента – x и список, в котором будет выполнен поиск, – a. Функция будет возвращать индекс искомого элемента или же минус один, если такого элемента нет в списке.  Объявим переменные-указатели f и l, которые будут указывать на промежуток, на котором происходит поиск элемента. Вначале промежутком поиска будет весь список, поэтому присвоим f и l соответственно значения его наименьшего и наибольшего индексов – 0 и len (a) - 1. Теперь запишем цикл while, который будет работать до тех пор, пока f ≠ l. В цикле будем проверять средний элемент промежутка между указателями f и l. Его индекс будет равен (f + l) // 2. Если значение этого элемента меньше x, то мы будем продолжать поиск x после искомого элемента, поэтому изменим указатель начального элемента промежутка на следующий, после проверенного. В противном случае мы будем искать x до проверенного элемента, включая сам элемент. Поэтому присвоим указателю последнего элемента списка индекс проверенного элемента.

После цикла, когда указатели сошлись на одном элементе, запишем ветвление с условием, что a[f] == x. Если это условие выполняется, то функция вернёт значение индекса элемента – f, в противном случае функция вернёт -1.

def SearchInSortedList (x, a):

    f, l = 0, len (a) - 1

    while f != l:

        if a[(f + l) // 2] < x:

            f = (f + l) // 2 + 1

        else:

            f = (f + l) // 2

    if a[f] == x:

        return f

    else:

        return -1

Сохраним модуль и протестируем описанную функцию. Для этого объявим список a из 20 случайных чисел на промежутке от 1 до20 и отсортируем его с помощью функции BubbleSort. С помощью функции SearchInSortedList отыщем в этом списке элемент со значением 5. Функция вернула значение индекса какого-то из элементов списка. Просмотрим список и убедимся, что элемент с этим индексом действительно 5.

Многие из вас наверняка поняли, что сортировка списка – достаточно тяжёлая задача. Поэтому алгоритмы её решения постоянно совершенствуются. Один из самых эффективных методов на сегодняшний день так же, как и двоичный поиск, основан на принципе «Разделяй и властвуй». Этот алгоритм был назван быстрой сортировкой. Рассмотрим, как он работает. Сначала выбирается некоторое базовое значение, назовём его m. После этого список нужно упорядочить так, чтобы в одной его части были элементы, которые меньше m, а в другой  – большие либо равные m. После этого выбираются базовые значения для левой и правой частей списка и повторяются те же действия уже для них. Так происходит до тех пор, пока длина всех промежутков не станет равной одному элементу. Такие промежутки отсортированы сами по себе.

Рассмотрим алгоритм подробнее. Так как он сортирует элементы на некотором промежутке, обозначим его указателями, которые назовём first и last. Сначала в этот промежуток входит весь список. Условимся, что в качестве базового значения будем выбирать значение среднего элемента промежутка. Теперь нужно упорядочить список так, чтобы в его левой части находились элементы, которые меньше m, а в правой части – большие либо равные m. Для этого введём ещё два указателя – b и e, которые вначале будут равны соответственно first и last. Будем передвигать указатель b вправо, увеличивая его значение на 1, пока не найдём элемент списка, который будет большим либо равным Эм. После этого будем двигать указатель Е влево, уменьшая его значение на единицу, пока не найдём элемент списка, меньший либо равный m. После этого проверим, не пересеклись ли указатели, то есть e < b. Если это условие выполняется – поменяем элементы местами, после чего передвинем b и e на одну позицию вправо и влево соответственно. Мы будем повторять эти действия до тех пор, пока указатели b и e не пересекутся. Если же они пересеклись – значит мы уже упорядочили список и от First до e: у нас находятся элементы, которые меньше m, а от b до last – элементы, большие либо равные m. И нам нужно упорядочить уже эти промежутки и так далее. Скорость работы этого алгоритма зависит от выбора опорного значения, поэтому его часто выбирают на указанном промежутке случайно.

Теперь напишем функцию быстрой сортировки списка. Назовём её QuickSort. У неё будет три аргумента: список a,  содержащий элементы, которые необходимо отсортировать, а также индексы начального и конечного элементов промежутка – first и last. В теле функции проверим длину сортируемого промежутка: если указатель first больше либо равен указателю last, то промежуток состоит из одного элемента или пуст, поэтому функция завершит свою работу. Теперь объявим переменную m, в которой будем хранить опорное значение. Выбирать его будем случайно на заданном промежутке. Для этого за пределами функции подключим модуль random, а переменной m будем присваивать значение случайного целого элемента списка a с индексом на промежутке от first до last. Объявим указатели b и e равными, соответственно first и last.

Напишем цикл, который будет работать до тех пор, пока указатели b и e не пересекутся, то есть пока b ≤ e. Напишем цикл, в котором будем передвигать указатель b вправо. Он будет работать до того момента, пока элемент с индексом b будет меньше m. В цикле будем увеличивать значение b на 1. Напишем цикл, который будет передвигать указатель e влево. Он будет работать до тех пор, пока a[e] > m.  В цикле будем уменьшать значение e на 1. Теперь проверим, не пересеклись ли указатели. Для этого напишем ветвление с условием, что b ≤ e. Если это условие не выполняется, то поменяем местами элементы b и e, после чего, соответственно, увеличим и уменьшим на единицу указатели b и e, и продолжим передвигать их вправо и влево, пока они не пересекутся. Если же указатели b и e уже пересеклись, то список упорядочен относительно базового значения m. Мы упорядочим его левую часть, вызвав для этого функцию QuickSort для промежутка от first до e, и правую часть, вызвав функцию для промежутка от b до last.

def QuickSort (a, first, last):

    if first >= last:

        return

    m = a[random.randint (first, last)]

    b, e = first, last

    while b <= e:

        while a[b] < m:

            b = b + 1

        while a[e] > m:

            e = e - 1

        if b <= e:

            a[b], a[e] = a[e], a[b]

            b, e = b + 1, e - 1

    QuickSort (a, first, e)

    QuickSort (a, b, last)

Описание функции завершено, протестируем её. Сохраним модуль и запустим его на выполнение. Создадим список a из 20 случайных чисел от 1 до 20. Просмотрим его. Элементы в нём расположены вразнобой. Вызовем функцию QuickSort для сортировки всего списка a. Для этого укажем промежуток от нулевого элемента до элемента с индексом, равным len (a) / 2. После этого снова просмотрим список. Его элементы расположены по неубыванию. Функция работает правильно.

Сравним скорость работы описанных функций сортировки. Создадим список a из 5000 случайных чисел от 1 до 10 000 и его копию – b. Вызовем функцию сортировки пузырьком для списка a. Функция завершила свою работу с заметной временной задержкой. Теперь вызовем функцию быстрой сортировки для списка b. Она завершила свою работу мгновенно. На экране вы видите таблицу тестирования обоих алгоритмов для списков разной длины. Как видим, для списков с большой длиной использовать быструю сортировку куда выгоднее.

Так как сортировка списков – распространённая операция, в языке Python реализована встроенная функция сортировки списка – sorted, она принимает на вход исходный список и возвращает отсортированный. Если нужно отсортировать список по невозрастанию, то при вызове функции логическому параметру reverse присваивается значение «истина». Функция sorted использует гибридный алгоритм TimeSort. Он наиболее эффективен для списков, содержащих уже упорядоченные последовательности.

Мы узнали:

·     Сортировкой называется упорядочивание элементов множества, в соответствии с некоторыми правилами.

·     Алгоритм сортировки «пузырьком», основанный на последовательной проверке пар элементов.

·     Алгоритмы двоичного поиска и быстрой сортировки, основанные на принципе «Разделяй и властвуй».

·     Для сортировки списков в языке Python можно использовать стандартную функцию sorted.