Примеры реализации сортировки вставками

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 )
  {
      for( Iterator i = first + 1; i < last; ++i )
          for( Iterator j = i; first < j && *j < *(j - 1); --j )
              std::iter_swap( j - 1, j );
  }

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

Было произведено три пункта оптимизации:

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

template <class Item>
void exch(Item &A, Item &B)
{ 
        Item t = A; A = B; B = t; 
}
template <class Item>
void compexch (Item &A, Item &B)
{ 
        if (B < A) exch(A, B) ;
}
template <class Item>
void insertion_sort(Item a[], int L, int R)
{
        int i;
        for(i = R; i > L; i--) compexch(a[i-1], a[i]);
        for (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 i;
      int[] result = new int[array.Length];
      for (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+1] = array[i];
      }
      return result;
  }

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

public void InsertionSort(ref int[] array)
{
    int i;
    for (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

         public static void insertionSort (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;
                  }
                }

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.

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