Sortowanie przez wstawianie

Z Wikipedii

Sortowanie przez wstawianie - prosty algorytm sortowania, o złożoności O(n²). Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:

• wydajny dla danych wstępnie posortowanych
• wydajny dla zbiorów o niewielkiej liczebności
• stabilny
• prosty do interpretacji

Algorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny. Szybkość tego algorytmu zależy od struktury danych wyjściowych i implementacji operacji wstawiania.

Schemat działania algorytmu:

1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
2. Weź dowolny element ze zbioru nieposortowanego.
3. Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
4. Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
5. Jeśli zbiór elementów nieuporządkowanych jest niepusty wróć do punkt 2.

Prosty algorytm sortowania przez wstawianie w języku Pascal:

procedure sort_insertion;
       var
               i,j:zakres;
               temp:longint;
       begin
       for i := 2 to ile do
               begin
               temp := dane[i];
               dane[0] := temp;
               j := i - 1;
               while temp < dane[j] do
                      begin
                      dane[j+1] := dane[j];
                      j := j - 1;
                      end;
               dane[j+1] := temp;
               end;
       end;

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

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

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

Prosty algorytm sortowania przez wstawianie w języku C++:

/* Przyjmuje wskaźnik do tablicy i wymiar tablicy */
void inSort(int *t, int n)
{
   int i,j; // Do iteracji
   int x;   // Zmienna pomocnicza
   for (i = n-2; i >= 0; i--)
   {
      j = i;
      x = t[i];               
      while ((j < n-1) && (x > t[j+1]))
      {
          t[j] = t[j+1];
          j++;
      }             
      t[j] = x;
   } 
}

Algorytm sortowania przez wstawianie w C#:

public static void InsertionSort(IComparable[] a)
{
  for(int i = 1; i < a.Length; i++)
  {
    IComparable x = a[i];
    int j = i - 1;
    while((j >= 0) && (x.CompareTo(a[j]) < 0))
    {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = x;
  }
}

Zobacz też:

• Sortowanie Shella
• Sortowanie przez wybieranie