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

Как и практически любая книга, все начинается с алгоритмов сортировки. Казалось бы, что может быть проще чем отсортировать массив чисел? С 10 числами все плюс-минус понятно, там можно использовать что угодно, все равно скорость будет мгновенная.

Что же делать, в случае огромного числа элементов в массиве?

Чтоб было легче пользовать и тестировать алгоритмы, создадим небольшие вспомогательные методы, которые упростят нам жизнь ( в реальном проекте я вам очень не рекомендую так делать, просто потому-что добавлять методы в нативные объекты не стоит, и может вылезти вам боком в самых не предвиденных ситуациях ):

Небольшой метод который добавляет в обычный массив функцию смена позиций 2х элементов:

Array.prototype.swap = function(a,b){
 var tmp = this[a];
 this[a] = this[b];
 this[b] = tmp;
}

Функция для заполнения массива случайными числами:

Array.prototype.generate_numbers = function(amount){
 for (var i = 0; i < amount; i++ ){
 this[i] = Math.floor(Math.random() * amount + 1);
 }
}

Функция сортировки ( метод сортировки Кнута, про который мы поговорим потом ):

Array.prototype.knuth_shuffle = function() {
  var random = 0;
  for (var i = 1; i < this.length; i++){
    var random = Math.floor(Math.random() * i);
    this.swap(i, random); 
  }
};

Еще раз подчеркиваю, что так стандартные объекты расширять не стоит, но так как унаследование массива в JavaScript совсем уж не простая задача — для теста делаем так.

Алгоритм отличается своей простотой, стабильностью, и очень хорошими показателями в случае если массив частично отсортирован. Лучше всего работу алгоритма демонстрирует следующая гифка:

Код алгоритма очень прост:

insertion_sort = function(array){
 var length = array.length;
for (var i = 0; i < length; i++){
for ( var j = i; j > 0; j — ){
 if (array[j] < array[j-1] ){
     array.swap(j, j-1);
   } else {
     break;
   }
  }
}
return array;

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

Тестирование алгоритма происходило следующим образом: генерились массивы величиной в 100, 1000, 10000, и 100000 элементов и сортировались. Время сортировки замерялось. Чтоб уменьшить различные факторы, типа сгенерился массив который был почти сортирован ( ну а вдруг ) тест проводился 5 раз, и вот какие результаты были полученны на моем MacBook Middle 2014, 2.6GHz Intel Core i5, 8gb DDR3:

В последующих постах мы сравним результаты с другими алгоритмами.

Немного инфы про алгоритм:

1. Сложность по памяти O(n) = 1
2. По времени O(n) = n ^ 2 :

Исходники примеров вы можете найти тут.