Реализации алгоритмов/Сортировка/Вставками

Haskell

isort :: (Ord e) => [e] -> [e]
isort    []    = []
isort (x : xs) = insert x $ isort xs
  where
    insert x [] = [x]
    insert x (y : ys)
      | x <= y = x : y : ys
      |  True  = y : insert x ys

Си

int pass, j, hold;

	for (pass = 0; pass < SIZE-1; pass++){
		for (j = pass+1; j < SIZE; j++){
			if (n[pass]>n[j]){
				hold = n[j];
				n[j] = n[pass];
				n[pass] = hold;
			}
		}
	}

typedef struct List {
    struct List* next;
    struct List* prev;
    uint32_t id;
} list_t;
void list_insert_prev(list_t* head, list_t* tail) {
    tail->prev = head->prev;
    tail->next = head;
    head->prev = tail;
    if (tail->prev) tail->prev->next = tail;
}
list_t* list_cut(list_t* head) {
    list_t* cut = head;
    if (cut->next) head->next->prev = head->prev;
    if (cut->prev) head->prev->next = head->next;
    return cut;
}
void list_insertion_sort(list_t* head) {
    while (head->next) {
        if (head->next->id < head->id) {
            list_t* cut = list_cut(head->next);
            while ((head->prev) && (cut->id < head->prev->id)) {
                head = head->prev;
            }
            list_insert_prev(head, cut);
        } else {
            head = head->next;
        }
    }
}

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# (без дополнительной памяти 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;
    }
}

С++11

#include <algorithm>
#include <cstddef>

template<typename T>
void insertion_sort(T array[], std::size_t size)
{
    for (std::size_t sorted_size = 1; sorted_size < size; sorted_size++)
    {
        if (array[sorted_size] < array[sorted_size - 1])
        {
            T tmp = std::move(array[sorted_size]);

            std::size_t idx = sorted_size;
            for (; idx != 0 && tmp < array[idx - 1]; idx--)
            {
                array[idx] = std::move(array[idx - 1]);
            }
            array[idx] = tmp;
        }
    }
}//

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 insertIntoSort(int[] arr)
{
    int temp, j;
    for(int i = 0; i < arr.length - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
           temp = arr[i + 1];
           arr[i + 1] = arr[i];
           
           for (j = i; j >0 && temp < arr[j - 1]; j--)
           arr[j] = temp;
        }
    }
}

Java 2

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

            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

k=input()
a=list(map(int,input().split()))
n=len(a)-1
k=0
for i in range(len(a)):
    for j in range(len(a)-1-i):
        if a[j]>a[j+1]:
            a[j],a[j+1]=a[j+1],a[j]
            o=True
    k+=1
    if not o : break
print(*a)

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;
  }
 return $a; // return 
}

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

PLSQL

 type sort_lst is table of integer; 
----------------------Сортировка вставками-----------------------------------------------
Function Insertion_sort(in_list IN sort_lst) return sort_lst
  IS   
   l_list sort_lst := sort_lst();
   h pls_integer; j pls_integer;
begin
     l_list := in_list;
     
            for i in l_list.first..l_list.last-1 loop
                j:=i;
                    while j>=1 and l_list(j)>l_list(j+1) loop
                        h:= l_list(j);
                        l_list(j):=l_list(j+1);
                        l_list(j+1):=h;
                        j:=j-1;  
                    end loop;
            end loop;
            
   return l_list;                                
end Insertion_sort;

Ссылки

• Сортировка пузырьком, выборкой, вставками (Youtube)