algorytm.org

sortowanie babelkowe poprawnosc



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Forum www.algorytm.org :: Algorytmy sortowania
Witaj Gość   
[Zarejestruj się]  
[Zaloguj się]
Zamieść odpowiedź
 sortowanie babelkowe poprawnosc

photo
Witam. Mam taki problem. Mam zadany algorytm sortowania babelkowego z wartownikiem o to pseudokod:

SORT_BUBBLE(n,A)
wart <- n
while wart >= 2
do k <-1
for i <- 1 to wart - 1
do if A[i] > A[i+1]
then A[i] <-> A[i+1]
k <- i
wart <- k

Mam udowodnić poprawność algorytmu
Udało mi się zdefiniować niezmiennik wewnętrznej pętli for oraz udowodnić 3 kroki muszę to samo zrobić dla tej zewnętrznej pętli while no i tutaj się zaciąłem. Może pomożecie zdefiniować chociaż niezmiennik tej zewnętrznej petli ??? Pozdrawiam

Niezmiennik pętli for:
Na początku każdej iteracji pętli for fragment tablicy A[wart ... n] jest posortowany

Niezmiennik pętli while: ???
Cytuj
photo
Sorki trochę kod się trochę poprzesuwał. Jeśli ktoś ma jakiś pomysł to proszę o pomoc.
Cytuj
Zamieść odpowiedź Strona # 
Szybka odpowiedź

Kod:    


Powered by ccBoard