Problem z SelectionSortem - pierwsza wartosc tablicy we wszystkich pozycjach
Ostatnio zmodyfikowano 2015-11-23 16:23
maciek1o3s Temat założony przez niniejszego użytkownika |
Problem z SelectionSortem - pierwsza wartosc tablicy we wszystkich pozycjach » 2015-11-21 23:26:59 void ss( int tab[], int n )
{
bool flag;
for( int i = 0; i < n; i++ )
{
int min = tab[ i ];
for( int j = i + 1; j < n; j++ )
{
if( min > tab[ j ] )
{
flag = true;
tab[ j ] = min;
}
if( flag == true )
{
int temp = tab[ i ];
tab[ i ] = min;
tab[ j ] = temp;
}
}
}
} przykładowa tablica 5 4 3 8 7 9 zamienia sie na 5 5 5 5 5 5 Jak powinien wyglądać algorytm, żeby to działało? Daje boola bo chce wykonać swapa jedynie kiedy została znaleziona mniejsza wartość niż wyjsciowa. |
|
carlosmay |
» 2015-11-22 01:03:55 ma niezdefiniowane zachowane, 'flag' jest niezainicjalizowana. |
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-11-22 01:24:01 A mógłbyś powiedzieć coś więcej? Wszystkie tutoriale i opisy pokazują przykłady użycia boola i flag, które nijak mi pomagają tu.
Innymi słowy, czy mógłbyś poprawić mój kod, bo nie mam zielonego pojęcia gdzie jest błąd? |
|
carlosmay |
» 2015-11-22 02:28:29 | Daje boola bo chce wykonać swapa jedynie kiedy została znaleziona mniejsza wartość niż wyjsciowa. |
Niepotrzebnie. Zamiana wykonywana jest dopiero po wyjściu z wewnętrznej pętli. Łatwiej napisać kod od nowa niż przerabiać. void ss( int tab[], int n )
{
int k;
for( int i = 0; i < n; i++ )
{
k = i;
for( int j = i + 1; j < n; j++ )
{
if( tab[ j ] < tab[ k ] )
k = j;
}
int temp = tab[ k ];
tab[ k ] = tab[ i ];
tab[ i ] = temp;
}
}
|
|
maciek1o3s Temat założony przez niniejszego użytkownika |
» 2015-11-22 15:53:10 Tak ta opcja jest latwiejsza i szybka i ja juz znam. Robilismy jednak na uczelni na cwiczeniach wersje z boolem. Problem w tym ze piszemy w pseudokodzie a wiec generalnie tak ze to w kompilatorach nie dziala. Przeczytalem pare przykladow z boolem i niestety nie umiem go tutaj zastosowac poprawnie. Czy masz moze wiec pomysl jak napisacto z boolem? Pytam z czystej ciekawosci bo to jest dosc przydatna opcja - jesli zaszla jakas zmiana w algorytmie to wykonaj cos tam. |
|
carlosmay |
» 2015-11-22 19:10:49 | Tak ta opcja jest latwiejsza i szybka i ja juz znam. |
To po co kombinować? | Robilismy jednak na uczelni na cwiczeniach wersje z boolem. |
Na Selection Sort również? | Przeczytalem pare przykladow z boolem |
Czy możesz przytoczyć jakiś przykładowy kod? | Czy masz moze wiec pomysl jak napisacto z boolem? |
Nie widzę potrzeby. | Pytam z czystej ciekawosci bo to jest dosc przydatna opcja |
Do czego konkretnie? | jesli zaszla jakas zmiana w algorytmie to wykonaj cos tam. |
Co konkretnie miałaby wykrywać 'flaga'? |
|
michal11 |
» 2015-11-22 19:30:53 if( min > tab[ j ] )
{
flag = true;
tab[ j ] = min;
}
if( flag == true )
{
int temp = tab[ i ];
tab[ i ] = min;
tab[ j ] = temp;
}
|
Tu i tak ta flaga nie ma sensu, można to równie dobrze napisać tak: if( min > tab[ j ] )
{
flag = true;
tab[ j ] = min;
int temp = tab[ i ];
tab[ i ] = min;
tab[ j ] = temp;
}
|
|
bombatom69 |
» 2015-11-23 16:23:31 | Daje boola bo chce wykonać swapa jedynie kiedy została znaleziona mniejsza wartość niż wyjsciowa. |
Twojemu wykładowcy albo brakuje wyobraźni albo nie słyszał nawet o podstawach analizy algorytmów albo czegoś nie zrozumiałeś. Nie ma jednak wątpliwości, że jeśli taka wersja istnieje(jakimś dziwnym zrządzeniem losu), to będzie Ci ją bardzo trudno znaleźć(sensowną), wiem bo widziałem ich ... no powiedzmy: sporo :) Ten algorytm nie daje możliwości przyspieszania, przynajmniej nie elementarnego, to jedna z jego licznych wad. Problem jest taki, że zamiana nie znajduje się w najbardziej zagnieżdżonej pętli i przy losowym wejściu przypisanie flagi będzie bardziej kosztowne niż zysk na warunkowym swapie. Wniosek jest mniej więcej taki: Z faktu, że wersję nazywasz trudniejszą, niestety nie wynika, że jest ona lepsza. |
|
| « 1 » |