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

  1. Выбор опорного элемента (pivot):
    • Выбирается опорный элемент из списка. Обычно в качестве опорного элемента выбирается последний элемент списка.
fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high] // Опорный элемент
  1. Разделение списка на подсписки:
    • Создаются два подсписка: элементы, меньшие опорного элемента, и элементы, большие опорного элемента.
    • Перемещаем элементы так, чтобы все элементы меньше опорного оказались слева от него, а большие - справа.
    var i = low - 1
    for (j in low until high) {
        if (arr[j] < pivot) {
            i++
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
  1. Перемещение опорного элемента:
    • Помещаем опорный элемент после всех элементов, меньших него.
    val temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp
  1. Рекурсивная сортировка подсписков:
    • Рекурсивно вызываем алгоритм быстрой сортировки для подсписков до тех пор, пока подсписок не станет достаточно маленьким (обычно один элемент).
fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}
  1. Конец рекурсии:
    • Рекурсия завершается, когда подсписок содержит один элемент или пуст.

Пример сортировки массива с использованием быстрой сортировки на Kotlin:

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    quickSort(arr, 0, arr.size - 1)
    println("Отсортированный массив: ${arr.joinToString()}")
}

В результате выполнения алгоритма на входном массиве [64, 34, 25, 12, 22, 11, 90] мы получим [11, 12, 22, 25, 34, 64, 90].