Ten rodzaj sortowania możemy porównać do układania kart pokerzysty. Pierwszą kartę wstawiamy w odpowiednie miejsce przesuwając pozostałe, następną także wstawiamy między odpowiednie karty i tak układamy zestaw kart.
Ciąg liczb:
2, 5, 3, 0, 7, 1
Strategia algorytmu:
Rozpoczynamy od drugiego elementu, czyli 5 i porównujemy go z elementami poprzedzającymi – w tym przykładzie poprzedza tylko liczba 2
Jeśli napotkamy liczbę większą, to musimy przesunąć ją o jeden w prawo.
Czynność tą powtarzamy do momentu napotkania liczby niemniejszej lub gdy skończą nam się liczby (nie będzie spełniony warunek j>=0).
W następnym kroku wstawiamy naszą liczbę w odpowiednie miejsce i otrzymujemy podzbiór uporządkowany.
Powyższe czynności powtarzamy dla reszty wyrazów.
Dla przykładowego ciągu wygląda to następująco:
2 5 3 0 7 1 – liczba 5
pozostaje na swoim miejscu (dwa pierwsze elementy są posortowane)
2 3 5 0 7 1 – liczba 3
zostaje wstawiona między liczby 2 i 5 (trzy pierwsze elementy są posortowane)
0 2 3 5 7 1 – liczba 0 zostaje wstawiona na początek (cztery pierwsze elementy są posortowane)
0 2 3 5 7 1 – liczba 7
pozostaje na swoim miejscu (pięć pierwszych elementów jest posortowanych)
0 1 2 3 5 7 – liczba 1
zostaje wstawiona między liczby 0 i 2
- . (otrzymujemy zbiór uporządkowany)
Sortowanie przez wstawianie można zaliczyć do atrakcyjniejszych algorytmów. Chociaż jego złożoność jest rzędu
O(n2)
a więc nie należy do najszybszych, to algorytm ma swoje zalety:
- jest stabilny
- bardzo dobrze zachowuje się w przypadku zbioru posortowanego lub częściowo posortowanego
- prosty w implementacji
- dobrze radzi sobie z niedużymi zbiorami
Algorytm najwięcej porównań elementów musi wykonać w przypadku pesymistycznej wersji zbioru danych (elementy posortowane są malejąco):
0+1+2+3+4+5…+n=n(n-1)/2
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void sortwstaw(int *tab, int n)
{
int pom, j;
for(int i=1; i=0 && tab[j]>pom)
{
tab[j+1] = tab[j]; //przesuwanie elementów
–j;
}
tab[j+1] = pom; //wstawienie pom w odpowiednie miejsce
}
}
int main()
{
int n; // Zmienna typu int o nazwie n wskazuje na ilosc elementow tablicy.
int *tablica; // Tworzymy tablice dynamiczna. Wymagany wskaznik.
cout << ” Ilość elementów tablicy: „; cin >> n; // Okreslamy wielkosc tablicy.
srand(time(NULL)); // Pseudolosowe wypelnienie tablicy.
tablica = new int [n]; // Dynaminczne utworzenie tablicy.
for (int i=0; i<n; i++)
{
tablica [i] = rand()%50; // Okreslamy przedzial losowosci liczb od 0-9.
cout << ” Tabblica ” << i+1 << „: ” << tablica [i] << endl;
}
sortwstaw(tablica,n);
cout << ” \n Liczby posortowane: „;
for (int i=0; i<n; i++)
//Wypisanie liczb posorotwanych.
cout << tablica [i] << ” „;
cout << '\n’;
delete [] tablica;
}