Sortowanie przez wstawianie

Question

int pom, j;
     for(int i=1; i<n; i++)
     {
             //wstawienie elementu w odpowiednie miejsce
             y = tab[i]; //ten element będzie wstawiony w odpowiednie miejsce
             j = i-1;
             
             //przesuwanie elementów większych od y
             while(j>=0 && tab[j]>y) 
             {
                        tab[j+1] = tab[j]; //przesuwanie elementów
                        --j;
             }
             tab[j+1] = y;

Analizuje algorytm i do czego służy tutaj podstawienie tab[j+1] = y; ?

 

Answer 1

tab[j+1] służy tu do wstawienia liczby y w odpowiednie miejsce ponieważ pętla while przesuwa liczby większe od niej nadpisując liczbę y.

Najlepiej na przykładzie na kartce spróbuj, zawsze działa

Comments

A j= i-1 to ilość razy ile wykonamy porównanie dla 0 zawsze będą posortwane tak jakby ?

---

Tak, to tak jakby maksymalna ilość porównań do wykonania