ALGORYTM 01 SORTOWANIE PRZEZ PROSTE WSTAWIANIE
Opis algorytmu
Algorytm sortowania przez proste wstawianie rozpoczynamy od podzielenia ciągu porównywanych
elementów
a1,a2,..., an
na dwa ciągi:
a) wynikowy a1,a2,...,ai-1,
b) zródłowy ai,ai +1,...,an .
W każdym kroku, począwszy od i = 2, 3, & , n, i ty element ciągu zródłowego przenosimy do ciągu
wynikowego wstawiając w odpowiednie miejsce (czyli w takie miejsce, żeby wszystkie elementy ciągu wyni-
kowego pozostawały ułożone w odpowiedniej kolejności od wartości najmniejszej do największej).
W ogólności możemy sformułować algorytm w następujący sposób:
for (i=2; i<=n; i++)
{
Ustaw x = a[i];
Wstaw x w odpowiednim miejscu ciągu wynikowego
}
Algorytm szukania odpowiedniego miejsca może polegać na stosowaniu na przemian porównań i prze-
sunięć, czyli tzw. przesiewania x poprzez porównanie go z następnym elementem aj . Wówczas albo wsta-
wiamy x, w odpowiednie miejsce, albo przesuwamy element aj na prawo i sprawdzamy dalej przesuwając się
w lewo. Warunki kończące proces przesiewania możemy sformułować następująco:
a) znaleziono element aj o wartości mniejszej niż x,
b) osiągnięto lewy koniec ciągu wynikowego.
Poprawność działania algorytmu możemy zapewnić rozszerzając zakres tablicy o pozycję z indeksem 0,
na którą w każdym bieżącym kroku metody wstawiamy element x.
Algorytm (w języku C++)
for (i=2; i<=n; i++)
{
x = a[i];
a[0] = x;
j = i - 1;
while (x < a[j]) {
a[j+1] = a[j];
j = j - 1;
};
a[j+1] = x;
}
Przykład
Niech dany będzie następujący ciąg wartości:
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
Wartości
44 55 12 42 94 18 6 67
początkowe
i = 2 44 55 12 42 94 18 6 67
i = 3 12 44 55 42 94 18 6 67
i = 4 12 42 44 55 94 18 6 67
i = 5 12 42 44 55 94 18 6 67
i = 6 12 18 42 44 55 94 6 67
i = 7 6 12 18 42 44 55 94 67
i = 8 6 12 18 42 44 55 67 94
i = 2
x = a[2] = 55
a[0] = x = 55
j = i 1 = 1
// Pętla while ---------------------- //
Czy x < a[1] ? (Czy 55 < 44 ?)
Nie (wychodzimy z pętli while)
// ---------------------------------- //
a[2] = 55
i = 3
x = a[3] = 12
a[0] = x = 12
j = i 1 = 2
// Pętla while ---------------------- //
Czy x < a[2] ? (Czy 12 < 55 ?)
Tak
a[3] = a[2] = 55
j = 1
Przesuwamy a[2] o jedną pozycję w prawo i kontynuujemy pętlę while
Czy x < a[1] ? (Czy 12 < 44 ?)
Tak
a[2] = a[1] = 44
j = 0
Przesuwamy a[1] o jedną pozycję w prawo i kontynuujemy pętlę while
Czy x < a[0] ? (Czy 12 < 12 ?)
Nie (wychodzimy z pętli while)
// ---------------------------------- //
a[1] = 12
...
Wyszukiwarka
Podobne podstrony:
Sortowanie przez wstawienieW03 sortowania prosteSortowanie 02 Wstawianie polowkowesortowanie przez wstawianiesortowanie przez wstawianie binarneAPP Proste Metody Sortowania Tablict informatyk12[01] 02 101r11 012570 01introligators4[02] z2 01 nBiuletyn 01 12 2014beetelvoiceXL?? 01012007 01 Web Building the Aptana Free Developer Environment for Ajax9 01 07 drzewa binarnewięcej podobnych podstron