» Forum » Programowanie » [C, C++] Szukam pomocy

Sortowanie przez kopcowanie - usuwanie kopca

Ostatnio zmodyfikowano 2014-08-27 16:23

Mikilll

Temat założony przez niniejszego użytkownika

» 2014-08-27 10:38:32

#include <iostream>

using namespace std;

int MniejszeDziecko( int rodzic, int rozmiarKopca, int kopiec[] )
{
int leweDziecko = 2 * rodzic;
int praweDziecko = 2 * rodzic + 1;
if( leweDziecko > rozmiarKopca )
   return 0;

if( praweDziecko > rozmiarKopca and kopiec[ leweDziecko ] < kopiec[ praweDziecko ] )
   return leweDziecko;

return praweDziecko;
}

void UsunKorzen( int rozmiar, int kopiec[] )
{
int rozmiarKopca = rozmiar + 1;
int ostatni = kopiec[ rozmiarKopca ];
rozmiarKopca--;
int x = 1;
int c = MniejszeDziecko( 1, rozmiarKopca, kopiec );
while( c and kopiec[ c ] < ostatni )
{
kopiec[ x ] = kopiec[ c ];
x = c;
c = MniejszeDziecko( c, rozmiarKopca, kopiec );
}
kopiec[ x ] = ostatni;
}

int main()
{
const int rozmiar = 7;
int kopiec[ rozmiar + 1 ] = { 0, 2, 5, 3, 7, 6, 4, 5 };
int tab[ rozmiar ] = { 0 };
for( int i = 0; i < rozmiar; i++ )
{
tab[ i ] = kopiec[ 1 ];
UsunKorzen( rozmiar, kopiec );
}
for( int i = 0; i < rozmiar; i++ )
   cout << tab[ i ] << " ";

return 0;
}

Napisałem tu algorytm usuwanie kopca. Kopiec indeksowany jest od 1 i zapisany jest w tablicy kopiec (element na zerowej pozycji 0 ignorujemy). Program usuwa kopiec i zapisuje już wtedy posortowane dane do tablicy tab. Program źle działa i wyświetla 2 2 2 2 2 2 2 tak jakby w ogóle nie wykonywał funkcji UsunKorzen. Ktoś wie o co chodzi?

P-116241

pekfos

» 2014-08-27 10:57:15

Za każdym razem wykonujesz usuwanie korzenia na tej samej ilości elementów.

if( praweDziecko > rozmiarKopca and kopiec[ leweDziecko ] < kopiec[ praweDziecko ] )

int ostatni = kopiec[ rozmiarKopca ];

Wychodzisz poza tablice.

P-116244

Mikilll

Temat założony przez niniejszego użytkownika

» 2014-08-27 11:10:39

Dzięki za informację. Tylko czy masz jakiś pomysł jak to zrobić bez używania zmiennych globalnych. Bo właśnie ten zmniejszający się rozmiar kopca o 1 co iterację jest dla mnie problemem w implementacji.

I miałeś rację, że w jednej linijce wychodziłem poza rozmiar kopca. Powinno być

int ostatni = kopiec[ rozmiarKopca - 1 ];

EDIT: Udało mi się wymyślić coś takiego.

#include <iostream>

using namespace std;

int MniejszeDziecko( int rodzic, int & rozmiarKopca, int kopiec[] )
{
int leweDziecko = 2 * rodzic;
int praweDziecko = 2 * rodzic + 1;
if( leweDziecko > rozmiarKopca )
   return 0;

if( praweDziecko > rozmiarKopca and kopiec[ leweDziecko ] < kopiec[ praweDziecko ] )
   return leweDziecko;

return praweDziecko;
}

void UsunKorzen( int & rozmiarKopca, int kopiec[] )
{
int ostatni = kopiec[ rozmiarKopca - 1 ];
rozmiarKopca--;
int x = 1;
int c = MniejszeDziecko( 1, rozmiarKopca, kopiec );
while( c and kopiec[ c ] < ostatni )
{
kopiec[ x ] = kopiec[ c ];
x = c;
c = MniejszeDziecko( c, rozmiarKopca, kopiec );
}
kopiec[ x ] = ostatni;
}

int main()
{
const int rozmiar = 7;
int rozmiarKopca = rozmiar + 1;
int kopiec[ rozmiar + 1 ] = { 0, 2, 5, 3, 7, 6, 4, 5 };
int tab[ rozmiar ] = { 0 };
for( int i = 0; i < rozmiar; i++ )
{
tab[ i ] = kopiec[ 1 ];
UsunKorzen( rozmiarKopca, kopiec );
}
for( int i = 0; i < rozmiar; i++ )
   cout << tab[ i ] << " ";

return 0;
}

Teraz zmienna rozmiarKopca jest przekazywana przez referencję, więc rozmiarKopca będzie zmniejszana w całym programie. Program mimo to dalej nie sortuje prawidłowo tablicy. Ktoś wykombinowałby o co chodzi?

P-116245

pekfos

» 2014-08-27 14:37:27

if( praweDziecko > rozmiarKopca and kopiec[ leweDziecko ] < kopiec[ praweDziecko ] )

Dalej wychodzisz poza tablicę.

P-116271

Mikilll

Temat założony przez niniejszego użytkownika

» 2014-08-27 15:26:38

#include <iostream>

using namespace std;

int MniejszeDziecko( int rodzic, int & rozmiarKopca, int kopiec[] )
{
int leweDziecko = 2 * rodzic;
int praweDziecko = 2 * rodzic + 1;
if( leweDziecko >= rozmiarKopca )
   return 0;

if( praweDziecko >= rozmiarKopca and kopiec[ leweDziecko ] < kopiec[ praweDziecko ] )
   return leweDziecko;

return praweDziecko;
}

void UsunKorzen( int & rozmiarKopca, int kopiec[] )
{
int ostatni = kopiec[ rozmiarKopca - 1 ];
rozmiarKopca--;
int x = 1;
int c = MniejszeDziecko( 1, rozmiarKopca, kopiec );
while( c and kopiec[ c ] < ostatni )
{
kopiec[ x ] = kopiec[ c ];
x = c;
c = MniejszeDziecko( c, rozmiarKopca, kopiec );
}
kopiec[ x ] = ostatni;
}

int main()
{
const int rozmiar = 7;
int rozmiarKopca = rozmiar + 1;
int kopiec[ rozmiar + 1 ] = { 0, 2, 5, 3, 7, 6, 4, 5 };
int tab[ rozmiar ] = { 0 };
for( int i = 0; i < rozmiar; i++ )
{
tab[ i ] = kopiec[ 1 ];
UsunKorzen( rozmiarKopca, kopiec );
}
for( int i = 0; i < rozmiar; i++ )
   cout << tab[ i ] << " ";

return 0;
}

No, dobra. Poprawiłem. Teraz nie wychodzę już poza rozmiar kopca, ale program dalej źle sortuje zwłaszcza na końcu tablicy.

P-116273

pekfos

» 2014-08-27 16:14:10

Dalej wychodzisz poza tablicę, ta sama linia..

P-116276

Mikilll

Temat założony przez niniejszego użytkownika

» 2014-08-27 16:23:20

OGARNĄŁEM

#include <iostream>

using namespace std;

int MniejszeDziecko( int rodzic, int & rozmiarKopca, int kopiec[] )
{
int leweDziecko = 2 * rodzic;
int praweDziecko = 2 * rodzic + 1;
if( leweDziecko >= rozmiarKopca )
   return 0;

if( praweDziecko >= rozmiarKopca or kopiec[ leweDziecko ] < kopiec[ praweDziecko ] )
   return leweDziecko;

return praweDziecko;
}

void UsunKorzen( int & rozmiarKopca, int kopiec[] )
{
int ostatni = kopiec[ rozmiarKopca - 1 ];
rozmiarKopca--;
int x = 1;
int c = MniejszeDziecko( 1, rozmiarKopca, kopiec );
while( c and kopiec[ c ] < ostatni )
{
kopiec[ x ] = kopiec[ c ];
x = c;
c = MniejszeDziecko( c, rozmiarKopca, kopiec );
}
kopiec[ x ] = ostatni;
}

int main()
{
const int rozmiar = 5;
int rozmiarKopca = rozmiar + 1;
int kopiec[ rozmiar + 1 ] = { 0, 2, 3, 2, 8, 4 };
int tab[ rozmiar ] = { 0 };
for( int i = 0; i < rozmiar; i++ )
{
tab[ i ] = kopiec[ 1 ];
UsunKorzen( rozmiarKopca, kopiec );
}
for( int i = 0; i < rozmiar; i++ )
   cout << tab[ i ] << " ";

return 0;
}

P-116277

« 1 »

Strona 1 z 1

» Forum » Programowanie » [C, C++] Szukam pomocy