Самый простой путь к пониманию быстрой сортировки🔥

Быстрая сортировка была алгоритмом, который я боялся изучать😢, думая, что это слишком сложно и требует слишком много времени для понимания, но теперь я объясняю вам, насколько это просто, используя небольшую статью, написанную для этого. Для полного понимания быстрой сортировки требуется простая рекурсивная функция.

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

Здесь я использую переменную pivotIndex для сравнения элемента по этому индексу с другими элементами, переменную swapIndex для отслеживания индекса, который будет поменян местами с маленьким элементом, найденным слева от поворотной точки, и переменную i для перебора всех элементов и определения текущего элемента, который мы сравниваем с поворотной точкой.

Первоначально swapIndex устанавливается на тот же индекс, что и pivotIndex. Каждый раз, когда находится элемент, меньший, чем поворотный, мы увеличиваем 1 к swapIndex и меняем элемент на swap index с текущим элементом, на котором мы находимся в цикле с i. После этого мы меняем поворотный элемент с элементом на swap index.

Функция Swap

function swapFn(array, firstIndex, secondIndex) {
    let temp = array[firstIndex]
    array[firstIndex] = array[secondIndex]
    array[secondIndex] = temp
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Ниже приведен алгоритм, который мы рекурсивно используем для сортировки элементов с помощью Quick sort.
Алгоритм быстрой сортировки
Шаг 1: Запуск
Шаг 2: Объявить переменные pivotIndex, swapIndex и i.
Шаг 3: Инициализируем переменные pivotIndex←0 swapIndex← pivotIndex, i= pivotIndex +1

Шаг 4: Повторять шаги до тех пор, пока i≤array.length-1
если массив[i] меньше, чем массив[pivotIndex], то
swapIndex++
swapFn(array[swap], array[i])
swapFn(array[swapIndex], array[pivotIndex])
Шаг 5: OUTPUT swapIndex
Шаг 6: Стоп

Индекс свопа, по которому будет выполняться функция свопирования поворотных точек

function pivotFn(array, pivotIndex=0, endIndex=array.length-1) { 
    let swapIndex = pivotIndex
    for (let i = pivotIndex + 1; i <= endIndex; i++) {
        if (array[i] < array[pivotIndex]) {
            swapIndex++
            swapFn(array, swapIndex, i)
        }
    }
    swapFn(array, pivotIndex, swapIndex)
    return swapIndex
}
Вход в полноэкранный режим Выход из полноэкранного режима

Следуйте этой схеме, чтобы увидеть, как это работает.

function quickSort(array, left=0, right=array.length-1) {
if(left < right) {
let pivotIndex = pivot(array, left, right)
quickSort(array, left, pivotIndex-1)
quickSort(array, pivotIndex+1, right)
}
return array
}

Протестируйте быструю сортировку, вызвав эту функцию: quickSort([4,6,1,7,3,2,5])

Подведем итог: у нас есть левая сторона с красным цветом и правая сторона с зеленым цветом. Мы выполняем одинаковый процесс для обеих сторон, сравнивая элементы с центральным элементом и меняя их местами, если элемент меньше центрального элемента, а затем меняем центральный элемент местами с индексом swap.

Оцените статью
devanswers.ru
Добавить комментарий