Quicksort

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

Miriam Antona

Software engineer

Quicksort

  • Дотримується принципу divide and conquer
  • Реалізований у багатьох мовах програмування
  • Техніка partition
    • Pivot
    • елементи менші за pivot -> ліворуч
    • елементи більші за pivot -> праворуч
  • Елементи ліворуч сортуються рекурсивно
  • Елементи праворуч сортуються рекурсивно
Структури даних і алгоритми в Python

Quicksort — на практиці

Схема списку з невпорядкованими числами.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім.

  • Розбиття Гоара
Структури даних і алгоритми в Python

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Два вказівники: лівий на другий елемент, правий на останній.

  • Розбиття Гоара
    • Рухайте лівий вказівник, доки не знайдете значення більше за pivot
Структури даних і алгоритми в Python

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Два вказівники: лівий на третій елемент, правий на останній.

  • Розбиття Гоара
    • Рухайте лівий вказівник, доки не знайдете значення більше за pivot
Структури даних і алгоритми в Python

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Два вказівники: лівий на третій елемент, правий на п'ятий.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Два вказівники: лівий на третій, правий на п'ятий. Дві стрілки показують обмін третього і п'ятого елементів.

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

Quicksort — на практиці

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

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Два вказівники: лівий на четвертий, правий на п'ятий.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Два вказівники: обидва на четвертий елемент.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Лівий вказівник на четвертий елемент, правий — на третій.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент виділено синім. Лівий вказівник на четвертий, правий — на третій. Дві стрілки показують обмін першого і третього елементів.

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

Quicksort — на практиці

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

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Третій елемент виділено зеленим.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Третій елемент — зелений, перші два — помаранчеві (ліва частина списку).

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший — синій, другий — помаранчевий, третій — зелений. Обидва вказівники на другий елемент.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший — синій, другий — помаранчевий, третій — зелений. Обидва вказівники на другий елемент. Дві стрілки показують обмін першого і другого елементів.

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

Quicksort — на практиці

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

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший елемент — помаранчевий, другий і третій — зелені.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перший, другий і третій елементи — зелені.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші три елементи — зелені. Права частина списку — помаранчева.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші три елементи — зелені. Перший елемент правої частини — синій. Лівий вказівник на другий елемент правої частини, правий — на останній правої частини.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші три елементи — зелені. Перший елемент правої частини — синій. Обидва вказівники на другий елемент правої частини списку.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші три елементи — зелені. Перший елемент правої частини — синій. Лівий вказівник на перший елемент правої частини, правий — на другий.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші чотири елементи — зелені, п'ятий і шостий — помаранчеві.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші чотири елементи — зелені. Елемент виділено синім. Обидва вказівники на останній елемент.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші чотири елементи — зелені. Елемент виділено синім. Обидва вказівники на останній елемент. Дві стрілки показують обмін п'ятого і шостого елементів.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Перші чотири елементи — зелені. Елемент виділено синім. Обидва вказівники на останній елемент. П'ятий і шостий елементи вже обміняно.

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

Quicksort — на практиці

Схема списку з невпорядкованими числами. Усі елементи зелені, бо відсортовані.

  • Розбиття Гоара
    • Рухайте лівий вказівник, доки не знайдете значення більше за pivot
    • Рухайте правий вказівник, доки не знайдете значення менше за pivot
Структури даних і алгоритми в 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...