Quicksort

Структуры данных и алгоритмы на Python

Miriam Antona

Software engineer

Quicksort

  • Следует принципу «разделяй и властвуй»
  • Реализован во многих языках программирования
  • Техника разбиения
    • Опорный элемент
    • элементы меньше опорного -> влево
    • элементы больше опорного -> вправо
  • Элементы слева сортируются рекурсивно
  • Элементы справа сортируются рекурсивно
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами.

Структуры данных и алгоритмы на Python

Quicksort — в действии

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

  • Разбиение Хоара
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Два указателя: левый указывает на второй элемент, правый — на последний.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Два указателя: левый указывает на третий элемент, правый — на последний.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Два указателя: левый указывает на третий элемент, правый — на пятый.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Два указателя: левый указывает на третий элемент, правый — на пятый. Стрелки показывают, что третий и пятый элементы будут переставлены местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Два указателя: левый указывает на третий элемент, правый — на пятый. Третий и пятый элементы поменяны местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Два указателя: левый указывает на четвёртый элемент, правый — на пятый.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Оба указателя — левый и правый — указывают на четвёртый элемент.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Левый указатель указывает на четвёртый элемент, правый — на третий.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим. Левый указатель указывает на четвёртый элемент, правый — на третий. Стрелки показывают, что первый и третий элементы будут переставлены местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

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

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Третий элемент выделен зелёным цветом.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Третий элемент выделен зелёным, первые два — оранжевым, что обозначает левую часть списка.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым, третий — зелёным. Оба указателя указывают на второй элемент.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым, третий — зелёным. Оба указателя указывают на второй элемент. Стрелки показывают, что первый и второй элементы будут переставлены местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым, третий — зелёным. Оба указателя указывают на второй элемент. Первый и второй элементы поменяны местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

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

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

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

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

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

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены зелёным. Первый элемент правой части выделен синим. Левый указатель указывает на второй элемент правой части, правый — на последний.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены зелёным. Первый элемент правой части выделен синим. Оба указателя указывают на второй элемент правой части списка.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены зелёным. Первый элемент правой части выделен синим. Левый указатель указывает на первый элемент правой части, правый — на второй.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены зелёным, пятый и шестой — оранжевым.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены зелёным. Пятый элемент выделен синим. Оба указателя указывают на последний элемент.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены зелёным. Пятый элемент выделен синим. Оба указателя указывают на последний элемент. Стрелки показывают, что пятый и шестой элементы будут переставлены местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

Схематичное изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены зелёным. Пятый элемент выделен синим. Оба указателя указывают на последний элемент. Пятый и шестой элементы поменяны местами.

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — в действии

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

  • Разбиение Хоара
    • Двигаем левый указатель до значения, большего опорного
    • Двигаем правый указатель до значения, меньшего опорного
Структуры данных и алгоритмы на Python

Quicksort — реализация

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)
Структуры данных и алгоритмы на Python

Quicksort — реализация

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer
Структуры данных и алгоритмы на Python

Quicksort — реализация

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]
Структуры данных и алгоритмы на Python

Quicksort — сложность

  • Худший случай: $O(n^2)$
  • Очень эффективно!
    • Средний случай: $\Theta(n\log{}n)$
    • Лучший случай: $\Omega(n\log{}n)$
  • Пространственная сложность: $O(n\log{}n)$
Структуры данных и алгоритмы на Python

Давайте потренируемся!

Структуры данных и алгоритмы на Python

Preparing Video For Download...