Algorithm Implementation/Sorting/Insertion sort

Insertion sort Ada Sorts an array of integers. type Integer_Array is array (Natural range <>) of Integer; procedure Insertion_Sort (A : in out Integer_Array) is Value : Integer; J : Natural; begin for I in A'First + 1 .. A'Last loop Value := A(I); J := I - 1; while J >= A'First and then A(J) > Value loop A(J + 1) := A(J); J := J - 1; end loop; A(J + 1) := Value; end loop; end Insertion_Sort; AutoIt3 Func insertionSort( ByRef $array ) For $i = 1 to Ubound( $array ) - 1 $j = $i - 1 $temp = $array[$i] While ( $j >= 0 ) And ( $array[$j] > $temp ) $array[$j+1] = $array[$j] $j -= 1 WEnd $array[$j+1] = $temp Next EndFunc C/C++ In C: void insertSort(int a[], int length) { int i, j, value; for(i = 0 ; 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; } } In C++: #include <iostream> using namespace std; template<class Iterator> void insertion_sort( Iterator a, Iterator end ) { std::iter_swap( a, std::min_element( a, end ) ); for ( Iterator b = a; ++b < end; a = b ) for( Iterator c = b; *c < *a; --c, --a ) std::iter_swap( a, c ); } In C++, half insertion sort: void halfInsertSort(int array[], int length) { int begin; int end; int middle; int value; for (int i = 1; i < length; ++i) { value = array[i]; begin = 0; end = i - 1; while (begin <= end) { middle = (begin + end) / 2; if (value < array[middle]) { end = middle - 1; } else { begin = middle + 1; } } for (int j = i - 1; j >= begin; --j) { array[j + 1] = array[j]; } array[begin] = value; } } C# static void InsertSort(IComparable[] array) { int i, j; for (i = 1; i < array.Length; i++) { IComparable value = array[i]; j = i - 1; while ((j >= 0) && (array[j].CompareTo(value) > 0)) { array[j + 1] = array[j]; j--; } array[j + 1] = value; } } C# 2.0 This example sorts a list of objects of any type T that implements IComparable. It demonstrates C# 2.0 generics and in particular the "where" clause. static void InsertSort<T>(IList<T> list) where T : IComparable<T> { int i, j; for (i = 1; i < list.Count; i++) { T value = list[i]; j = i - 1; while ((j >= 0) && (list[j].CompareTo(value) > 0)) { list[j + 1] = list[j]; j--; } list[j + 1] = value; } } CAML let rec insertion_sort l = match l with | [] -> [] | (h::n) -> insert h (insertion_sort n) and insert t l = match l with | [] -> [t] | (h::n) -> if t > h then h::(insert t n) else t::h::n ;; Common Lisp (defun insert (target list) (if (null list) (cons target nil) (if (<= target (first list)) (cons target list) (cons (first list) (insert target (rest list)))))) (defun insertSort (myList) (if (null myList) nil (insert (first myList) (insertSort (rest myList))))) Fortran 90/95 This implementation of Insertion sort follows closely the implementation that can be found in the GPL FORTRAN 90/95 GPL library AFNL. ! *********************************** ! * Subroutine Insrt(X, Ipt) ! * ! *********************************** ! * Sort Array X(:) in ascendent order. ! * If present Ipt, a pointer with the ! * changes is returned in Ipt. ! *********************************** Real (kind=4), Intent (inout) :: X(:) Integer, Intent (out), Optional :: Ipt(:) Real (kind=4) :: Rtmp Integer :: I, J If (Present(Ipt)) Then Forall (I=1:Size(X)) Ipt(I) = I Do I = 2, Size(X) Rtmp = X(I) Do J = I-1, 1, -1 If (Rtmp < X(J)) Then X(J+1) = X(J) CALL Swap(Ipt, J, J+1) Else Exit End If End Do X(J+1) = Rtmp End Do Else Do I = 2, Size(X) Rtmp = X(I) Do J = I-1, 1, -1 If (Rtmp < X(J)) Then X(J+1) = X(J) Else Exit End If End Do X(J+1) = Rtmp End Do End If Return End Subroutine Insrt ! *********************************** ! * Subroutine Swap(X, I, J) ! * ! *********************************** ! * Swaps elements I and J of array X(:). ! *********************************** Integer, Intent (inout) :: X(:) Integer, Intent (in) :: I, J Integer :: Itmp Itmp = X(I) X(I) = X(J) X(J) = Itmp Return End Subroutine Swap F# let insertionSort l = let rec insert x sortedList = match sortedList with | smallest :: sortedTail when smallest < x -> smallest :: insert x sortedTail | _ -> x :: sortedList List.foldBack insert l [] Go func InsertionSort(data []int) { for i, v := range data { j := i for ;j > 0 && v < data[j - 1]; j-- { data[j] = data[j - 1] } data[j] = v } } Java public static void insertionsort(int[] numbers) { for (int i = 0; i < numbers.length; i++) { int copyNumber = numbers[i]; int j = i; while (j > 0 && copyNumber < numbers[j-1]) { numbers[j] = numbers[j-1]; j--; } numbers[j] = copyNumber; } } another general implements. public static < E extends Comparable<? super E> > void insertSort( E[] comparable ) { for ( int i = 1; i < comparable.length; i++ ) { E value = comparable[i]; int j = i - 1; while ( j >= 0 && comparable[j].compareTo( value ) > 0 ) { comparable[j + 1] = comparable[j--]; } comparable[j + 1] = value; } } JavaScript // Assumes all elements are non-null and non-undefined function insertionSort(sortMe) { for (var i = 0, j; i < sortMe.length; ++i) { var tmp = sortMe[i]; for (var j = i - 1; j >= 0 && sortMe[j] > tmp; --j) sortMe[j + 1] = sortMe[j]; sortMe[j + 1] = tmp; } } Haskell import Data.List (insert) insertsort :: Ord a => [a] -> [a] insertsort = foldr insert [] OCaml In lists let rec insert e = function h::t when e <= h -> h :: insert e t | l -> e :: l let rec insertion_sort = function [] -> [] | h::t -> insert h (insertion_sort t) shorter version The insert function is the same as above. let rec insert e = function h::t when e <= h -> h :: insert e t | l -> let insertion_sort xs = List.fold_right insert xs [] Pascal Procedure InsertionSort(var ArrayOfOrd: AnyOrdType); var Top, InsertionPos: integer; Cache :string; Begin for Top := 1 to length(ArrayOfOrd) - 1 do begin Cache := ArrayOfOrd[Top]; InsertionPos := Top; while (ArrayOfOrd[InsertionPos - 1] > Cache) and (InsertionPos > 0) do begin ArrayOfOrd[InsertionPos] := ArrayOfOrd[InsertionPos - 1]; dec(InsertionPos); end; ArrayOfOrd[InsertionPos] := Cache; end; End; Linked list version procedure insertionSort(var L:PNode); var h, x, xs, y, z:PNode; begin h := NIL; x := L; while x <> NIL do begin xs := x^.next; y := h; z :=NIL; while (y <> NIL)and(x^.key > y^.key)do begin z := y; y := y^.next; end; x^.next := y; if z <> NIL then z^.next := x else h := x; x := xs; end; L := h; end; Perl sub insert_sort { for(my $i = 1; $i <= $#_; $i++) { my ($j, $val) = ($i - 1, $_[$i]); $_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val); $_[$j+1] = $val; } } Phix function insertion_sort(sequence s) object temp integer j for i=2 to length(s) do temp = s[i] j = i-1 while j>=1 and s[j]>temp do s[j+1] = s[j] j -= 1 end while s[j+1] = temp end for return s end function PHP for ($j=1; $j < count($array); $j++) { $temp = $array[$j]; $i = $j; while (($i >= 1) && ($array[$i-1] > $temp)) { $array[$i] = $array[$i-1]; $i--; } $array[$i] = $temp; } Python def insertsort(array): for removed_index in range(1, len(array)): removed_value = array[removed_index] insert_index = removed_index while insert_index > 0 and array[insert_index - 1] > removed_value: array[insert_index] = array[insert_index - 1] insert_index -= 1 array[insert_index] = removed_value Standard ML fun insertsort [] = [] | insertsort (x::xs) = let fun insert (x:real, []) = [x] | insert (x:real, y::ys) = if x<=y then x::y::ys else y::insert(x, ys) in insert(x, insertsort xs) end; shorter version The insert function is the same as above. fun insert (x:real, []) = [x] | insert (x, y::ys) = if x <= y then x::y::ys else y::insert(x, ys) val insertion_sort = foldr insert [] Ruby It sorts the original array. def insert_sort!(list) for i in 1..(list.length - 1) value = list[i] j = i - 1 while j >= 0 and list[j] > value list[j + 1] = list[j] j -= 1 end list[j + 1] = value end end Swift In Swift: func insertionSort<T: Comparable> (list: inout [T]) { for i in 1..<list.count { var j = i - 1 let x = list[i] while 0 <= j && x < list[j] { swap(&list[j+1], &list[j]) j -= 1 } list[j+1] = x } } NASM C prototype is void isort(int *a, int n) Assembler routine is isort: %define a [ebp + 8] %define n [ebp + 12] enter 0, 0 pusha mov ecx, 1 for: mov ebx, ecx imul ebx, 4 add ebx, a mov ebx, [ebx] mov edx, ecx dec edx while: cmp edx, 0 jl while_quit mov eax, edx imul eax, 4 add eax, a cmp ebx, [eax] jge while_quit mov esi, [eax] mov dword [eax + 4], esi dec edx jmp while while_quit: mov [eax], ebx inc ecx cmp ecx, n jl for popa leave ret VB Public Sub InsertionSort(ByRef ArrayAngka() As Long) Dim i, j As Integer Dim t As Long For i = 0 To (n - 1) For j = i + 1 To 1 Step -1 If ArrayAngka(j) < ArrayAngka(j - 1) Then Call tukar(ArrayAngka(j), ArrayAngka(j - 1)) End If Next j Next i End Sub Private Sub tukar(data1 As Long, data2 As Long) Dim temp As Long temp = data1 data1 = data2 data2 = temp End Sub And here's something a little bit quicker. Public Sub Insertionsort(nums() As Long) Dim i&, j&, k&, length& length = UBound(nums) For i = 1 To length j = nums(i) k = i Do While (k > 0) And (nums(k - 1) > j) nums(k) = nums(k - 1) k = k - 1 Loop nums(k) = j Next i End Sub it:Implementazioni di algoritmi/Insertion sort ru:Примеры реализации сортировки вставками