maciek1o3s Temat założony przez niniejszego użytkownika |
BubbleSort - pytanie o podstawy » 2015-10-18 21:24:24 Hej, mam to w książce od algorytmów: void BubbleSort()
{
for( int i = 1; i < n; i++ )
for( int j = 1; j <= n - i; j++ )
if( tab[ j ] > tab[ j + 1 ]
{
int x = tab[ j ];
tab[ j ] = tab[ j + 1 ];
tab[ j + 1 ] = x;
}
} Chciałem się zapytać czy tu aby na pewno wszystko gra. Weźmy np. ciąg 2,1,3,5,4. Jeśli zaczniemy sortowanie od i=1 czyli w tym przypadku od wartosci "1", to otrzymamy ciąg 2,1,3,4,5 bo nie widzę opcji aby w powyższym skrypcie porównywać i=0 z i=1. Czy nie powinno być w warunkach dla forów i=0 i j=0? Ponadto czemu w drugim forze mamy warunek j<=n-i, nie powinno być j<=n-1? Druga sprawa to skrypt z Wiki (https://pl.wikipedia.org/wiki/Sortowanie_b%C4%85belkowe): procedure bubbleSort( A : lista elementow do posortowania )
n = liczba_elementow(A)
do
for (i = 0; i < n-1; i++) do:
if A[i] > A[i+1] then
swap(A[i], A[i+1])
end if
end for
n = n-1
while n > 1
end procedure Czemu nie można zapisać samego: for (i = 0; i < n-1; i++) do:
if A[i] > A[i+1] then
swap(A[i], A[i+1])
end if
end for Nie wystarczyłoby? |
|
michal11 |
» 2015-10-18 21:37:59 Sprawdź lepiej w twojej książce czy nie ma gdzieś adnotacji, że tablice są indeksowane od 1, jeżeli nie, to jest to błąd. | Ponadto czemu w drugim forze mamy warunek j<=n-i, nie powinno być j<=n-1? |
Wystarczy sprawdzać do n-i ponieważ później już wiadomo, że elementy są posortowane, zrób sobie symulację to zobaczysz o czym mówię. for (i = 0; i < n-1; i++) do:
if A[i] > A[i+1] then
swap(A[i], A[i+1])
end if
end for |
Nie możesz tak zrobić ponieważ nie dostaniesz posortowanego zbioru. W takim wypadku porównujesz tylko sąsiadujące ze sobą elementy ale tylko raz. Znowu, zrób sobie symulację to zobaczysz. |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-10-18 21:49:41 Dzieki za szybką odpowiedź. Robię więc symulację dla tablicy: 2,1,3,5,4 i=1 tab[1]>tab[2] wiec zamieniamy i mamy nowa tablice: 1,2,3,5,4 i=2 tab[2] nie jest wieksze od tab[3] wiec przeskakujemy i=3 warunek j<= n-i juz nie jest spelniony.. bo mamy j=3 <= 5-3 czyli bzdura, a wiec zostawiamy petle zostaje nam: 1,2,3,5,4 Nie jest to posortowany ciąg/tablica. Gdzie popełniam błąd? A jeśli chodzi o ten kod: procedure bubbleSort( A : lista elementow do posortowania )
n = liczba_elementow(A)
do
for (i = 0; i < n-1; i++) do:
if A[i] > A[i+1] then
swap(A[i], A[i+1])
end if
end for
n = n-1
while n > 1
end procedure/ to tutaj mamy do while, tak? To wg mnie też coś nie gra, bo while jest dla n > 1 , czyli jak wystartujemy z i=0 to while nie zostanie spełnione i caly algorytm sie wyłączy do pierwszym przejsciu petli (bo zeby algorytm przeorał jeszcze raz to co jest miedzy "do" a "while" to argument z while musi byc spelniony, zle mowie? |
|
carlosmay |
» 2015-10-18 22:38:19 Robię więc symulację dla tablicy: 2,1,3,5,4
i=1
tab[1]>tab[2]
wiec zamieniamy i mamy nowa tablice:
1,2,3,5,4
|
Na dzień dobry: tab[1] = 1, tab[2] = 3 więc tab[1] > tab[2] , nie ma mowy o jakiejkolwiek zamianie w pierwszym przebiegu. |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-10-18 22:41:57 Nie bzdura, na początku ustaliliśmy że moja tablica zaczyna się od i=1 a nie i=0.
Czekam na dalsze sugestie. |
|
michal11 |
» 2015-10-18 22:45:55 Wybrałeś akurat taki przykład dla którego to zadziała, spróbuj chociażby dla takiego: 5,4,3,2,1 |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-10-18 23:01:51 Słucham? Ja wybrałem przykład dla którego to własnie nie działa. Sprobuj dla: 2,1,3,5,4 zaden z tych algorytmow nie dziala.. Tu mam kod: void BubbleSort()
{
for( int i = 1; i < n; i++ )
for( int j = 1; j <= n - i; j++ )
if( tab[ j ] > tab[ j + 1 ]
{
int x = tab[ j ];
tab[ j ] = tab[ j + 1 ];
tab[ j + 1 ] = x;
}
} Robię symulację dla tablicy: 2,1,3,5,4 i=1 tab[1]>tab[2] wiec zamieniamy i mamy nowa tablice: 1,2,3,5,4 i=2 tab[2] nie jest wieksze od tab[3] wiec przeskakujemy i=3 warunek j<= n-i juz nie jest spelniony.. bo mamy j=3 <= 5-3 czyli bzdura, a wiec zostawiamy petle zostaje nam: 1,2,3,5,4 Nie jest to posortowany ciąg/tablica. Gdzie popełniam błąd? |
|
michal11 |
» 2015-10-18 23:13:36 Wrzuciłeś 3 kody, skąd mam widzieć który akurat sprawdzasz ? Myślałem, że ostatni.
Błąd robisz taki, że operujesz na i a powinieneś na j, źle przeprowadzasz symulację. |
|
| « 1 » 2 3 4 |