Merge sort wyrzuca w code blocksie, ale w kompilatorze online działa

Odpowiedz Nowy wątek
adam1707
2018-03-22 10:39
adam1707
0

Witam moi drodzy! Mam następujący problem - mój algorytm wyrzuca przy stosunkowo małych wartościach w code blocksie (przestaje działać dla <300 000 elementów), podczas gdy w kompilatorze online (konkretnie repl.it) działa nawet dla 1 000 000 elementów. Na zaliczenie mam stworzyć wykresy różnych funkcji sortujących i trochę mnie to nie urządza - wszystkie inne mają większą rozpiętość w CB i właśnie na podstawie tamtych danych chciałem opracować całe sprawozdanie. tutaj pojawia się pytanie, wiecie co może to powodować i jak to ewentualnie naprawić?? przecież logicznie rzecz biorąc powinno być odwrotnie
(i odpowiadając na pytania o sprzęt - mam laptopa średnio/wysokiej klasy)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void scalanie(int p,int k, int tab[],int pom_tab[]) {
  int pocz_p = p;
  int pocz_k = k;
  int pocz_srodkowy=(pocz_k+pocz_p)/2+1;
  int srodkowy = pocz_srodkowy;
  int licznik = 0;
  while (licznik < pocz_k-pocz_p+1) {
    if (p < pocz_srodkowy && srodkowy <= pocz_k) {

      if (tab[p] > tab[srodkowy]) {
        pom_tab[licznik+pocz_p] = tab[srodkowy];
        srodkowy++;
      }
      else if (tab[p] < tab[srodkowy]) {
        pom_tab[licznik+pocz_p] = tab[p];
        p++;
      }
      else if (tab[p] == tab[srodkowy] && p != srodkowy) {
        pom_tab[licznik+pocz_p] = tab[p];
        p++;
      }
      else {
        pom_tab[licznik+pocz_p] = tab[p];
        p++;
        srodkowy++;
      }
    }
    else if (p < pocz_srodkowy) {
      pom_tab[licznik+pocz_p] = tab[p];
      p++;
    }
    else {
      pom_tab[licznik+pocz_p] = tab[srodkowy];
      srodkowy++;
    }
    licznik++;
  }
    for (int n=pocz_p;n<=pocz_k;n++) {
      tab[n] = pom_tab[n];
    }
  }
void merge(int p, int k, int tab[], int pom_tab[]) {
  int element_srodkowy = (k+p)/2;
  if (k!=p) {
  merge(p,element_srodkowy,tab,pom_tab);
  merge(element_srodkowy+1,k,tab,pom_tab);
  scalanie(p,k,tab,pom_tab);
}
}
void merge_sort(int tab[], int n) {
  int k = n-1;
  int p = 0;
  int element_srodkowy = (k+p)/2;
  int pom_tab[n];
  if (k!=p) {
  merge(p,element_srodkowy,tab,pom_tab);
  merge(element_srodkowy+1,k,tab,pom_tab);
  scalanie(p,k,tab,pom_tab);
}
}

int main() {
  int n;
  double t;
  printf("wpisz liczbę elementów tablicy:");
  scanf("%d",&n);
  int tab[n];
  int i = 0;
  srand(time(0));
  int length = sizeof(tab)/ sizeof(int);
  while (i < n) {
    tab[i] = rand()%(10*n);
    //printf("%d ", tab[i]);
    i = i + 1;
  }
  printf("\n");
  t = clock();
  merge_sort(tab, length);
  t = clock() - t;
  t = t/CLOCKS_PER_SEC;
  printf("czas to %f\n",t);
  for(int i =0; i<length;i++){
    //printf("%d ", tab[i]);
  }
  return 0;
}
edytowany 1x, ostatnio: furious programming, 2018-03-22 12:34
Trochę tego kodu jest a czasu mam mało ale jedno, czy odpalałeś to pod debbugerem? Wydajnościowo ocenić sobie też możesz na podstawie vallgrind. - revcorey 2018-03-22 10:41

Pozostało 580 znaków

2018-03-22 10:56

Rejestracja: 2 lata temu

Ostatnio: 2 lata temu

2

Spróbuj zaalokować pamięć przez malloc.
Czyli zamiast:

int tab[n];

Przydziel pamięć dynamicznie:

int *tab = (int *)malloc(n * sizeof(int));

I gdzieś przed return wyczyść ją

free(tab);
Bardzo słuszna uwaga. Możliwe, że miejsce na heap sie zwyczajnie kończy. - pingwindyktator 2018-03-22 11:03
@pingwindyktator: chyba stos miałeś na myśli. - Azarien 2018-03-22 14:59
@Azarien: tak, oczywiście, mój błąd. - pingwindyktator 2018-03-22 15:41

Pozostało 580 znaków

adam1707
2018-03-22 15:38
adam1707
0
murduck napisał(a):

Spróbuj zaalokować pamięć przez malloc.
Czyli zamiast:

int tab[n];

Przydziel pamięć dynamicznie:

int *tab = (int *)malloc(n * sizeof(int));

I gdzieś przed return wyczyść ją

free(tab);

super, program nie wyrzuca już nawet przy 1 000 000! ale chyba pojawił się jakiś problem z printowaniem wartości tablicy po merge sorcie (zawsze pojawiają się dwie, które były pierwsze jeszcze przed wywołaniem funkcji)

Pozostało 580 znaków

2018-03-22 15:45

Rejestracja: 7 lat temu

Ostatnio: 4 dni temu

Lokalizacja: Kraków

0

https://wandbox.org/permlink/sA7UzgkqqeBb8CLt
int length = sizeof(tab)/ sizeof(int); tego nie potrzebujesz, bo znasz rozmiar tablicy - jest to wprowadzone przez usera n.


Pozostało 580 znaków

adam1707
2018-03-22 18:47
adam1707
0
pingwindyktator napisał(a):

https://wandbox.org/permlink/sA7UzgkqqeBb8CLt
int length = sizeof(tab)/ sizeof(int); tego nie potrzebujesz, bo znasz rozmiar tablicy - jest to wprowadzone przez usera n.

Taaak, masz rację, a co do poprzedniego mojego posta to jednak działa wszystko już
dzięki wszystkim!

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 0, botów: 1

Robot: PetalBot