Быстрая сортировка, гномья сортировка, сортировка пузырьком. Реализация сортировок на Javascript. Сортировки на Javascript

February 3, 2019 00:52

Быстрая сортировка - это алгоритм сортировки, сложности O(nlog(n)). Алгоритм работы: выбирается опорный элемент, после чего все остальные элементы массива сравниваются с опорным; далее элементы переставляются так, чтобы получилось три массива (меньше опорного элемента, равные опорному элементу и больше опорного элемента); теперь для каждого из массивов, длиной больше единицы, нужно рекурсивно выполнить те же операции.

Сортировка пузырьком - простейший алгоритм сортировки, эффективен только для небольших массивов. Сложность O(n^2). Алгоритм: в цикле последовательно сравниваются пары элементов; если элемент А больше элемента Б - меняем их местами между собой; так продолжается до тех пор, пока число обменов не станет равно нулю.

Гномья сортировка - сортировка, схожая и с сортировкой вставками и с сортировкой пузырьком. Сложность O(n^2). Разница между этой сортировкой и сортировкой вставками - не используется дополнительная переменная для текущего элемента, а спускается, так сказать, пузырьком вниз, до первого элемента со значением меньше, чем у текущего (или больше, в случае сортировки убывания).

Пример работы программы (скриншот, нажать для увеличения):

Пример работы программы
Пример работы программы

Реализация на Javascript:

// bubble sort
const bubbleSort = (array) => {
    for (let i = 0, endI = array.length - 1; i < endI; i++) {
        let wasSwap = false
        for (let j = 0, endJ = endI - i; j < endJ; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1)
                wasSwap = true
            }
        }
        if (!wasSwap) break
    }
    return array
}

// quick sort
const quickSort = (array, left, right) => {
    let index
    if (array.length > 1) {
        index = partition(array, left, right)
        if (left < index - 1) {
            quickSort(array, left, index - 1)
        }
        if (index < right) {
            quickSort(array, index, right)
        }
    }
    return array
}

const partition = (array, left, right) => {
    let pivot = array[Math.floor((right + left) / 2)]
    let i = left
    let j = right

    while (i <= j) {
        while (array[i] < pivot) {
            i++
        }
        while (array[j] > pivot) {
            j--
        }
        if (i <= j) {
            swap(array, i, j)
            i++
            j--
        }
    }
    return i
}

// gnome sort
const gnomeSort = (array) => {
    let i = 0
    while (i < array.length) {
        if (i == 0 || array[i - 1] <= array[i]) {
            i++
        } else {
            swap(array, i, i - 1)
            i--
        }
    }
    return array
}

// utils
const swap = (array, index1, index2) => {
    let temp = array[index1]
    array[index1] = array[index2]
    array[index2] = temp
}

const getRandomInt = (min, max) => {
    min = Math.ceil(min)
    max = Math.floor(max)
    return Math.floor(Math.random() * (max - min + 1)) + min
}

const generateArray = (length, limit1, limit2) => {
    let array = []
    for (let f = 0; f < length; f++) {
        array[f] = getRandomInt(limit1, limit2)
    }
    return array
}

// main
let globalArray = generateArray(25, 0, 100)

console.log('Generated array: ' + JSON.stringify(globalArray))
console.log('    Bubble sort: ' + JSON.stringify(bubbleSort(globalArray)))
console.log('     Quick sort: ' + JSON.stringify(quickSort(globalArray, 0, globalArray.length - 1)))
console.log('     Gnome sort: ' + JSON.stringify(gnomeSort(globalArray)))