[C++] Sortowanie kubełkowe liczb naturalnych za pomocą kopca
Ostatnio zmodyfikowano 2014-11-20 14:26
Diegogo Temat założony przez niniejszego użytkownika |
[C++] Sortowanie kubełkowe liczb naturalnych za pomocą kopca » 2014-11-19 23:09:10 Zadaniem było napisać sortowanie kubełkowe sortujące liczby naturalne mniejsze od 1000, tak żeby kubełkami były kopce i każdy kopiec miał zakres 100. Sortowanie miało zmieniać tablicę a nie zwracać nową. #include<iostream> #include"heap.h" #include<cmath> using namespace std; Heap * kubelki( int * tab, int n ) { Heap kubel[ 11 ]; int p; for( int k = 0; k < n; k++ ) { p = tab[ k ] / 100; kubel[ p + 1 ].InsertHeap( tab[ k ] ); } return kubel; } int * sort( Heap * kubel, int n ) { int i = n - 1; int k = 10; int * tab = new int[ n ]; for( k; k > 0; k-- ) { while( kubel[ k ].HeapSize != 0 ) { tab[ i ] = kubel[ k ].DeleteMax(); i--; } } return tab; } void kubsort( int * tab, int n ) { Heap * kubel = new Heap[ 11 ]; kubel = kubelki( tab, n ); tab = sort( kubel, n ); }
int main() { int n = 23; int * test = new int[ n ]; cout << "Nieposortowane elementy tablicy" << endl; for( int i = 0; i < n; i++ ) { test[ i ] = rand() % 1000; cout << test[ i ] << " "; } cout << endl; cout << "Nastepuje rozdzielenie do kubelkow" << endl; Heap * testkub = new Heap[ 11 ]; testkub = kubelki( test, n ); for( int i = 1; i <= 10; i++ ) { cout << "Elementy kubelka nr " << i << endl; testkub[ i ].PrintHeap(); cout << endl; } kubsort( test, n ); for( int i = 0; i < n; i++ ) { cout << test[ i ] << " "; } cout << endl; return 0; } Do tego klasa kopiec i jej funkcje #include <iostream> using namespace std;
const static int Max = 200;
class Heap { public: int HeapSize; int H[ Max + 1 ]; Heap() : HeapSize( 0 ) { } void UpHeap( int k ) { int x; int i =( int )( k / 2 ); x = H[ k ]; while( i > 0 ) if( H[ i ] < x ) { H[ k ] = H[ i ]; k = i; i =( int )( i / 2 ); } else break; H[ k ] = x; } void InsertHeap( int x ) { HeapSize++; H[ HeapSize ] = x; UpHeap( HeapSize ); } Klasa ma zdefiniowane więcej funkcji, ale że nie są używane to ich nie wklejam W mainie jest napisany test, w sortowaniu pojawiają się "śmieci" , a po wrzuceniu ich w kubełki program przestaje działać. Sprawdzałem sortowania znajomych i opierają się na tym samym mechanizmie, szukałem błędu ja, szukali oni, mam nadzieję, że ktoś tutaj mnie oświeci. Pozdrawiam Diegogo |
|
Wgbg |
» 2014-11-20 14:25:01 Podaj ciało metody DeleteMax. int * sort( Heap * kubel, int n ) { int i = n - 1; int k = 10; int * tab = new int[ n ]; for( k; k > 0; k-- ) { while( kubel[ k ].HeapSize != 0 ) { tab[ i ] = kubel[ k ].DeleteMax(); i--; } }
|
|
darko202 |
» 2014-11-20 14:26:47 w metodzie Heap * kubelki( int * tab, int n ) //wrzuca wartosci w kubelki { Heap kubel[ 11 ]; .... return kubel; } a kubel jest zmienną lokalną
to prowadzi do błędu w linii testkub = kubelki( test, n );
|
|
« 1 » |