Heapsort[sortowanie kopcowe] - problem
Ostatnio zmodyfikowano 2008-12-30 21:39
nnick Temat założony przez niniejszego użytkownika |
Heapsort[sortowanie kopcowe] - problem » 2008-12-30 11:52:04 Witam ponownie! Tym razem mam problem z algorytmem sortowania przez kopcowanie. Program prawie dziala. Prawie. Wiekszosc liczb poprawnie sortuje, problemy pojawiaja sie na koncu i poczatku kopca. Ostatnia liczba w "posortowanej" tabeli jest wogóle nie na miejscu, wczesniejsze 5-10 liczb tez jest nie do konca posortowane, z samym poczatkiem tabeli bywa podobnie. Prawdopodobnie wina lezy w funkcji heapmake. Oto kod #include <iostream>
using namespace std;
class heap
{
#define ROZM 100
int data[ ROZM ];
int last;
public:
heap()
{
last = ROZM - 1;
for( int i = 0; i < ROZM; i++ )
data[ i ] =( rand() % 255 ) + 1;
}
void listall()
{
for( int i = 0; i < ROZM; i++ )
{
cout << i << ":" << data[ i ] << '\n';
}
}
int parent( int el )
{
if( el > 0 )
{
if( el % 2 == 0 )
return( el / 2 ) - 1;
else return el / 2;
}
else return NULL;
}
int childleft( int el )
{
if(( 2 * el ) + 1 < ROZM )
return( 2 * el ) + 1;
else return NULL;
}
int childright( int el )
{
if(( 2 * el ) + 2 < ROZM )
return( 2 * el ) + 2;
else return NULL;
}
void upheap( int el )
{
swap( data[ el ], data[ parent( el ) ] );
}
void heapmake()
{
for( int i = 0; i < last; i++ )
{
if( data[ childleft( i ) ] >= data[ childright( i ) ] )
swap( data[ childleft( i ) ], data[ childright( i ) ] );
if( data[ i ] > data[ parent( i ) ] )
upheap( i );
}
}
void deletemax()
{
swap( data[ 0 ], data[ last ] );
last--;
}
void sort()
{
for( int i = 0; i < ROZM; i++ )
{
deletemax();
heapmake();
}
}
};
int main()
{
srand( static_cast < unsigned >( time( 0 ) ) );
heap kopiec;
kopiec.listall();
kopiec.heapmake();
cout << '\n';
kopiec.sort();
kopiec.listall();
return 0;
}
EDIT: jeden blad wychwycilem - w heapmake petla powinna wygladac tak: for(int i=last;i>0;i--), ale znowu pierwszy element laduje zawsze na ostatnim miejscu. Cala reszta dobrze sie sortuje. EDIT2: Rozwiazalem problem, temat zamykam |
|
DejaVu |
» 2008-12-30 18:32:57 Mógłbyś chociaż dać komuś rozwiązanie, skoro już temat założyłeś :) a tak na moje oko to używasz we wszystkich pętlach stałej zamiast zmiennej last. |
|
nnick Temat założony przez niniejszego użytkownika |
» 2008-12-30 21:39:55 ok, oto kod: #include <iostream>
using namespace std;
class heap
{
#define ROZM 290
int data[ ROZM ];
int last;
public:
heap()
{
last = ROZM - 1;
for( int i = 0; i < ROZM; i++ )
data[ i ] =( rand() ) + 1;
}
~heap()
{
delete data;
}
void listall()
{
for( int i = 0; i < ROZM; i++ )
{
cout << i << ":" << data[ i ] << '\n';
}
}
int parent( int el )
{
if( el > 0 )
{
if( el % 2 == 0 )
return( el / 2 ) - 1;
else return el / 2;
}
else return NULL;
}
void upheap( int el )
{
swap( data[ el ], data[ parent( el ) ] );
}
void heapmake()
{
for( int i = last; i > 0; i-- )
{
if( data[ i ] > data[ parent( i ) ] )
upheap( i );
}
}
void deletemax()
{
swap( data[ 0 ], data[ last ] );
last--;
}
void sort()
{
for( int i = 0; i < ROZM; i++ )
{
heapmake();
deletemax();
}
}
};
int main()
{
srand( static_cast < unsigned >( time( 0 ) ) );
heap kopiec;
kopiec.sort();
kopiec.listall();
system( "pause" );
return 0;
}
last nie jest stałą, przy każdym wykonaniu deletemax zmniejsza swoja wartosc |
|
| « 1 » |