Быстрая сортировка (Quick Sort)

Основные идеи быстрой сортировки

  1. Выбор опорного элемента (pivot): Выбирается один элемент массива, который называется опорным (pivot). Это может быть первый элемент, последний элемент, случайный элемент или медиана.

  2. Разделение (partitioning): Массив реорганизуется так, чтобы все элементы, меньшие опорного, располагались перед ним, а все элементы, большие опорного, — после него. В итоге опорный элемент оказывается на своем окончательном месте в отсортированном массиве.

  3. Рекурсивная сортировка подмассивов: Алгоритм рекурсивно применяет те же операции к подмассивам, которые расположены до и после опорного элемента.

fun quickSort(nums: IntArray, low: Int = 0, high: Int = nums.size - 1) {
    if (low < high) {
        // Находим индекс опорного элемента так, что элементы меньше опорного слева от него,
        // а элементы больше опорного справа от него
        val pivotIndex = partition(nums, low, high)
        
        // Рекурсивно применяем быструю сортировку к подмассивам слева и справа от опорного элемента
        quickSort(nums, low, pivotIndex - 1)
        quickSort(nums, pivotIndex + 1, high)
    }
}

private fun partition(nums: IntArray, low: Int, high: Int): Int {
    val pivot = nums[high] // Выбираем опорный элемент (последний элемент массива)
    var i = low - 1 // Индекс меньшего элемента

    for (j in low until high) {
        if (nums[j] < pivot) {
            i++
            // Меняем местами nums[i] и nums[j]
            val temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
        }
    }
    
    // Меняем местами nums[i + 1] и nums[high] (или опорный элемент)
    val temp = nums[i + 1]
    nums[i + 1] = nums[high]
    nums[high] = temp
    
    return i + 1 // Возвращаем индекс опорного элемента
}

// Пример использования:
val nums = intArrayOf(4, 2, 7, 1, 9)
quickSort(nums)
println(nums.joinToString(", ")) // Вывод: 1, 2, 4, 7, 9

Детальный разбор

  1. Выбор опорного элемента: В данном примере опорным элементом выбран последний элемент массива nums[high]. Это простой, но не всегда лучший выбор, так как он может привести к худшему времени выполнения на уже отсортированных или почти отсортированных массивах.

  2. Разделение (partition):

    • Инициализация: Инициализируем i на один индекс меньше low, чтобы иметь возможность обменивать элементы.
    • Перебор элементов: Перебираем элементы от low до high - 1.
      • Если текущий элемент меньше опорного, увеличиваем i и меняем местами nums[i] и nums[j].
    • Размещение опорного элемента: После завершения перебора меняем местами nums[i + 1] и nums[high]. Опорный элемент оказывается на своем окончательном месте.

  3. Рекурсивная сортировка: Рекурсивно вызываем quickSort для подмассивов слева и справа от опорного элемента. Это продолжается до тех пор, пока подмассивы не станут длиной 1 или 0 (базовый случай рекурсии).

Пример с выбором опорного элемента посередине

fun quickSort(array: IntArray, start: Int = 0, end: Int = array.size - 1) {
    if (start < end) {
        // Разбиение массива и получение индекса опорного элемента
        val partitionIndex = partition(array, start, end)

        // Рекурсивно сортируем левую и правую части массива
        quickSort(array, start, partitionIndex - 1)
        quickSort(array, partitionIndex, end)
    }
}

fun partition(array: IntArray, start: Int, end: Int): Int {
    // Выбор опорного элемента как элемента в середине массива
    val pivot = array[(start + end) / 2]

    var leftPointer = start
    var rightPointer = end

    while (leftPointer <= rightPointer) {
        // Поиск элемента слева, который больше или равен pivot
        while (array[leftPointer] < pivot) {
            leftPointer++
        }
        // Поиск элемента справа, который меньше или равен pivot
        while (array[rightPointer] > pivot) {
            rightPointer--
        }
        if (leftPointer <= rightPointer) {
            // Обмен элементов местами
            array.swap(leftPointer, rightPointer)
            leftPointer++
            rightPointer--
        }
    }

    return leftPointer
}

// Вспомогательная функция для обмена элементов массива
fun IntArray.swap(index1: Int, index2: Int) {
    val temp = this[index1]
    this[index1] = this[index2]
    this[index2] = temp
}

Преимущества и недостатки быстрой сортировки

Преимущества:

  • Быстрота: В среднем случае имеет временную сложность O(n log n), что делает её очень быстрой для больших массивов.
  • Не требует дополнительной памяти: Работает на месте (in-place), используя только дополнительную память для стека вызовов при рекурсии.

Недостатки:

  • Худший случай: В худшем случае временная сложность O(n^2). Это может произойти, если опорные элементы выбираются неудачно, например, в уже отсортированном массиве при выборе первого или последнего элемента в качестве опорного.
  • Не стабильная: Стабильность означает, что два равных элемента остаются в том же порядке относительно друг друга после сортировки. Быстрая сортировка не является стабильной.

Оптимизация выбора опорного элемента

Для уменьшения вероятности попадания в худший случай часто используют различные стратегии выбора опорного элемента:

  • Случайный элемент: Выбор случайного элемента в качестве опорного.
  • Медиана трёх: Выбор медианы из первого, среднего и последнего элементов массива.

Пример использования медианы трёх в Kotlin:

private fun partition(nums: IntArray, low: Int, high: Int): Int {
    val mid = low + (high - low) / 2
    val pivot = medianOfThree(nums, low, mid, high)
    var i = low - 1

    for (j in low until high) {
        if (nums[j] < pivot) {
            i++
            nums.swap(i, j)
        }
    }

    nums.swap(i + 1, high)
    return i + 1
}

private fun medianOfThree(nums: IntArray, low: Int, mid: Int, high: Int): Int {
    if (nums[low] > nums[mid]) nums.swap(low, mid)
    if (nums[low] > nums[high]) nums.swap(low, high)
    if (nums[mid] > nums[high]) nums.swap(mid, high)
    nums.swap(mid, high)
    return nums[high]
}

private fun IntArray.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}