Kody źródłowe/Sortowanie przez wstawianie

C

Wersja klasyczna:

void insertSort(int a[], int length)
{
    int i, j, value;

    for (i = 1; i < length; ++i) 
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; --j) 
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = value;
    }
}

Wersja z wyszukiwaniem połówkowym:

void insertionsortwithsearch(int table[], int size) //size jest to ilość elementów -1 (uwzględnienie indexu 0)
{
	int i;
	for ( i=1; i<=size; i++ )
		{
			int j, l, p, key, m;
			key = table[i];
			l = 0;
			p = i-1;
			while ( l<=p )
			{
				m=(l+p)/2;
				if(key<table[m]) 
				{
					p = m-1;
				} else {
					l = m+1;
				}
			}
			for(j=i-1; j>=l; --j)
			{
				table[j+1] = table[j];
			}
				table[l] = key;
			
		}
}

C++

void SortInsert::insertSort(vector<int>::iterator begin, vector<int>::iterator end)
{
    for (vector<int>::iterator i = begin + 1; i != end; ++i)
        for(vector<int>::iterator j = i; j > begin && *j < *(j - 1); --j)
            std::iter_swap((j - 1), j);
}

Ocaml

let rec insertsort list =
	let rec insert element list =
		match list with
		| [] -> [element]
		| (h :: t) ->
				if element > h then h :: (insert element t)
				else element :: h :: t
	in
	match list with
	| [] -> []
	| h :: t -> insert h (insertsort t)

Python

def Insert_sort(A):
    for i in range(1,len(A)):
        klucz = A[i]
        j = i - 1
        while j>=0 and A[j]>klucz:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = klucz
     return A

Ruby

class Array
  def insert_sort!(&sort_by)
    (1..length-1).each do |i|
       value = self[i]
       ivalue = sort_by[self[i]]

       j = i - 1
       while (j >= 0) && (sort_by[self[j]] > ivalue)
         self[j+1] = self[j]
         j -= 1
       end
       self[j+1] = value
     end
     return(self)
  end
   
  def insert_sort(&sort_by)
    self.dup.insert_sort!(&sort_by)
  end
end

Javascript

function insertionSort(array) {
    for (var i = 1; i < array.length; i++) {
        var key = array[i];
        var j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j = j - 1;
        }
        j++;
        array[j] = key;
    }
}

SML

Implementacja algorytmu w języku funkcyjnym - SML-u:

(* funkcja bierze listę dowolnego typu i relacje zgodnie z którą sortuje elementy listy*)
fun isort [] f = []
  | isort (x::xs) f =
          let fun insert x [] = [x]
                | insert x (l as hd::tl) = if f (x,hd) then x::l
                                             else hd::insert x tl
          in insert x (isort xs f) end;

(* przykładowe użycie sortuj niemalejąco listę liczb całkowitych: *)
isort [108, 15, 15, 3, 14, 15, 108] op<;

Prolog

wstaw(X,[Y|T],[Y|NT]) :- X>Y, wstaw(X,T,NT).
wstaw(X,[Y|T],[X,Y|T]) :- X=<Y.
wstaw(X,[],[X]).

sortuj([], []).

sortuj(X, Y) :-
	X = [H|T],
	sortuj(T, Y2),
	wstaw(H, Y2, Y),
	!.