Сортировка Вставками (Insertion-sort)

Подробности
Категория: Сортировка и поиск

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

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

 

 

 



Худшее время

О(n2) сравнений, обменов
Лучшее время

O(n) сравнений, O(1) обмен
Среднее время

О(n2) сравнений, обменов
Затраты памяти

О(n) всего, O(1) вспомогательный

 

 

 

Реализация алгоритма на различных языках программирования:

Haskell

 insert :: Ord a ? a ? [a] ? [a]
 insert x [] = [x]
 insert x (y : ys)
   | x ? y = x : y : ys
   | otherwise = y : insert x ys

 isort :: Ord a ? [a] ? [a]
 isort [ ] = [ ]
 isort (x : xs) = insert x (isort xs)

 

Си

int i, j, temp;
for (i = 1; i < size; i++)
{
    temp = array[i];
    for (j = i - 1; j >= 0; j--)
    {
        if (array[j] < temp)
            break;
 
        array[j + 1] = array[j];
        array[j] = temp;
    }
}

 

C++

#include <algorithm>
 
template <typename Iterator>
void insertion_sort(Iterator first, Iterator last)
{
    if (!(first < last))
        return;
 
    for (Iterator i = first + 1; i != last; ++i)
        for (Iterator j = i; j != first && *j < *(j - 1); --j)
            std::iter_swap(j - 1, j);
}

 

C++ (оптимизирован)

Произведены следующие оптимизации:

  • нахождение минимального элемента и помещение его в первую позицию (это требуется для правильного функционирования второго пункта);
  • выход из внутреннего цикла, когда элемент находится на требуемой позиции;
  • замена операции обмена (swap) операцией присваивания.
template <typename Item>
void exch(Item &A, Item &B)
{
    Item t = A; A = B; B = t;
}
 
template <typename Item>
void compexch(Item &A, Item &B)
{
    if (B < A) exch(A, B);
}
 
template <typename Item>
void insertion_sort(Item a[], int L, int R)
{
    for(int i = R; i > L; i--)
        compexch(a[i - 1], a[i]);
 
    for (int i = L + 2; i <= R; i++)
    {
        int j = i;
        Item cur = a[j];
        while (a[j - 1] > cur)
        {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = cur;
    }
}

 

C# (с возвратом результата)

public int[] InsertionSort(int[] array)
{
    int[] result = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
    {
        int j = i;
        while (j > 0 && result[j - 1] > array[i])
        {
            result[j] = result[j - 1];
            j--;
        }
        result[j] = array[i];
    }
    return result;
}

 

C# (без дополнительной памяти 1)

public void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int cur = array[i];
        int j = i;
        while (j > 0 && cur < array[j - 1])
        {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = cur;
    }
}

 

C# (без дополнительной памяти 2)

public void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int j;
        int buf = array[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (array[j] < buf)
                break;
 
            array[j + 1] = array[j];
        }
        array[j + 1] = buf;
    }
}

 

Java 1

public static void insertionSort(int[] arr) {
    for(int i = 1; i < arr.length; i++){
        int currElem = arr[i];
        int prevKey = i - 1;
            while(prevKey >= 0 && arr[prevKey] > currElem){
                arr[prevKey+1] = arr[prevKey];
                arr[prevKey] = currElem;
                prevKey--;
            }
    }
}

 

 

Java 2

public static void insertionSort2(int[] m, int a, int b) {
    int t;
    int i, j;
    for (i = a; i < b; i++) {
        t = m[i];
        for (j = i - 1; j >= a && m[j] > t; j--)
            m[j + 1] = m[j];
 
        m[j + 1] = t;
    }
}

 

Javascript

(function() {
    var oSort= function() {
 
        var that = {};
 
        //собственно сама функция сортировки
        that.insertionSort = function(a) {
            var i,j,x,
                iCount = that.getCountOfElements(a);
 
            for( i=0; i<iCount; i++) {
                x = a[i];
                for( j=i-1; j>=0 && a[j]>x; j-- ) {
                    a[j+1] = a[j];
                }
                a[j+1] = x;
            }
 
            return a;
        };
 
        that.getCountOfElements = function(a) {
            var i = 0,
                elem;
            for (elem in a) {
                i++
            }
            return i;
        };
 
        return that;
 
    }();
 
    console.log(oSort.insertionSort([9, 13, 7, 12, 10, 14, 8, 11, 6]));
    //[6, 7, 8, 9, 10, 11, 12, 13, 14]
 
})();

 

VBA

Sub Sort(Mus() As Long)
    Dim l As Long, r As Long, i As Long, j As Long, buf As Long
    l = LBound(Mus)
    r = UBound(Mus)
 
    For i = (l + 1) To r
        buf = Mus(i)
        j = i - 1
        Do While (Mus(j) > buf)
            Mus(j + 1) = Mus(j)
            j = j - 1
            If j < l Then Exit Do
        Loop
        Mus(j + 1) = buf
    Next
End Sub

 

Python

def fast_insertion_sort(l):
    for i in xrange(1, len(l)):
        j = i - 1
        value = l.pop(i)
        while (j >= 0) and (l[j] > value):
            j -= 1
        l.insert(j + 1, value)
    return l

 

Perl

for(1..$N-1){
    my$tmp=$out[$_];
	for($j=$_-1;$j>=0;$j--){
	    $out[$j+1]=$out[$j];
	    last if($out[$j]lt$tmp);
	}
    $out[$j+1]=$tmp;
}

 

Паскаль

const N = 255;
type TArray = array [1..N] of integer;
procedure InsertSort(var x: TArray);
var
  i, j, buf: integer;
begin
  for i := 2 to N do
  begin
    buf := x[i];
    j := i - 1;
    while (j >= 1) and (x[j] > buf) do
    begin
      x[j + 1] := x[j];
      j := j - 1;
    end;
    x[j + 1] := buf;
  end;
end;

 

Delphi

type TArray<T> = array of T;
procedure TSomeObject.InsertSort<T>(var arr: TArray<T>);
var
  i, j: integer;
  buf:T;
begin
  for i := Low(arr)+1 to High(arr) do
  begin
    buf := arr[i];
    j := i - 1;
    while (j >= Low(arr) ) and (arr[j] > buf) do
    begin
      arr[j + 1] := arr[j];
      Dec(j);
    end;
    arr[j + 1] := buf;
  end;
end;

 

PHP

function insertion_sort(&$a) {
  // для каждого $a[$i] начиная со второго элемента...
  for ($i = 1; $i < count($a); $i++) {
    $x = $a[$i];
    for ($j = $i - 1; $j >= 0 && $a[$j] > $x; $j--) {
      /* сдвигаем элементы вправо, пока выполняется условие
         $a[$j] > $a[$i] */
      $a[$j + 1] = $a[$j];
    }
    // на оставшееся после сдвига место, ставим $a[$i]
    $a[$j + 1] = $x;
  }
}

 

Ruby

arr = [9, 13, 7, 12, 10, 14, 8, 11, 6]
for i in 1..arr.length - 1
  x = arr[i]
  for j in 0..i - 1
    if arr[i] < arr[j]
        i.downto(j + 1) do |k|
          arr[k] = arr[k - 1]
        end
      arr[j] = x
      break
    end
  end
end
puts "#{arr.join(" ")}"
# output => 6 7 8 9 10 11 12 13 14

 

Turbo Basic 1.1

Входной массив Y[1],...,Y[N]

FOR I=2 TO N
   K=Y[I]
   J=I-1
   WHILE J>0 AND Y[J]>K
      Y[J+1]=Y[J]
      J=J-1
      WEND
   Y[J+1]=K
   NEXT I

 

 Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — O(n^2). 

 

 

При написании статьи были использованы открытые источники сети интернет :

 

Wikipedia

 

Kvodo

 

Youtube

 







Похожие материалы

Видеотека

-->

Яндекс.Метрика