Cześć! Właśnie pracuję nad programem sortującym przez kopcowanie tablice dynamiczne jednowymiarowe. Oto mój kod źródłowy:
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// funkcja ta tworzy tablice dynamiczna dwuwymiarową
int** stworz_tablice (int ilosc_tab, int rozm_tab){
int** tablice = new int* [ilosc_tab];
for (int i=0; i<ilosc_tab; i++){
tablice[i] = new int [rozm_tab];
}
return tablice;
}
// funkcja ta generuje losowe liczby naturalne w zaleznosci od wybranego zakresu oraz wpisuje je do tablicy dynamicznej
void generuj_losowe (int **tablica, int lk, int lw, int zakres){
srand(time(NULL));
for(int i=0; i<lk; i++)
for(int j=0; j<lw; j++)
tablica[i][j]=rand()%zakres;
}
// jest to funkcja wyswietlajaca zawartosc wczesniej utworzonej tablicy
void wyswietl_tablice (int **tablica, int lk, int lw){
for(int i=0; i<lk; i++){
cout << endl;
for(int j=0; j<lw; j++){
cout << tablica[i][j];
cout << " ";
}
}
cout << endl;
}
// ta funkcja sprawdza, czy wprowadzona wartosc do kopca ma wartosc wieksza i jesli tak, to zamienia ja z przodkiem
void sprawdz_przodka (int** tablice, int lisc, int ktora_tablica){
int przodek;
int tmp;
while(lisc>0){
przodek=(lisc+1)/2-1;
if(tablice[ktora_tablica][lisc]>tablice[ktora_tablica][przodek]){
tmp=tablice[ktora_tablica][przodek];
tablice[ktora_tablica][przodek]=tablice[ktora_tablica][lisc];
tablice[ktora_tablica][lisc]=tmp;
lisc=przodek;
}
else
lisc=0;
}
}
// ta funkcja zamienia element z poczatku kopca ze wskazanym elementem
void zamien_z_poczatkiem (int** tablice, int i, int ktora_tablica){
int tmp=tablice[ktora_tablica][i];
tablice[ktora_tablica][i]=tablice[ktora_tablica][0];
tablice[ktora_tablica][0]=tmp;
}
void kopcowanie (int** tablice, int rozm_tab, int ktora_tablica){
// TWORZENIE KOPCA
for(int lisc=1; lisc<rozm_tab; lisc++){ // "int lisc" - pozycja wstawionego liscia (nr kolumny dwuwym. tab. dyn. "tablice")
sprawdz_przodka(tablice, lisc, ktora_tablica);
}
// ROZBIERANIE KOPCA
for(int rozmiar_kopca=rozm_tab-1; rozmiar_kopca>0; rozmiar_kopca--){
zamien_z_poczatkiem (tablice, rozmiar_kopca, ktora_tablica);
for (int lisc=1; lisc<rozmiar_kopca; lisc++){
sprawdz_przodka(tablice, lisc, ktora_tablica);
}
}
}
// jest to funkcja usuwajaca tablice dynamiczna
void usun_tablice (int **tablice, int rozm_tab){
for(int i=0; i<rozm_tab; i++)
delete [] tablice[i];
delete [] tablice;
}
int main()
{
int ilosc_tab=30; // liczba wierszy
int rozm_tab=20; // liczba kolumn
cout << "Zostanie stworzonych " << ilosc_tab << " tablic i kazda z nich bedzie zawierac " << rozm_tab << " elementow.";
int** tablice=stworz_tablice(ilosc_tab, rozm_tab);
int zakres=20;
cout << "Zakres liczb losowo generowanych to: " << zakres << "." << endl << endl;
generuj_losowe(tablice, rozm_tab, ilosc_tab, zakres);
wyswietl_tablice(tablice, rozm_tab, ilosc_tab);
for(int i=0; i<ilosc_tab; i++){
kopcowanie(tablice, rozm_tab, i);
}
cout << "Po sortowaniu:" << endl;
wyswietl_tablice(tablice, rozm_tab, ilosc_tab);
usun_tablice (tablice, rozm_tab);
return 0;
}
Program działa nieźle na Ubuntu (Code::Blocks 10.15) przy parametrach:
int ilosc_tablic=20;
int rozm_tab=20;
int zakres=20;
Przy zwiększaniu np. ilości tablic wywala błąd:
Aborted (core dumped)
Process returned 134 (0x86)
Z kolei, gdy uruchamiałem na windowsie 7 (również kompilowałem w Code::Blocks), to przy parametrach:
int ilosc_tablic=100;
int rozm_tab=100;
int zakres=100;
działało jeszcze optymalnie. Kaszana zaczęła się dopiero przy zmianie ilości tablic na 200 - tu po prostu program zawiesił się aż w końcu wyświetlił się komunikat w stylu: "Program przestał działać... Debuguj lub zamknij program".
Czy da się jakoś temu zapobiec? Moim zadaniem jest przetestowanie tego rodzaju sortowania dla 100 tablic (elementy typu całkowitoliczbowego) o następujących rozmiarach: 10 000, 50 000, 100 000, 500 000 i 1 000 000. Za odpowiedź z góry dziękuję!
C++