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

Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.

Виды алгоритмов сортировки

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

wiki

Сортировка пузырьком — это простейший и один из самых известных алгоритмов сортировки. Идея заключается в последовательном сравнении значений соседних элементов. Если текущий элемент больше следующего, меняем их местами. Алгоритм необходимо повторять до тех пор, пока массив не будет отсортирован.

Плюсы и минусы

Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

private fun bubbleSort(array: IntArray) {
    if (array.isEmpty()) return

        var swap = true
        while (swap) {
            swap = false
            for (i in 1 until array.size) {
                if (array[i] < array[i - 1]) {
                    val temp = array[i - 1]
                    array[i - 1] = array[i]
                    array[i] = temp
                    swap = true
                }
            }
        }
}

Сортировка перемешиванием / Shaker (cocktail, ripple, shuffle, shuttle) sort

wiki

Также известна как шейкерная или коктейльная сортировка.

Сортировка перемешиванием - это разновидность сортировки пузырьком. Отличие в том, что данная сортировка в рамках одной итерации проходит по массиву в обоих направлениях (слева направо и справа налево), тогда как сортировка пузырьком - только в одном направлении (слева направо).

Общая идея алгоритма:

• Обход массива слева направо, аналогично пузырьковой - сравнение соседних элементов, меняя их местами, если левое значение больше правого. В итоге наибольшее число будет перемещено в конец массива.
• Обход массива в обратном направлении (справа налево), начиная с элемента, который находится перед последним отсортированным. На этом этапе элементы также сравниваются между собой и меняются местами, чтобы наименьшее значение всегда было слева. В итоге наименьшее число будет перемещено в начало массива.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

fun cocktailSort(a: IntArray) {
    fun swap(i: Int, j: Int) {
        val temp = a[i]
        a[i] = a[j]
        a[j] = temp
    }
    do {
        var swapped = false
        for (i in 0 until a.size - 1)
            if (a[i] > a[i + 1]) {
                swap(i, i + 1)
                swapped = true
            }
        if (!swapped) break
        swapped = false
        for (i in a.size - 2 downTo 0)
            if (a[i] > a[i + 1]) {
                swap(i, i + 1)
                swapped = true
            }
    } while (swapped)
}

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

Сортировка расчёской / Comb sort

wiki

Сортировка расчёской - еще одна разновидность сортировки пузырьком. Данная сортировка улучшает сортировку пузырьком за счет устранения маленьких значений в конце списка (черепах).

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

Оптимальное значение фактора уменьшения - 1,247.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

fun combSort(input: Array<Int>) {
    var gap = input.size
    if (gap <= 1) return  // если массив <= 1, то он считается отсортированным
    var swaps = false
    while (gap > 1 || swaps) {
        gap = (gap / 1.247331).toInt()
        if (gap < 1) gap = 1
        var i = 0
        swaps = false
        while (i + gap < input.size) {
            if (input[i] > input[i + gap]) {
                val tmp = input[i]
                input[i] = input[i + gap]
                input[i + gap] = tmp
                swaps = true
            }
            i++
        }
    }
}

Сортировка вставками / Insertion sort

wiki

Сортировка вставками - алгоритм, при котором каждый последующий элемент массива сравнивается с предыдущими элементами (отсортированными) и вставляется в нужную позицию.

Общая идея алгоритма:

• Сравниваем второй элемент с первым элементом массива и при необходимости меняем их местами. Условно эти элементы (первый и второй) будут являться отсортированным массивом, остальные элементы - неотсортированным.
• Сравниваем следующий элемент из неотсортированного массива с элементами отсортированного и вставляем в нужную позицию.
• Повторям шаг 2 до тех пор, пока в неотсортированном массиве не останется элементов.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fun insertionsort(items:MutableList<Int>): List<Int> {
    if (items.isEmpty() || items.size < 2){
        return items
    }

    for (count in 1..items.count() - 1) {
        val item = items[count]
        var i = count
        while (i > 0 && item < items[i - 1]) {
            items[i] = items[i - 1]
            i -= 1
        }
        items[i] = item
    }
    return items
}

Сортировка Шелла / Shell sort

wiki

Сортировка Шелла - усовершенствованная разновидность сортировки вставками.

Сначала сравниваются и сортируются между собой значения, стоящие друг от друга на некотором расстоянии - d. После этого расстояние d уменьшается и процедура повторяется до тех пор, пока значение d не станет минимальным, т.е. d = 1. Это означает, что сортировка достигла последнего шага. А на последнем шага элементы сортируются обычной сортировкой вставками.

Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:

• первая итерация - d₁ = N/2, где N - размер массива;
• последующие итерации - d_i = d_i-1/2;
• последняя итерация - d_k = 1

Существуют и другие последовательности.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

fun sort(arr: IntArray): Int {
    val n = arr.size
    var gap = n / 2
    while (gap > 0) {
        var i = gap
        while (i < n) {
            val temp = arr[i]
            var j = i
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
            i += 1
        }
        gap /= 2
    }
    return 0
}

Сортировка выбором / Selection Sort

wiki

Сортировка выбором - это алгоритм, при котором многократно осуществляется поиск минимального элемента в неотсортированной части массива и его помещение в конец отсортированной части массива.

Общая идея алгоритма:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fun selectionSort(sampleArray: IntArray) {
    var n = sampleArray.size
    var temp: Int
    for(i in 0..n-1) {
        var indexOfMin = i
        for(j in n-1 downTo  i) {
            if (sampleArray[j] < sampleArray[indexOfMin])
                indexOfMin=j
        }
        if (i != indexOfMin) {
            temp = sampleArray[i]
            sampleArray[i] = sampleArray[indexOfMin]
            sampleArray[indexOfMin] = temp
        }
    }
}

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

wiki

Быстрая сортировка - это алгоритм типа “разделяй и властвуй”.

Общая идея алгоритма:

• Выбрать из массива элемент, который обычно называют опорным. Это может быть любой элемент из массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
• Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
• Рекурсивно применить первые два шага к отрезкам, содержащим «меньшие» и «большие» значения. Не применять к массиву, в котором только один элемент или отсутствуют элементы.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

fun quicksort(items: List<Int>): List<Int> {
    // если в массиве меньше 2х элементов, то он уже отсортирован
    if (items.count() < 2) {
        return items
    }

    // выбираем опорный элемент
    val pivot = items[items.count()/2]

    // сортируем элементы по 3м массивам - меньшие, равные и большие опорного
    val equal = items.filter { it == pivot }
    val less = items.filter { it < pivot }
    val greater = items.filter { it > pivot }

    // рекурсивно вызываем функцию для меньших и больших элементов
    return quicksort(less) + equal + quicksort(greater)
}

Сортировка слиянием / Merge sort

wiki

Сортировка слиянием - это алгоритм типа “разделяй и властвуй”.

Общая идея алгоритма:

• Массив разбивается на две части примерно одинакового размера. Разбиение получившихся массивов повторяется до тех пор, пока размер каждого массива не достигнет единицы.
• Каждая из получившихся частей сортируется отдельно, после чего происходит слияние двух массивов следующим образом:
  • На каждом шаге сравниваем первые элементы массивов, берём наименьшее значение и записываем в результирующий массив.
  • Когда один из массив закончился, добавляем оставшиеся элементы второго массива в результирующий массив.
• Слияние подмассивов продолжается до тех пор, пока не получим один, отсортированный массив.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

fun mergeSort(list: List<Int>): List<Int> {
    if (list.size <= 1) {
        return list
    }

    val middle = list.size / 2
    var left = list.subList(0, middle)
    var right = list.subList(middle, list.size)

    return merge(mergeSort(left), mergeSort(right))
}

fun merge(left: List<Int>, right: List<Int>): List<Int>  {
    var indexLeft = 0
    var indexRight = 0
    var newList: MutableList<Int> = mutableListOf()

    while (indexLeft < left.count() && indexRight < right.count()) {
        if (left[indexLeft] <= right[indexRight]) {
            newList.add(left[indexLeft])
            indexLeft++
        } else {
            newList.add(right[indexRight])
            indexRight++
        }
    }

    while (indexLeft < left.size) {
        newList.add(left[indexLeft])
        indexLeft++
    }

    while (indexRight < right.size) {
        newList.add(right[indexRight])
        indexRight++
    }
    return newList;
}

Пирамидальная сортировка / Heap sort

wiki

Пирамидальная сортировка - это улучшенная сортировка выбором.

Для сортировки используется бинарное сортирующее дерево - дерево, у которого выполнены условия:

• Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
• Значение в любой вершине не меньше значения её потомков.

Общая идея алгоритма:

• Выстраиваем массив в виде сортирующего дерева:
  Array[i] >= Array[2i + 1]
  Array[i] >= Array[2i + 2]
  при 0 <= i < n/2
• Обмениваем элементы Array[0] и Array[n-1] местами. Array[0] является корнем сортирующего дерева, т.е. самым большим значением массива.
• Повторям шаги до тех пор, пока в сортирующем дереве не останется один элемент.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

fun heapSort(a: IntArray) {
    heapify(a)
    var end = a.size - 1
    while (end > 0) {
        val temp = a[end]
        a[end] = a[0]
        a[0] = temp
        end--
        siftDown(a, 0, end)
    }
}

fun heapify(a: IntArray) {
    var start = (a.size - 2) / 2
    while (start >= 0) {
        siftDown(a, start, a.size - 1)
        start--
    }
}

fun siftDown(a: IntArray, start: Int, end: Int) {
    var root = start
    while (root * 2 + 1 <= end) {
        var child = root * 2 + 1
        if (child + 1 <= end && a[child] < a[child + 1]) child++
        if (a[root] < a[child]) {
            val temp = a[root]
            a[root] = a[child]
            a[child] = temp
            root = child
        }
        else return
    }
}

fun main(args: Array<String>) {
    val aa = arrayOf(
        intArrayOf(100, 2, 56, 200, -52, 3, 99, 33, 177, -199),
        intArrayOf(4, 65, 2, -31, 0, 99, 2, 83, 782, 1),
        intArrayOf(12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8)
    )

    for (a in aa) {
        heapSort(a)
        println(a.joinToString(", "))
    }
}

Сортировка подсчётом / Counting sort

wiki

Сортировка подсчётом - это алгоритм, основанный на подсчёте повторяющихся элементов в массиве.

Общая идея алгоритма (простой вариант):

• Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями.
• Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C - это значения массива A, а значение в массиве C - это то, сколько раз это число повторяется в массиве A.
• Проходим по массиву C и переносим значения в массив A.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

fun countingSort(array: IntArray) {
    if (array.isEmpty()) return

    // вычисляем минимальное и максимальное значение в массиве
    val min = array.min()!!
    val max = array.max()!!

    // создаём вспомогательный массив, все элементы которого == 0
    val count = IntArray(max - min + 1)

    // подсчитываем числа и записываем во вспомогательный массив
    for (number in array) count[number - min]++

    // переносим значения в первоначальный массив
    var z = 0
    for (i in min..max)
        while (count[i - min] > 0) {
            array[z++] = i
            count[i - min]--
        }
}

• n - размер отсортированного массива, а k - размер вспомогательного массива

Блочная (карманная, корзинная) сортировка / Bucket sort

wiki

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

Общая идея алгоритма:

• Делим массив на блоки таким образом, чтобы элементы в каждом следующем блоке были всегда больше, чем в предыдущем.
• Сортируем каждый блок, используя какой-либо другой алгоритм сортировки, либо рекурсивно тем же методом разбиения на блоки.
• Объединяем все блоки в один массив.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

fun insertion_sort(arr: ArrayList<Double>) {
    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<Double>) {
    var n = arr.size
    var bucket = Array<ArrayList<Double>>(n, {i-> ArrayList() } )

    for(i in 0..arr.size-1) {
        bucket[Math.floor(n * arr[i]).toInt()].add(arr[i])
    }

    for(i in 0..arr.size - 1) {
        insertion_sort(bucket[i])
    }

    for (i in 1..arr.size - 1) {
        bucket[0].addAll(bucket[i])
    }

• k - количество блоков.

Поразрядная (цифровая) сортировка / Radix sort

wiki

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

Перед началом сортировки необходимо знать:

• length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове);
• rang количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).

Общая идея алгоритма:

• Создаём пустые массивы, количество которых равно rang.
• Распределяем исходные значения по этим массивам. Распределение осуществляется по значению младшего (крайнего) разряда.
• Соединяем значения в той последовательности, в которой они находятся после распределения по спискам.
• Повторяем шаги 1-2 для оставшихся разрядов.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

fun radixSort(original: IntArray): IntArray {
    var old = original
    for (shift in 31 downTo 0) {
        val tmp = IntArray(old.size)
        var j = 0

        for (i in 0 until old.size) {
            val move = (old[i] shl shift) >= 0
            val toBeMoved = if (shift == 0) !move else move

            if (toBeMoved)
                tmp[j++] = old[i]
            else {
                old[i - j] = old[i]
            }
        }
        for (i in j until tmp.size) tmp[i] = old[i - j]
        old = tmp
    }
    return old
}

• w - количество бит, требуемых для хранения каждого ключа.

Битонная сортировка / Bitonic sort

wiki

Битонная сортировка - алгоритм, основанный на понятии битонных последовательностей и операций над ними.

Битонная последовательность - последовательность, которая сначала возрастает, а потом убывает.

Общая идея алгоритма:

• Создаём битонную последовательность. В результате получаем два массива: первый отсортирован в порядке возрастания, второй - в порядке убывания.
• Последовательно сравниваем элементы первого и второго массивов (сначала первые элементы, потом вторые и т.д.). Если какой либо элемент из второго массива окажется меньше, то меняем его местами с элементом из первого массива. В результате в первом массиве окажутся наименьшие элементы из обоих массивов, а во втором - наибольшие. При этом каждый из массивов будет являться битонной последовательностью.
• Рекурсивно применяем второй шаг к отсортированным массивам, после чего массивы можно склеить.

Чтобы превратить произвольную последовательность в битонную, нужно:

• разделить последовательность пополам;
• первую часть отсортировать по возрастанию;
• вторую часть отсортировать по убыванию.

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

1

// в разработке

Timsort

wiki

Timsort - гибридный алгоритм, сочетающий в себе сортировку вставками и сортировку слиянием.

Общая идея алгоритма:

• По специальному алгоритму разделяем входной массив на подмассивы.
• Каждый подмассив сортируем при помощи сортировки вставками.
• Отсортированные массивы собираются в единый массив с помощью модифицированной сортировки слиянием.

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

1

// в разработке

Полезные ссылки

Алгоритм сортировки - общая статья на wiki об алгоритмах сортировки.
Programming algorithms - сайт, посвящённый алгоритмам. Есть раздел с алгоритмами сортировки.
Описание алгоритмов сортировки и сравнение их производительности - статья, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера.
Sorting Algorithms - список статей на geeksforgeeks.org об алгоритмах сортировки.
Sorting Algorithms Visualized - радужная визуализация алгоритмов сортировки.
Kotlin Algorithms - примеры реализации алгоритмов на Kotlin.
Kotlin Algorithm Club - примеры реализации алгоритмов на Kotlin.