Sortowanie bąbelkowe - rosnąco i malejąco - problem z wyjściem poza zakres tablicy
Ostatnio zmodyfikowano 2014-03-20 22:44
inomushis Temat założony przez niniejszego użytkownika |
Sortowanie bąbelkowe - rosnąco i malejąco - problem z wyjściem poza zakres tablicy » 2014-03-20 20:35:53 Cześć! Zadanie wygląda na proste: Stworzyć funkcję, która sortuje tablice tab o rozmiarze n rosnąco lub malejąco. Funkcję porównującą dwa elementy przekazać przez wskaźnik. Kod źródłowy wygląda tak: #include<iostream>
using namespace std;
int porownaj_rosnaco( const int a, const int b ) {
if( a > b ) {
return 1;
}
return 0;
}
int porownaj_malejaco( const int a, const int b ) {
if( a < b ) {
return 1;
}
return 0;
}
void sortuj( int( * komparator )( int, int ), int * const tab, const unsigned int n ) {
int temp = 0;
for( unsigned int i = 0; i < n; i++ ) {
for( unsigned int j = 0; j < n; j++ ) {
if( komparator( tab[ j ], tab[ j + 1 ] ) == 1 ) {
temp = tab[ j + 1 ];
tab[ j + 1 ] = tab[ j ];
tab[ j ] = temp;
}
}
}
}
int main() {
int tablica[] = { 5, 9, 3, 1, 7, 5, 0, 17, 9, 4 };
unsigned int n = 10;
int * wsk = tablica;
int( * WSKfunkcja )( const int a, const int b );
cout << "Rosnaco:" << endl;
WSKfunkcja = porownaj_rosnaco;
sortuj( WSKfunkcja, wsk, n );
for( unsigned int i = 0; i < n; i++ ) {
cout << wsk[ i ] << endl;
}
cout << "Malejaco:" << endl;
WSKfunkcja = porownaj_malejaco;
sortuj( WSKfunkcja, wsk, n );
for( unsigned int i = 0; i < n; i++ ) {
cout << wsk[ i ] << endl;
}
return 1;
}
Wynik działania programu: Rosnaco: 0 1 3 4 5 5 7 9 9 17 Malejaco: 4231966 17 9 9 7 5 5 4 3 1 W przypadku sortowania rosnąco - wszystko działa poprawnie. W przypadku sortowania malejąco - pojawia się jedna liczba z kosmosu - bierze się ona z tab[j+1], (gdy j < n, otrzymujemy tab[n] - wychodzimy poza tablicę). Dlaczego jednak problem ten pojawia się tylko w sortowaniu malejącym i czy istnieje możliwość pozbycia się tego mankamentu? Zastosowanie warunku w pętli for (j<n-1) powoduje, że ostatni element nigdy nie jest sortowany :( |
|
Admixior |
» 2014-03-20 21:14:56 Obawiam się że w pierwszym przypadku jednak też nie działa poprawnie. Aby to sprawdzić dorzuć jakąś liczbę ujemną na koniec tablicy nie zmieniając innego kodu (zmienna "n" dalej jest równa tyle samo). Co do samego problemu to przeglądam kod. //edit: (to co napisałem wyżej też sprawdź) Wszystko to wina " + 1" w odwołaniu do tablicy i zakresu pracy pętli for( unsigned int i = 0; i < n; i++ ) {
for( unsigned int j = 0; j < n; j++ ) {
if( komparator( tab[ j ], tab[ j + 1 ] ) == 1 )
Krótka analiza 1.Ilość el. w tablicy to 10, więc ostatni indeks to 9 (tab[9]) 2.Ostatnie "j" na którym pętla środkowa pracuje to 9 (wynika z warunku j<n) 3.W pętli środkowej odwołanie się do tab dla obiektu max (tab[max] ) to "max = j + 1" 4.czyli innymi słowy tab[10], a to niezgodne z pkt nr. 1 4.można zmniejszyć warunek w pętli j< n-1 ale czy to wpłynie na dalszą część kodu? 5. po przeanalizowaniu kodu wzrokiem można powiedzieć że nie gdyż dla ostatniego el. tab[9] nie trzeba wykonywać żadnej operacji z elementem następnym (lub jakimś jeszcze innym) |
|
inomushis Temat założony przez niniejszego użytkownika |
» 2014-03-20 22:44:43 "Śmieć", który pojawiał się przy wyjściu poza tablicę był większy od największej liczby z sortowanej tablicy, stąd pierwsze sortowanie wydało się być prawidłowe - element ten nie pojawiał się bo nie był zamieniany z innymi:)
Zmiana warunku na j < n-1 pomogła - dzięki wielkie :) |
|
| « 1 » |