Набор Алгоритмов

Данная статья посвящена менее распространённым алгоритмам сортировки. Контретно Сортировке вставкой (Insertion), Сортировке Дональда Шелла (Shell), Сортировке слиянием (Merge), Кучной сортировке (Heap).

Алгоритмы - Алгоритмы сортировки #5, Другие алгоритмы сортировки

Все примеры кода приведены на JavaScript.

1. Сортировка вставкой (Insertion)

1.1. Первое объяснение

Алгоритм сортировки от меньшего к большему:

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        Поменять местами a[k,k-1]
    // Подмассив a[1..i] уже отсортирован
end

Алгоритм сортировки от большего к меньшему:

for i = 2:n,
    for (k = i; k > 1 and a[k] > a[k-1]; k--)
        Поменять местами a[k,k-1]
    // Подмассив a[1..i] уже отсортирован
end

1.2. Второе объяснение

Дадим блок-схему сортировки вставкой в обоих направлениях (от большего к меньшему, от меньшего к большему):

Рис. 1. Блок-схема сортировки вставкой (Insertion).

1.3. Третье объяснение

1.3.1. Общий код для тестирования и работы сортировок

1.3.1.1. Работа сортировок

Рассмотрим вспомогатальный код для работы сортировок:

var Sorter = {
    SortDirection : {
        FromLowToHigh: -1,
        FromHighToLow: 1
    }
};

Код 1.3.1.1. Исходный код файла "sorter-enum.js".

Зачем нужна эта переменная?

Поле Sorter.SortDirection.FromHighToLow означает направление сортировки от большего к меньшему.

Поле Sorter.SortDirection.FromLowToHigh означает направление сортировки от меньшего к большему.

Рассмотрим вспомогатальный код для тестирования сортировок:

1.3.1.2. Класс для тестирования сортировок

var SortingTest = {
    newArray: function(length, order) {
        var result = [];
        if(Sorter.SortDirection.FromLowToHigh == order) {
            for(var i = 0; i < length; i++) {
                result.push(i);
            }
        }
        else {
            for(var i = length - 1; i >= 0; i--) {
            result.push(i);
            }
        }
        return result;
    },
    arrayToString: function (arr) {
        result = "[";
        for(var i = 0; i < arr.length; i++) {
            result += arr[i];
            if(i < (arr.length - 1)) {
                result += ", ";
            }
        }
        result += "]";
        return result;
    },
    testArray: function(arr, order) {
        var result = true;
        for(var i = 0; (i < (arr.length - 2)) && result; i++) {
            if(order) {
                if(arr[i] > arr[i+1]) {
                result = false;
            }
            }
            else {
                if(arr[i] < arr[i+1]) {
                    result = false;
                }
            }
        }
        return result;
    }
};

Код 1.3.1.2. Исходный код файла "test-other-sorting.js".

Рассмотрим его:

1.3.2. Код Сортировки вставкой (Insertion).

Код класса сортировки:

function InsertionSorter(array, sortOrder, callback) {
    var self = this;
    self._private = {
        array: array,
        sortOrder: sortOrder,
        callback: callback
    };
    self.sort = function () {
        var arr = self._private.array;
        if(sortOrder === Sorter.SortDirection.FromLowToHigh) {
            for(var i = 1; i < arr.length; i++) {
                for(var k = i; k > 0 && arr[k] < arr[k-1]; k--) {
                    var temp = arr[k-1];
                    arr[k-1] = arr[k];
                    arr[k] = temp;
                }
            }
        }
        else {
            for(var i = 1; i < arr.length; i++) {
                for(var k = i; k > 0 && arr[k] > arr[k-1]; k--) {
                    var temp = arr[k-1];
                    arr[k-1] = arr[k];
                    arr[k] = temp;
                }
            }
        }
        self._private.callback();
    };
    self.getArray = function () {
        return self._private.array;
    };
}

Код 1.3.2.1. Исходный код файла "insertion-sorter.js".

2. Сортировка Дональда Шелла (Shell)

2.1. Первое объяснение

Согласно Википедии: Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами.

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

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, сортировка вставкой(insertion sort) a[k:h:n]
end

2.2. Второе объяснение

Дадим блок-схему сортировки Дональда Шелла в обоих направлениях (от большего к меньшему, от меньшего к большему):

Рис. 2. Блок-схема сортировки Дональда Шелла (Shell).

2.3. Третье объяснение

2.3.1. Код Сортировки Дональда Шелла (Shell)

Код класса сортировки:

function ShellSorter(array, sortOrder, callback) {
    var self = this;
    self._private = {
        array: array,
        sortOrder: sortOrder,
        callback: callback
    };
    self.sort = function () {
        var arr = self._private.array;
        if(sortOrder === Sorter.SortDirection.FromLowToHigh) {
            var increment = arr.length / 2;
            while (increment > 0) {
                for (var i = increment; i < arr.length; i++) {
                    var j = i;
                    var temp = arr[i];
                    while (j >= increment && arr[j-increment] > temp) {
                        arr[j] = arr[j-increment];
                        j = j - increment;
                    }
                    arr[j] = temp;
                }
                if (increment == 2) {
                    increment = 1;
                } else {
                    increment = parseInt(increment*5 / 11);
                }
            }
        }
        else {
            var increment = arr.length / 2;
            while (increment > 0) {
            for (var i = increment; i < arr.length; i++) {
                var j = i;
                    var temp = arr[i];
                    while (j >= increment && arr[j-increment] < temp) {
                        arr[j] = arr[j-increment];
                        j = j - increment;
                    }
                    arr[j] = temp;
                }
                if (increment == 2) {
                    increment = 1;
                } else {
                    increment = parseInt(increment*5 / 11);
                }
            }
        }
        self._private.callback();
    };
    self.getArray = function () {
        return self._private.array;
    };
}

Код 2.3.1.1. Исходный код файла "shell-sorter.js".

3. Сортировка слиянием (Merge)

3.1. Первое объяснение

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

# разделение пополам
m = n / 2

# рекурсивная сортировка
sort a[1..m]
sort a[m+1..n]

# слияние отсортированных массивов используя временный массив
b = делаем копию подмассива a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
while i <= m,
    a[k++] = b[i++]

Направление сортировки в алгоритме определите самостоятельно при его реализации.

3.2. Второе объяснение

Дадим блок-схему сортировки слиянием (Merge) в обоих направлениях (от большего к меньшему, от меньшего к большему):

Рис. 3. Блок-схема сортировки слиянием (Merge).

3.3. Третье объяснение

3.3.1. Код Сортировки слиянием (Merge)

Код класса сортировки:

function MergeSorter(array, sortOrder, callback) {
    var self = this;
    self._private = {
        array: array,
        sortOrder: sortOrder,
        callback: callback
    };
    var _mergeArrays = function (left, right) {
        var arr = [];
        if(sortOrder === Sorter.SortDirection.FromLowToHigh) {
            while (left.length && right.length) {
                if (left[0] < right[0]) {
                    arr.push(left.shift());
                } else {
                    arr.push(right.shift());
                }
            }
            var result = [];
            for(var i = 0; i < arr.length; i++)
                result.push(arr[i]);
            for(var i = 0; i < left.length; i++)
                result.push(left[i]);
            for(var i = 0; i < right.length; i++)
                result.push(right[i]);
            return result;
        }
        else {
            while (left.length && right.length) {
                if (left[0] > right[0]) {
                    arr.push(left.shift());
                } else {
                    arr.push(right.shift());
                }
            }
            var result = [];
            for(var i = 0; i < arr.length; i++)
                result.push(arr[i]);
            for(var i = 0; i < left.length; i++)
                result.push(left[i]);
            for(var i = 0; i < right.length; i++)
                result.push(right[i]);
            return result;
        }
    }
    var mergeSort = function (array) {
        var half = array.length / 2;
        if(array.length < 2) {
            return array;
        }
        var left = array.splice(0, half);
        return _mergeArrays(mergeSort(left),mergeSort(array));
    }
    self.sort = function () {
        self._private.array = mergeSort(self._private.array);
        self._private.callback();
    };
    self.getArray = function () {
        return self._private.array;
    };
}

Код 3.3.1.1. Исходный код файла "merge-sorter.js".

4. Кучная сортировка (Heap)

4.1. Первое объяснение

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

# нагружаем
for i = n/2:1, sink(a,i,n)

# сортировка
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
end

# тонем в i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # нет потомков
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # куча в порядке
    swap a[i,mc]
    sink(a,mc,n)

Направление сортировки в алгоритме определите самостоятельно при его реализации.

4.2. Второе объяснение

Дадим блок-схему кучной сортировки (Heap) в обоих направлениях (от большего к меньшему, от меньшего к большему):

Рис. 4. Блок-схема кучной сортировки (Heap).

4.3. Третье объяснение

4.3.1. Код Кучной сортировки (Heap)

Код класса сортировки, он оптимизирован для JavaScript:

function HeapSorter(array, sortOrder, callback) {
    var self = this;
    self._private = {
        array: array,
        sortOrder: sortOrder,
        callback: callback
    };
    var array_length = array.length;
    var heap = function (input, i) {
        var left = 2 * i + 1;
        var right = 2 * i + 2;
        var max = i;
        if(sortOrder === Sorter.SortDirection.FromLowToHigh) {
            if (left < array_length && input[left] > input[max]) {
                max = left;
            }
            if (right < array_length && input[right] > input[max]) {
                max = right;
            }
            if (max != i) {
                swap(input, i, max);
                heap(input, max);
            }
        }
        else {
            if (left < array_length && input[left] < input[max]) {
                max = left;
            }
            if (right < array_length && input[right] < input[max]) {
                max = right;
            }
            if (max != i) {
                swap(input, max, i);
                heap(input, max);
            }
        }
    }
    var swap = function (input, index_A, index_B) {
        var temp = input[index_A];
        input[index_A] = input[index_B];
        input[index_B] = temp;
    }
    var heapSort = function (input) {
        var array_length = input.length;
        for (var i = Math.floor(array_length / 2); i >= 0; i -= 1) {
            heap(input, i);
        }
        for (var i = input.length - 1; i > 0; i--) {
            swap(input, 0, i);
            array_length--;
            heap(input, 0);
        }
    }
    self.sort = function () {
        heapSort(array);
        self._private.callback();
    };
    self.getArray = function () {
        return self._private.array;
    };
}

Код 4.3.1.1. Исходный код файла "heap-sorter.js".

5. Пример вызова всех сортировок

Приведу пример вызова каждого типа сортировки, описанного выше, ввиде кода html-страницы со встроенным кодом JavaScript (JavaScript использует файлы описанные выше):

<!DOCTYPE html>
<html>
<head>
<title>Алгоритмы - Алгоритмы сортировки #5, Другие алгоритмы сортировки</title>
<link rel="stylesheet" type="text/css" href="../../../css/main.css">
<script src="js/sorter-enum.js"></script>
<script src="js/test-other-sorting.js"></script>
<script src="js/insertion-sorter.js"></script>
<script src="js/shell-sorter.js"></script>
<script src="js/merge-sorter.js"></script>
<script src="js/heap-sorter.js"></script>
</head>
<body>
    <h1>Тестирование сортировок #5</h1>
    <h2>Сортировка вставкой (Insertion)</h2>
    <p><b>Начальный массив:</b></p>
    <div class="commands">
        <script>
            document.write(SortingTest.arrayToString(SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh)));
        </script>
    </div>
    <p><b>Конечный массив:</b></p>
    <div class="commands" id="js-output-insertion">
        <script>
            var arr = new InsertionSorter(
                SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh), Sorter.SortDirection.FromHighToLow,
                function () {
                    document.getElementById('js-output-insertion').innerHTML += SortingTest.arrayToString(arr.getArray());
                }
            );
            arr.sort();
        </script>
    </div>
    <h2>Сортировка Дональда Шелла (Shell)</h2>
    <p><b>Начальный массив:</b></p>
    <div class="commands">
        <script>
            document.write(SortingTest.arrayToString(SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh)));
        </script>
    </div>
    <p><b>Конечный массив:</b></p>
    <div class="commands" id="js-output-shell">
        <script>
            var arr = new ShellSorter(
                SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh), Sorter.SortDirection.FromHighToLow,
                function () {
                    document.getElementById('js-output-shell').innerHTML += SortingTest.arrayToString(arr.getArray());
                }
            );
            arr.sort();
        </script>
    </div>
    <h2>Сортировка слиянием (Merge)</h2>
    <p><b>Начальный массив:</b></p>
    <div class="commands">
        <script>
            document.write(SortingTest.arrayToString(SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh)));
        </script>
    </div>
    <p><b>Конечный массив:</b></p>
    <div class="commands" id="js-output-merge">
        <script>
            var arr = new MergeSorter(
                SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh), Sorter.SortDirection.FromHighToLow,
                function () {
                    document.getElementById('js-output-merge').innerHTML += SortingTest.arrayToString(arr.getArray());
                }
            );
            arr.sort();
        </script>
    </div>
    <h2>Кучная сортировка (Heap)</h2>
    <p><b>Начальный массив:</b></p>
    <div class="commands">
        <script>
            document.write(SortingTest.arrayToString(SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh)));
        </script>
    </div>
    <p><b>Конечный массив:</b></p>
    <div class="commands" id="js-output-heap">
        <script>
            var arr = new HeapSorter(
                SortingTest.newArray(11, Sorter.SortDirection.FromLowToHigh), Sorter.SortDirection.FromHighToLow,
                function () {
                    document.getElementById('js-output-heap').innerHTML += SortingTest.arrayToString(arr.getArray());
                }
            );
            arr.sort();
        </script>
    </div>
</body>
</html>

6. Заключение

Попробуйте реализовать алгоритмы сортировки на любимом Вам языке программирования, пользуясь только описанием алгоритма, а не его реализацией на JavaScript, в прямом и обратном направлениях.