[Algorytmy] Sortowanie przez wstawianie - niezmiennik pętli

PiotrWP
Użytkownik
Użytkownik
Posty: 293
Rejestracja: 7 paź 2014, o 21:15
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 124 razy

[Algorytmy] Sortowanie przez wstawianie - niezmiennik pętli

Post autor: PiotrWP »

Kod: Zaznacz cały

for j = 2 to A.length
     key = A[ j ]
     i = j - 1
while i > 0 and A[ i ] > key
     A[ i + 1 ] = A[ i ]
     i = i - 1
A[ i + 1 ] = key
Niezmiennik dla pętli for mam zdefiniowany jako : " Na początku każdej iteracji pętli for w wierszach 1-7 fragment tablicy A[1...j-1] składa się z elementów znajdujących się pierwotnie w A[1...j-1], ale w porządku niemalejącym "

Nie rozumiem tego stwierdzenia.Co to znaczy "pierwotnie" ? Jak jest \(\displaystyle{ j}\) - iteracja to chodzi o \(\displaystyle{ j-1}\) iterację czy pierwotnie w sensie jeszcze przed pierwszą iteracją ?
Ostatnio zmieniony 18 lut 2016, o 18:45 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
bakala12
Użytkownik
Użytkownik
Posty: 3044
Rejestracja: 25 mar 2010, o 15:34
Płeć: Mężczyzna
Lokalizacja: Gołąb
Podziękował: 24 razy
Pomógł: 513 razy

[Algorytmy] Sortowanie przez wstawianie - niezmiennik pętli

Post autor: bakala12 »

Pierwotnie w sensie przed pierwszą iteracją. Chodzi o porządek danych na wejściu.
Przykładowo przeanalizuj sobie jak działa algorytm dla ciągu \(\displaystyle{ 2,4,5,3,1}\).
1. \(\displaystyle{ 2,4,5,3,1}\)
2. \(\displaystyle{ 2,4,5,3,1}\)
3. \(\displaystyle{ 2,3,4,5,1}\)
4. \(\displaystyle{ 1,2,3,4,5}\)
Zauważ, że na początku \(\displaystyle{ j}\)-tej iteracji pierwszych \(\displaystyle{ j-1}\) elementów jest już uporządkowanych (są w dobrej kolejności). Ale później pomiędzy nie mogą zostać wstawione jeszcze dalsze elementy. Tak jak tutaj, był kawałek \(\displaystyle{ 2,4,5}\) (uporządkowany dobrze), ale później wpadła tam jeszcze trójka.
ODPOWIEDZ