Tree sort

Tree sort – сортировка двоичным деревом поиска. Временная сложность – O(n²). В таком дереве у каждой ноды слева числа меньше ноды, справа больше ноды, при приходе от корня и распечатке значений слева направо, получаем отсортированный список чисел. Удивительно да?

Рассмотрим схему двоичного дерева поиска:

Derrick Coetzee (public domain)

Попробуйте вручную прочитать числа начиная с предпоследней левой ноды нижнего левого угла, для каждой ноды слева – нода – справа.

Получится так:

  1. Предпоследняя нода слева внизу – 3.
  2. У нее есть левая ветвь – 1.
  3. Берем это число (1)
  4. Дальше берем саму вершину 3 (1, 3)
  5. Справа ветвь 6, но она содержит ветви. Поэтому ее прочитываем таким же образом.
  6. CЛева ветвь ноды 6 число 4 (1, 3, 4)
  7. Сама нода 6 (1, 3, 4, 6)
  8. Справа 7 (1, 3, 4, 6, 7)
  9. Идем наверх к корневой ноде – 8 (1,3, 4 ,6, 7, 8)
  10. Печатаем все что справа по аналогии
  11. Получаем итоговый список – 1, 3, 4, 6, 7, 8, 10, 13, 14

Чтобы реализовать алгоритм в коде потребуются две функции:

  1. Сборка бинарного дерева поиска
  2. Распечатка бинарного дерева поиска в правильно порядке

Собирают бинарное древо поиска также как и прочитывают, к каждой ноде прицепляется число слева или справа, в зависимости от того – меньше оно или больше.

Пример на Lua:

Node = {value = nil, lhs = nil, rhs = nil}

function Node:new(value, lhs, rhs)
    output = {}
    setmetatable(output, self)
    self.__index = self  
    output.value = value
    output.lhs = lhs
    output.rhs = rhs
    output.counter = 1
    return output  
end

function Node:Increment()
    self.counter = self.counter + 1
end

function Node:Insert(value)
    if self.lhs ~= nil and self.lhs.value > value then
        self.lhs:Insert(value)
        return
    end

    if self.rhs ~= nil and self.rhs.value < value then
        self.rhs:Insert(value)
        return
    end

    if self.value == value then
        self:Increment()
        return
    elseif self.value > value then
        if self.lhs == nil then
            self.lhs = Node:new(value, nil, nil)
        else
            self.lhs:Insert(value)
        end
        return
    else
        if self.rhs == nil then
            self.rhs = Node:new(value, nil, nil)
        else
            self.rhs:Insert(value)
        end
        return
    end
end

function Node:InOrder(output)
    if self.lhs ~= nil then
       output = self.lhs:InOrder(output)
    end
    output = self:printSelf(output)
    if self.rhs ~= nil then
        output = self.rhs:InOrder(output)
    end
    return output
end

function Node:printSelf(output)
    for i=0,self.counter-1 do
        output = output .. tostring(self.value) .. " "
    end
    return output
end

function PrintArray(numbers)
    output = ""
    for i=0,#numbers do
        output = output .. tostring(numbers[i]) .. " "
    end    
    print(output)
end

function Treesort(numbers)
    rootNode = Node:new(numbers[0], nil, nil)
    for i=1,#numbers do
        rootNode:Insert(numbers[i])
    end
    print(rootNode:InOrder(""))
end


numbersCount = 10
maxNumber = 9

numbers = {}

for i=0,numbersCount-1 do
    numbers[i] = math.random(0, maxNumber)
end

PrintArray(numbers)
Treesort(numbers)

Важный нюанс что для чисел которые равны вершине придумано множество интересных механизмов подцепления к ноде, я же просто добавил счетчик к классу вершины, при распечатке числа возвращаются по счетчику.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/treesort

Источники

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube

Bucket Sort

Bucket Sort – сортировка ведрами. Алгоритм похож на сортировку подсчетом, с той разницей что числа собираются в «ведра»-диапазоны, затем ведра сортируются с помощью любого другого, достаточно производительного, алгоритма сортировки, и финальным аккордом делается разворачивание «ведер» поочередно, в результате чего получается отсортированный список.

Временная сложность алгоритма O(nk). Алгоритм работает за линейное время для данных которые подчиняются равномерному закону распределения. Если говорить проще, то элементы должны быть в каком-то определенном диапазоне, без «вспесков», например числа от 0.0 до 1.0. Если среди таких чисел есть 4 или 999, то такой ряд по дворовым законам «ровным» уже не считается.

Пример реализации на Julia:

function bucketSort(numbers, bucketsCount)
    buckets = Vector{Vector{Int}}()
    
    for i in 0:bucketsCount - 1
        bucket = Vector{Int}()
        push!(buckets, bucket)
    end

    maxNumber = maximum(numbers)

    for i in 0:length(numbers) - 1
        bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
        push!(buckets[bucketIndex], numbers[1 + i])
    end

    for i in 0:length(buckets) - 1
        bucketIndex = 1 + i
        buckets[bucketIndex] = sort(buckets[bucketIndex])
    end

    flat = [(buckets...)...]
    print(flat, "\n")

end

numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)

На производительность алгоритма также влияет число ведер, для большего количества чисел лучше взять большее число ведер (Algorithms in a nutshell by George T. Heineman)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort

Источники

https://www.youtube.com/watch?v=VuXbEb5ywrU
https://www.youtube.com/watch?v=ELrhrrCjDOA
https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124
https://www.geeksforgeeks.org/bucket-sort-2/
https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.youtube.com/watch?v=LPrF9yEKTks
https://en.wikipedia.org/wiki/Bucket_sort
https://julialang.org/
https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

Radixsort

Radix Sort – поразрядная сортировка. Алгоритм схож с сортировкой подсчетом тем, что отсутствует сравнение элементов, вместо этого элементы *посимвольно* группируются в *ведра* (buckets), ведро выбирается по индексу текущего числа-символа. Временная сложность – O(nd).

Работает примерно так:

  • На вход получим числа 6, 12, 44, 9
  • Создадим 10 ведер списков (0-9), в которые будем поразрядно складывать/сортировать числа.

Далее:

  1. Запускаем цикл со счетчиком i до максимального количества символов в числе
  2. По индексу i справа налево получаем один символ для каждого числа, если символа нет, то считаем что это ноль
  3. Символ преобразовываем в число
  4. Выбираем ведро по индексу – числу, кладем туда число полностью
  5. После окончания перебора чисел, преобразовываем все ведра назад в список чисел
  6. Получаем числа отсортированные по разряду
  7. Повторяем пока не кончатся все разряды

Пример Radix Sort на Scala:

import scala.collection.mutable.ListBuffer
import scala.util.Random.nextInt

object RadixSort {
    def main(args: Array[String]) = {
        var maxNumber = 200
        var numbersCount = 30
        var maxLength = maxNumber.toString.length() - 1

        var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList
        var numbers = referenceNumbers
        
        var buckets = List.fill(10)(ListBuffer[Int]())

        for( i <- 0 to maxLength) { numbers.foreach( number => {
                    var numberString = number.toString
                    if (numberString.length() > i) {
                        var index = numberString.length() - i - 1
                        var character = numberString.charAt(index).toString
                        var characterInteger = character.toInt  
                        buckets.apply(characterInteger) += number
                    }
                    else {
                        buckets.apply(0) += number
                    }
                }
            )
            numbers = buckets.flatten
            buckets.foreach(x => x.clear())
        }
        println(referenceNumbers)
        println(numbers)
        println(s"Validation result: ${numbers == referenceNumbers.sorted}")
    }
}

Алгоритм также имеет версию для параллельного выполнения, например на GPU; также существует вариант битовой сортировки, что наверное, очень интересно и поистине захватывает дух!

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala

Источники

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.geeksforgeeks.org/radix-sort/
https://www.youtube.com/watch?v=toAlAJKojos
https://github.com/gyatskov/radix-sort

Heapsort

Heapsort – пирамидальная сортировка. Временная сложность алгоритма – O(n log n), шустрый да? Я бы назвал эту сортировку – сортировкой падающих камушков. Объяснять её, как мне кажется, проще всего визуально.

На вход подается список цифр, например:
5, 0, 7, 2, 3, 9, 4

Слева направо делается структура данных – двоичное дерево, или как я ее называю – пирамидка. У элементов пирамидки могут быть максимум два дочерних элемента, со-но всего один верхний элемент.

Сделаем двоичное дерево:
⠀⠀5
⠀0⠀7
2 3 9 4

Если долго смотреть на пирамидку, то можно увидеть что это просто числа из массива, идущие друг за другом, количество элементов в каждом этаже умножается на два.

Далее начинается самое интересное, отсортируем пирамидку снизу вверх, методом падающих камушков (heapify). Сортировку можно было бы начинать с последнего этажа (2 3 9 4 ), но смысла нет т.к. нет этажа ниже, куда можно было бы упасть.

Поэтому начинаем ронять элементы с предпоследнего этажа (0 7)
⠀⠀5
⠀0⠀7
2 3 9 4

Первый элемент для падения выбирается справа, нашем случае это 7, далее смотрим что под ним, а под ним 9 и 4, девятка больше четверки, так еще и девятка больше семерки! Роняем 7 на 9, а 9 поднимаем на место 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Далее понимаем что семерке падать ниже некуда, переходим к числу 0 которое находится на предпоследнем этаже слева:
⠀⠀5
0⠀9
2 3 7 4

Смотрим что под ним – 2 и 3, два меньше трех, три больше нуля, поэтому меняем ноль и три местами:
⠀⠀5
⠀3⠀9
2 0 7 4

Когда добрались до конца этажа – переходите на этаж выше и роняйте там всё, если сможете.
В итоге получится структура данных – куча (heap), а именно max heap, т.к. наверху самый большой элемент:
⠀⠀9
⠀3⠀7
2 0 5 4

Если вернуть в представление массива, то получится список:
[9, 3, 7, 2, 0, 5, 4]

Из этого можно сделать вывод, что поменяв местами первый и последний элемент, мы получим первое число в окончательной отсортированной позиции, а именно 9 должна стоять в конце отсортированного списка, меняем местами:
[4, 3, 7, 2, 0, 5, 9]

Посмотрим на бинарное дерево:
⠀⠀4
⠀3⠀7
2 0 5 9

Получилась ситуация при которой нижняя часть древа отсортирована, нужно лишь уронить 4 до корректной позиции, повторяем алгоритм, но не учитываем уже отсортированные числа, а именно 9:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Получилось что мы, уронив 4, подняли следующее после 9 самое больше число – 7. Меняем местами последнее неотсортированное число (4) и самое больше число (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Получилось что теперь мы имеем два числа в корректной окончательной позиции:
4, 3, 5, 2, 0, 7, 9

Далее повторяем алгоритм сортировки, игнорируя уже отсортированные, в итоге получим кучу вида:
⠀⠀0
⠀2⠀3
4 5 7 9

Или в виде списка:
0, 2, 3, 4, 5, 7, 9

Реализация

Алгоритм обычно разделяют на три функции:

  1. Создание кучи
  2. Алгоритм просеивания (heapify)
  3. Замена последнего неотсортированного элемента и первого

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

Пример Heapsort на Ruby:

DEMO = true

module Colors
    BLUE = "\033[94m"
    RED = "\033[31m"
    STOP = "\033[0m"
end

def heapsort(rawNumbers)
    numbers = rawNumbers.dup

    def swap(numbers, from, to)
        temp = numbers[from]
        numbers[from] = numbers[to]
        numbers[to] = temp
    end

    def heapify(numbers)
        count = numbers.length()
        lastParentNode = (count - 2) / 2

        for start in lastParentNode.downto(0)
            siftDown(numbers, start, count - 1)
            start -= 1 
        end

        if DEMO
            puts "--- heapify ends ---"
        end
    end

    def siftDown(numbers, start, rightBound)      
        cursor = start
        printBinaryHeap(numbers, cursor, rightBound)

        def calculateLhsChildIndex(cursor)
            return cursor * 2 + 1
        end

        def calculateRhsChildIndex(cursor)
            return cursor * 2 + 2
        end            

        while calculateLhsChildIndex(cursor) <= rightBound
            lhsChildIndex = calculateLhsChildIndex(cursor)
            rhsChildIndex = calculateRhsChildIndex(cursor)

            lhsNumber = numbers[lhsChildIndex]
            biggerChildIndex = lhsChildIndex

            if rhsChildIndex <= rightBound
                rhsNumber = numbers[rhsChildIndex]
                if lhsNumber < rhsNumber
                    biggerChildIndex = rhsChildIndex
                end
            end

            if numbers[cursor] < numbers[biggerChildIndex]
                swap(numbers, cursor, biggerChildIndex)
                cursor = biggerChildIndex
            else
                break
            end
            printBinaryHeap(numbers, cursor, rightBound)
        end
        printBinaryHeap(numbers, cursor, rightBound)
    end

    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)
        if DEMO == false
            return
        end
        perLineWidth = (numbers.length() * 4).to_i
        linesCount = Math.log2(numbers.length()).ceil()
        xPrinterCount = 1
        cursor = 0
        spacing = 3
        for y in (0..linesCount)
            line = perLineWidth.times.map { " " }
            spacing = spacing == 3 ? 4 : 3
            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2
            for x in (0..xPrinterCount - 1)
                if cursor >= numbers.length
                    break
                end
                if nodeIndex != -1 && cursor == nodeIndex
                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]
                elsif rightBound != -1 && cursor > rightBound
                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]
                else
                    line[printIndex] = numbers[cursor].to_s
                end
                cursor += 1
                printIndex += spacing
            end
            print line.join()
            xPrinterCount *= 2           
            print "\n"            
        end
    end

    heapify(numbers)
    rightBound = numbers.length() - 1

    while rightBound > 0
        swap(numbers, 0, rightBound)   
        rightBound -= 1
        siftDown(numbers, 0, rightBound)     
    end

    return numbers
end

numbersCount = 14
maximalNumber = 10
numbers = numbersCount.times.map { Random.rand(maximalNumber) }
print numbers
print "\n---\n"

start = Time.now
sortedNumbers = heapsort(numbers)
finish = Time.now
heapSortTime = start - finish

start = Time.now
referenceSortedNumbers = numbers.sort()
finish = Time.now
referenceSortTime = start - finish

print "Reference sort: "
print referenceSortedNumbers
print "\n"
print "Reference sort time: %f\n" % referenceSortTime
print "Heap sort:      "
print sortedNumbers
print "\n"
if DEMO == false
    print "Heap sort time:      %f\n" % heapSortTime
else
    print "Disable DEMO for performance measure\n"
end

if sortedNumbers != referenceSortedNumbers
    puts "Validation failed"
    exit 1
else
    puts "Validation success"
    exit 0
end

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

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/heapsort/heapsort.rb

Источники

http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
https://www.youtube.com/watch?v=LbB357_RwlY
https://habr.com/ru/company/otus/blog/460087/
https://ru.wikipedia.org/wiki/Пирамидальная_сортировка
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_кучей
https://wiki5.ru/wiki/Heapsort
https://wiki.c2.com/?HeapSort
https://ru.wikipedia.org/wiki/Дерево (структура данных)
https://ru.wikipedia.org/wiki/Куча (структура данных)
https://www.youtube.com/watch?v=2DmK_H7IdTo
https://www.youtube.com/watch?v=kU4KBD4NFtw
https://www.youtube.com/watch?v=DU1uG5310x0
https://www.youtube.com/watch?v=BzQGPA_v-vc
https://www.geeksforgeeks.org/array-representation-of-binary-heap/
https://habr.com/ru/post/112222/
https://www.cs.usfca.edu/~galles/visualization/BST.html
https://www.youtube.com/watch?v=EQzqHWtsKq4
https://medium.com/@dimko1/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-heapsort-796ba965018b
https://ru.wikibrief.org/wiki/Heapsort
https://www.youtube.com/watch?v=GUUpmrTnNbw

Quicksort

Quicksort – алгоритм сортировки по методу «разделяй и влавствуй». Рекурсивно, по частям разбираем массив чисел, выставляя числа в меньшем и большем порядке от выбранного опорного элемента, сам опорный элемент вставляем в отсечку между ними. После нескольких рекурсивных итераций получится отсортированный список. Временная сложность O(n2).

Схема:

  1. Начинаем с того что получаем снаружи список элементов, границы сортировки. На первом шаге границы сортировки будут от начала до конца.
  2. Проверяем что границы начала и конца не пересекаются, если это произошло, значит пора заканчивать
  3. Выбираем какой-то элемент из списка, называем его опорным
  4. Сдвигаем вправо в конец на последний индекс, чтобы не мешался
  5. Создаем счетчик *меньших чисел* пока равный нулю
  6. Проходим циклом по списку слева направо, до последнего индекса, где находится опорный элемент, не включительно
  7. Каждый элемент сравниваем с опорным
  8. Если он меньше опорного, то меняем его местами по индексу счетчика меньших чисел. Инкрементируем счетчик меньших чисел.
  9. Когда цикл дойдет до опорного элемента, останавливаемся, меняем местами опорный элемент с элементом по счетчику меньших чисел.
  10. Запускаем отдельно алгоритм для левой меньшей части списка, и отдельно для правой большей части списка.
  11. В итоге все рекурсивные итерации начнут останавливаться из-за проверки в пункте 2
  12. Получим отсортированный список

Quicksort был придуман ученым Чарльзом Энтони Ричардом Хоаром в МГУ, выучив русский язык, он занимался изучением компьютерного перевода, а также теории вероятностей в школе Колмогорова. В 1960 г. из-за политического кризиса, он покинул Советский Союз.

Пример реализации на Rust:

extern crate rand;

use rand::Rng;

fn swap(numbers: &mut [i64], from: usize, to: usize) {
    let temp = numbers[from];
    numbers[from] = numbers[to];
    numbers[to] = temp;
}

fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
    if left >= right {
        return
    }
    let length = right - left;
    if length <= 1 {
        return
    }
    let pivot_index = left + (length / 2);
    let pivot = numbers[pivot_index];

    let last_index = right - 1;
    swap(numbers, pivot_index, last_index);

    let mut less_insert_index = left;

    for i in left..last_index {
        if numbers[i] < pivot {
            swap(numbers, i, less_insert_index);
            less_insert_index += 1;
        }
    }
    swap(numbers, last_index, less_insert_index);
    quicksort(numbers, left, less_insert_index);
    quicksort(numbers, less_insert_index + 1, right);
}

fn main() {
    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    let mut rng = rand::thread_rng();
    for i in 0..numbers.len() {
        numbers[i] = rng.gen_range(-10..10);
        reference_numbers[i] = numbers[i];
    }

    reference_numbers.sort();

  println!("Numbers           {:?}", numbers);
  let length = numbers.len();
  quicksort(&mut numbers, 0, length);
  println!("Numbers           {:?}", numbers);
  println!("Reference numbers {:?}", reference_numbers);

  if numbers != reference_numbers {
    println!("Validation failed");
    std::process::exit(1);
  }
  else {
    println!("Validation success!");
    std::process::exit(0);
  }
}

Если ничего непонятно, то предлагаю посмотреть видео Роба Эдвардса из университета Сан-Диего https://www.youtube.com/watch?v=ZHVk2blR45Q в нем наиболее просто, по шагам, показывается суть и реализация алгоритма.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/quickSort

Источники

https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=ywWBy6J5gz8
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://ru.wikipedia.org/wiki/Быстрая_сортировка
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=XE4VP_8Y0BU
https://www.youtube.com/watch?v=MZaf_9IZCrc
https://www.youtube.com/watch?v=ZHVk2blR45Q
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=dQw4w9WgXcQ
https://www.youtube.com/watch?v=maibrCbZWKw
https://www.geeksforgeeks.org/quick-sort/
https://www.youtube.com/watch?v=uXBnyYuwPe8

Binary Insertion Sort

Binary Insertion Sort – вариант сортировки вставками, в котором позицию для вставки определяют с помощью двоичного поиска. Временная сложность алгоритма O(n2)

Алгоритм работает так:

  1. Запускается цикл от нуля до конца списка
  2. В цикле выбирается число для сортировки, число сохраняется в отдельную переменную
  3. Бинарным поиском ищется индекс для вставки этого числа по сравнению с числами слева
  4. После нахождения индекса, числа слева сдвигаются на одну позицию вправо, начиная с индекса вставки. В процессе будет стерто число которое нужно отсортировать.
  5. Сохраненное ранее число вставляется по индексу вставки
  6. По окончанию цикла весь список будет отсортирован

Во время выполнения бинарного поиска, возможна ситуация когда число не будет найдено, со-но не возвращен индекс. Из-за особенности работы бинарного поиска, будет найдено число наиболее близкое к искомому, тогда для возврата индекса нужно будет сравнить его с искомым, если искомое меньше, то искомое должно быть по индексу слева, а если больше или равно то справа.

Код на Go:

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

	for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
	}
	fmt.Println(numbers)
}

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

Источники

https://www.geeksforgeeks.org/binary-insertion-sort/
https://www.youtube.com/watch?v=-OVB5pOZJug

Shell Sort

Shell Sort – вариант сортировки вставками с предварительным причесыванием массива чисел.

Надо вспомнить как работает сортировка вставками:

1. Запускается цикл от нуля до конца цикла, таким образом массив разделяется на две части
2. Для левой части запускается второй цикл, сравнение элементов справа налево, меньший элемент справа опускается пока не найдется меньший элемент слева
3. По окончанию обоих циклов, получим отсортированный список

Однажды во времени, информатик Дональд Шелл озадачился как улучшить алгоритм сортировки вставками. Он придумал предварительно проходить также двумя циклами по массиву, но на определенном расстоянии, постепенно уменьшая «расческу» пока она не превратиться в обычный алгоритм сортировки вставками. Всё действительно настолько просто, никаких подводных камней, к двум циклам сверху добавляем еще один, в котором уменьшаем постепенно размер «расчески». Единственное что нужно будет делать – проверять расстояние при сравнении, чтобы оно не вышло за пределы массива.

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

Таблицу известных вариантов и временную сложность можно посмотреть здесь: https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

Вычислением идеальной дистанции занимались разные люди, настолько, видимо, была им эта тема интересна. Неужели они не могли просто запустить Ruby, вызвать самый быстрый алгоритм sort()?

В общем эти странные люди писали диссертации на тему вычисления дистанции/зазора «расчески» для алгоритма Шелла. Я же просто воспользовался результатами их труда и проверил 5 типов последовательностей, Хиббарда, Кнута-Пратта, Чиуры, Седжвика.

from typing import List
import time
import random
from functools import reduce
import math

DEMO_MODE = False

if input("Demo Mode Y/N? ").upper() == "Y":
    DEMO_MODE = True

class Colors:
    BLUE = '\033[94m'
    RED = '\033[31m'
    END = '\033[0m'

def swap(list, lhs, rhs):
    list[lhs], list[rhs] = list[rhs], list[lhs]
    return list

def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
    for index, number in enumerate(numbers):
        if index == lhs:
            print(f"{Colors.BLUE}", end = "")
        elif index == rhs:
            print(f"{Colors.RED}", end = "")
        print(f"{number},", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
    print("\n")
    input(">")

def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
    distanceSequenceIterator = reversed(distanceSequence)
    while distance:= next(distanceSequenceIterator, None):
        for sortArea in range(0, len(numbers)):
            for rhs in reversed(range(distance, sortArea + 1)):
                lhs = rhs - distance
                if DEMO_MODE:
                    print(f"Distance: {distance}")
                    colorPrintoutStep(numbers, lhs, rhs)
                if numbers[lhs] > numbers[rhs]:
                    swap(numbers, lhs, rhs)
                else:
                    break

def ShellSort(numbers: List[int]):
    global ShellSequence
    ShellSortLoop(numbers, ShellSequence)

def HibbardSort(numbers: List[int]):
    global HibbardSequence
    ShellSortLoop(numbers, HibbardSequence)

def ShellPlusKnuttPrattSort(numbers: List[int]):
    global KnuttPrattSequence
    ShellSortLoop(numbers, KnuttPrattSequence)

def ShellPlusCiuraSort(numbers: List[int]):
    global CiuraSequence
    ShellSortLoop(numbers, CiuraSequence)

def ShellPlusSedgewickSort(numbers: List[int]):
    global SedgewickSequence
    ShellSortLoop(numbers, SedgewickSequence)

def insertionSort(numbers: List[int]):
    global insertionSortDistanceSequence
    ShellSortLoop(numbers, insertionSortDistanceSequence)

def defaultSort(numbers: List[int]):
    numbers.sort()

def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
    if DEMO_MODE:
        print(f"{algorithmName} started")
    numbers = inputNumbers.copy()
    startTime = time.perf_counter()
    algorithm(numbers)
    endTime = time.perf_counter()
    print(f"{algorithmName} performance: {endTime - startTime}")

def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
    numbers = inputNumbers.copy()
    algorithm(numbers)
    return str(numbers)

if DEMO_MODE:
    maximalNumber = 10
    numbersCount = 10
else:
    maximalNumber = 10
    numbersCount = random.randint(10000, 20000)

randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]

ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()

HibbardSequence = [
    0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
    8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
    2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
    268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]

KnuttPrattSequence = [
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 
    797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 
    1743392200, 5230176601, 15690529804, 47071589413
]

CiuraSequence = [
            1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 
            10941, 27353, 68383, 170958, 427396, 1068491, 
            2671228, 6678071, 16695178, 41737946, 104344866, 
            260862166, 652155416, 1630388541
]

SedgewickSequence = [
            1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
            8929, 16001, 36289, 64769, 146305, 260609, 587521, 
            1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 
            67084289, 150958081, 268386305, 603906049, 1073643521, 
            2415771649, 4294770689, 9663381505, 17179475969
]

insertionSortDistanceSequence = [1]

algorithms = {
    "Default Python Sort": defaultSort,
    "Shell Sort": ShellSort,
    "Shell + Hibbard" : HibbardSort,
    "Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
    "Shell + Ciura Sort": ShellPlusCiuraSort,
    "Shell + Sedgewick Sort": ShellPlusSedgewickSort,
    "Insertion Sort": insertionSort
}

for name, algorithm in algorithms.items():
    measureExecution(randomNumbers, name, algorithm)

reference = sortedNumbersAsString(randomNumbers, defaultSort)

for name, algorithm in algorithms.items():
    if sortedNumbersAsString(randomNumbers, algorithm) != reference:
        print("Sorting validation failed")
        exit(1)

print("Sorting validation success")
exit(0)

В моей реализации, для случайного набора числем самыми быстрыми оказываются зазоры Седжвика и Хиббарда.

mypy

Также хочется упомянуть анализатор статической типизации для Python 3 – mypy. Помогает справиться с проблемами присущими языкам с динамической типизацией, а именно устраняет возможность просунуть что-то куда не надо.

Как говорят опытные программисты “статическая типизация не нужна, когда у тебя есть команда профессионалов”, когда-нибудь мы все станем профессионалами, будем писать код в полном единении и понимании с машинами, а пока можно пользоваться подобными утилитами и языками со статической типизацией.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/

Источники

https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216

Double Selection Sort

Double Selection Sort – подвид сортировки выбором, вроде как должен ускоряться в два раза. Ванильный алгоритм проходит двойным циклом по списку чисел, находит минимальное число и меняет местами с текущей цифрой на которую указывает цикл на уровне выше. Двойная сортировка выбором же ищет минимальное и максимальное число, далее происходит замена двух цифр, на которые указывает цикл на уровне выше – два числа слева и справа. Заканчивается вся эта вакханалия когда курсоры чисел для замены встречаются в середине списка, по итогу слева и справа от визуального центра получаются отсортированные числа.
Временная сложность алгоритма аналогична Selection Sort – O(n2), но якобы есть ускорение на 30%.

Пограничное состояние

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

if (leftCursor == maximalNumberIndex) {
  maximalNumberIndex = minimalNumberIndex;
}

Реализация на Cito

Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:

public class DoubleSelectionSort
{
    public static int[] sort(int[]# numbers, int length)
    {
        int[]# sortedNumbers = new int[length];
        for (int i = 0; i < length; i++) {
            sortedNumbers[i] = numbers[i];
        }
        for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
            int minimalNumberIndex = leftCursor;
            int minimalNumber = sortedNumbers[leftCursor];

            int rightCursor = length - (leftCursor + 1);
            int maximalNumberIndex = rightCursor;
            int maximalNumber = sortedNumbers[maximalNumberIndex];

            for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
                    minimalNumber = cursorNumber;
                    minimalNumberIndex = cursor;
                }
                if (maximalNumber < cursorNumber) {
                    maximalNumber = cursorNumber;
                    maximalNumberIndex = cursor;
                }
            }

            if (leftCursor == maximalNumberIndex) {
                maximalNumberIndex = minimalNumberIndex;
            }

            int fromNumber = sortedNumbers[leftCursor];
            int toNumber = sortedNumbers[minimalNumberIndex];
            sortedNumbers[minimalNumberIndex] = fromNumber;
            sortedNumbers[leftCursor] = toNumber;

            fromNumber = sortedNumbers[rightCursor];
            toNumber = sortedNumbers[maximalNumberIndex];
            sortedNumbers[maximalNumberIndex] = fromNumber;
            sortedNumbers[rightCursor] = toNumber;
        }
        return sortedNumbers;
    }
} 

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito

Источники

https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/