n - размер отсортированного массива, а k - размер вспомогательного массива
Блочная (карманная, корзинная) сортировка / Bucket sort Блочная сортировка - это алгоритм, основанный на разделении входного массива на несколько частей - блоки/сегменты - и использовании другого алгоритма для их сортировки.
Общая идея алгоритма:
Делим массив на блоки таким образом, чтобы элементы в каждом следующем блоке были всегда больше, чем в предыдущем.
Сортируем каждый блок, используя какой-либо другой алгоритм сортировки, либо рекурсивно тем же методом разбиения на блоки.
Объединяем все блоки в один массив.
Пример реализации на Kotlin: fun insertion_sort(arr: ArrayList) {
var n = arr.size
var i: Int
for (j in 1 until n) {
var key = arr[j]
i = j - 1
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i]
i--
}
arr[i + 1] = key
}
}
fun bucketSort(arr:Array) {
var n = arr.size
var bucket = Array>(n, {i-> ArrayList() } )
