Лекция №4. Алгоритмы поиска и сортировки

Хорошевич Павел Александрович

Алгоритмы поиска

Линейный поиск

Линейный поиск подразумевает последовательный перебор всех элементов списка.

После обнаружения наилучшего значения выполняются действия, зависящие от условия задачи:

  • остановка обхода списка - “найти индекс первого элемента, который…”;

  • изменение значения переменной - “найти мин./макс. значение”, “определить есть ли …”, “посчитать количество …”;

  • вывод элемента на экран - “вывести все элементы, которые …”.

Обход элементов vs обход индексов списка

lst = [10, -3, 15, 0, -7]

Если по условию задачи не нужно искать индекс подходящих элементов:

for el in lst:
    print(el)

Результат:

10
-3
15
0
-7

Если по условию нужно найти индекс подходящих элементов:

# количество элементов в списке
col = len(lst) 
for i in range(col):
    print(i,"-->", lst[i])

Результат:

0 --> 10
1 --> -3
2 --> 15
3 --> 0
4 --> -7

Бинарный поиск

Бинарный поиск работает только для отсортированных списков.

Найдём в списке значение равное \(key\). Пусть \(mid\) - индекс элемента в середине, \(K_{mid}\) - значение элемента в середине списка:

  1. Если \(key = K_{mid}\), значит элемент найден.
  2. Если \(key < K_{mid}\), значит искомое число меньше числа по индексу \(mid\).
  3. Если \(key > K_{mid}\), значит искомое число больше числа по индексу \(mid\).

Блок-схема алгоритма

Бинарный поиск

Алгоритмы сортировки

Сортировка элементов массива

Задача алгоритма сортировки - расположить элементы массива таким образом, чтобы определённое отношение выполнялось для любой пары соседних элементов.

  • 3, 6, 7, 10, 11, 12, 20, 24
    • a[i] < a[i+1]
  • “a”, “an”, “the”, “then”, “image”, “window”
    • длина a[i] < длина a[i+1]
  • “at”, “bat”, “cat”, “dog”, “mouse”, “rat”
    • алфавитный порядок

Алгоритмы сортировки

  • Сортировка простым обменом (пузырьковая сортировка)
  • Сортировка выбором
  • Сортировка вставками
  • Сортировка подсчётом
  • Сортировка слиянием
  • Быстрая сортировка
  • …

Сортировка простым обменом

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

Блок-схема
def bubleSort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j+1], lst[j]

Возможны две оптимизации:

  • сократить количество итераций вложенного цикла;
  • прекращать сортировку, если на очередной итерации внешнего цикла не произошло перестановок.

Оптимизация метода

  • 1 проход алгоритма: n-1 сравнение
  • 2 проход алгоритма: n-2 сравнений
  • и т.д.
def bubleSort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j+1], lst[j]

Блок-схема
def bubleSort(lst):
    n = len(lst)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n-1-i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                flag = True # произошла замена
        i += 1

Визуализация

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

На каждом проходе алгоритма ищем минимальное значение в неотсортированной части массива и ставим его на текущую позицию.

Блок-схема
def selectionSort(lst):
    n = len(lst)
    for i in range(n-1):
        iMin = i
        for j in range(i, n):
            if lst[j] < lst[iMin]:
                iMin = j
        lst[i], lst[iMin] = lst[iMin], lst[i]

Визуализация

Сортировка вставками

Блок-схема
def insertionSort(lst):
    n = len(lst)
    for i in range(1, n):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j + 1] = lst[j]
            j = j - 1
        lst[j + 1] = key

Визуализация

Типовые задачи на сортировку

  • Поиск: сортировка данных и применение бинарного поиска.
  • Поиск ближайшей пары: найти в множестве из n чисел два числа с наименьшей разностью между ними.
  • Определение уникальности элементов: имеются ли дубликаты в множестве из n элементов? (Найти два соседних элемента разность которых равна 0).
  • Частотное распределение: определение самого часто встречающегося элемента в множестве.

Сложность алгоритмов

Сортировка в Python

В языке Python есть встроенная функция для сортировки последовательностей - sorted().

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

lst = [4, 6, 2, 7, 1]
s = sorted(lst)
print(s)

Функция-ключ

Кроме последовательности, функция sorted() может принимать аргумент с именем key - функцию-ключ.

Функция применяется к каждому элементу последовательности перед началом сортировки.

st_list = ['блок-схема', 'код', 'программа']
print(sorted(st_list))

print(sorted(st_list, key=len)

Задача

Названия групп в электронном расписании сортируются в лексикографическом порядке. Организовать сортировку групп по году поступления.

groups = ['240122', '240124', '240125', '240222', '240223', '240224', '240225', '240323', '240325', '240422', '240423', '240424', '240425', '240523', '240524', '240525']
print(sorted(groups))

Опишем функцию-компаратор, которая переставит в названии группы её номер и год поступления местами:

def convert(g):
    return g[:2] + g[4:] + g[2:4]
print(convert('240122'))

Используем функцию в качестве ключа сортировки:

print(sorted(groups, key=convert))

*Абстрактный тип данных “Хэш таблица”

Хэш таблица хранит каждое значение под уникальным ключом.

Компоненты:

  • список для хранения значений;
  • хэш-функция, которая по значению ключа, вычисляет индекс для хранения значения в списке.

Реализация хэш таблиц

Задача - сохранить отметку за экзамен с привязкой к имени студента.

Реализация в Python

Словарь – это набор ключей и соответствующих им значений.

Данные в словаре не упорядочены.

В Python словарю соответствует тип dict.

d = {}      # пустой словарь
d = dict()  # второй способ создать пустой словарь

Добавление и получение значений из словаря

Квадратные скобки [] позволяют добавить и получить значение из словаря.

bel2rus = {}
bel2rus["гарбуз"] = "тыква"
bel2rus["гузiк"] = "пуговица"
bel2rus["цмок"] = "дракон"

print(bel2rus)
print(bel2rus["гузiк"]) # получаем значение по ключу "гузiк"

Словарь можно заполнить при его создании:

bel2rus = {"цмок": "дракон", "гузiк": "пуговица", "гарбуз": "тыква"}
print(bel2rus)

Тип ключей в словаре

Ключами в словаре могут быть значению любого неизменяемого типа: int, float, str.

# целочисленный ключ, строковое значение
num_names={1:"Один", 2: "Два", 3:"Три"} 

# вещественный ключ, строковое значение
dec_names={1.5:"Одна целая, пять десятых", 2.5: "Два с половиной"}

# строковый ключ, целочисленное значение
roman_nums = {'I':1, 'II':2, 'III':3, 'IV':4, 'V':5}

# строковый ключ, значение - список
shop = {'фрукты': ['ананас', 'банан'], 'овощи': ['огурец', 'капуста']}

shop["фрукты"][1]?

Методы класса dict

Таблица 1: Некоторые методы класса dict
Метод Значение
<словарь>.get(<ключ>)
<словарь>.get(<ключ>, <значение>)		 Если в словаре есть <ключ> - получить его значение, иначе вернуть <значение>
<словарь_1>.update(<словарь_2>) Обновить содержимое <словарь_1> парами ключ-значение из <словарь_2>
<словарь>.keys() Получить список ключей
<словарь>.values() Получить список значений

Пример задачи

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

text = input("Введите текст: ")

text = text.lower()

for ch in '.,!?':
   text = text.replace(ch, " ")

words = text.split()

counts = {}

for w in words:
    if w in counts:
       counts[w] = counts[w] + 1
    else:
       counts[w] = 1

uWords = list(counts.keys())
uWords.sort()

for w in uWords:
    print(f"{w} - {counts[w]}")

Визуализация решения