Сортировка

Сортировка пузырьком

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

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    var swapped: Boolean
    do {
        swapped = false
        for (i in 0 until n - 1) {
            if (arr[i] > arr[i + 1]) {
                val temp = arr[i]
                arr[i] = arr[i + 1]
                arr[i + 1] = temp
                swapped = true
            }
        }
    } while (swapped)
}

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

Сортировка вставками (Insertion Sort)

Описание: Этот алгоритм проходит по списку и на каждой итерации вставляет текущий элемент в подходящее место в отсортированной части списка.
Сложность: В среднем и в худшем случае время выполнения составляет O(n^2).
Применение: Этот алгоритм эффективен на небольших списках или уже частично отсортированных данных.

fun insertionSort(arr: IntArray) {
    val n = arr.size
    for (i in 1 until n) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

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

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

Описание: Этот алгоритм использует метод "разделяй и властвуй", разбивая список на две подгруппы, затем рекурсивно сортируя каждую подгруппу и объединяя их.
Сложность: В среднем время выполнения составляет O(n log n), в худшем случае - O(n^2).
Применение: Один из самых быстрых алгоритмов сортировки, который широко используется в реальных приложениях.

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)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    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
        }
    }
    val temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp
    return i + 1
}

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

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