Sortowanie przez wstawianie jest kolejnym prostym algorytmem działającym w złożności O(n[kwadrat]).

Weźmy przykładową tablicę o elementach [3,9,5,2,4].

Zaczynamy od drugiego elementu tablicy i sprawdzamy czy jest on mniejszy od elemetu po lewej stronie. Jeśli tak to zamieniamy je miejscami i sprawdzamy następny, aż napotkany element będzie miał wartość mniejszą od obecnie wstawianego.

Po pierwszym kroku cyfra 9 pozostanie na swoim miejscu ponieważ zachodzi warunek 3<9.

Teraz bierzemy 5 i sprawdzamy czy jest mniejsza od poprzedniego elementu, czyli 9. Ponieważ jest to zamieniamy miejscami te elementy. Następnie sprawdzamy czy znowu 5 jest mniejsza od poprzednika - nie jest a więc zostaje na tej pozycji (tablica wygląda tak [3,5,9,2,4]).

Następnie bierzemy kolejny element i dopóki poprzednie elementy są większe od 2-ki to zamieniamy je miejscami. Tablica zmieni się następująco:

[3,5,9,2,4] -> [3,5,2,9,4] -> [3,2,5,9,4] -> [2,3,5,9,4]

Ostatni element podobnie zamieniamy miejscami z poprzednikami, aż ich wartość będzie niewiększa od wstawianego elementu.


Sortowanie to jest podobne do bąbelkowego prwada??


Teraz czas na implementację w C++:

void wstawianie(int *tab, int size) // To samo co w poprzednim algorytmie, czyli: *tab wskaźnik, który przchowuje cyfry i size czyli rozmiar.
{
 for(int i=1; i<size ;++i)        //jedziemy od drugiego elementu do ostatniego
  {
   int tmp = tab[i];             //zmienna pomocnicza, która zapamiętuje tab[i]
   int j=i-1;                        //indeks poprzednika
   while((j>=0) && (tablica[j]>tmp)) //dopóki istnieje poprzednik
    {                                //i jego wartość jest większa
     tablica[j+1] = tablica[j];      //przesuń poprzedni element w prawo
     --j;
    }
   tablica[j+1] = tmp;               //wstaw  element w odpowiednim miejscu
  }
}