Program wywłaszczony - problem z sortowaniem

Question

Witam! Od pewnego czasu zmagam się z zadaniem http://main.edu.pl/pl/archive/oi/4/kaj 
Do jego wykonania użyłem na początku sortowania bąbelkowego lecz dostałem komunikat "Program wywłaszczony" i 44 punkty. Postanowiłem przerzucić się na quicksort lecz wtedy było jeszcze gorzej "Program wywłaszsczony" i 0 punktów. W czym jest problem? Nie mam za bardzo pomysłu. 
Ktoś już zasugerował mi abym użył funkcji sort z biblioteki algorithm, lecz zastosowanie jej wymaga wiedzy, której nie posiadam, więc póki co chciałbym to wyminąć jeśli to możliwe. 
Dołączam mój kod źródłowy. Z góry dziękuję za pomoc. :)

 

#include <iostream>

using namespace std;
int wagamax, ilosc, licznik=0;

void quicksort(int *tablica, int lewy, int prawy)
{
    int v=tablica[(lewy+prawy)/2];
    int i,j,x;
    i=lewy;
    j=prawy;
    do
    {
        while (tablica[i]<v) i++;
        while (tablica[j]>v) j--;
        if (i<=j)
        {
            x=tablica[i];
            tablica[i]=tablica[j];
            tablica[j]=x;
            i++;
            j--;
        }
    }
    while (i<=j);
    if (j>lewy) quicksort(tablica,lewy, j);
    if (i<prawy) quicksort(tablica, i, prawy);
}

int main()
{
    cin>>wagamax>>ilosc;
    int *waga;
    waga= new int [ilosc];
    for(int i=0; i<=ilosc-1; i++)
    {
        cin>>waga[i];
    }
     quicksort(waga, 0, ilosc-1);
      for(int i=0; i<=ilosc-1; i++)
    {
        cout<<waga[i]<<endl;
    }
    int j=0;
    for(int i=ilosc-1; i>=0; i--)
    {
        if(waga[j]!=0 && waga[i]!=0)licznik++;
        if(waga[i]+waga[j]<=wagamax)
        {
            waga[j]=0;
            j++;
        }
        waga[i]=0;
    }
    delete [] waga;
    cout<<licznik;
    return 0;
}

Answer 1

Jeśli potrafisz napisać własne sortowanie, to tym bardziej umiesz wywołać gotowca.

#include <algorithm>
//...
  int tablica[rozmiar];
  int* wskaznik_na_poczatek_tablicy = &(tablica[0]);
  int* wskaznik_na_zaraz_po_koncu_tablicy = tablica+rozmiar;//nie wolno używać wartości spod niego!
  sort(wskaznik_na_poczatek_tablicy, wskaznik_na_zaraz_po_koncu_tablicy);//inaczej: sort(tablica,tablica+rozmiar)
//...

 

Comments

Dziękuję za odpowiedź! Zaimplementowałem analogicznie sortowanie z algorithm, lecz nadal otrzymuję ten sam komunikat - "Program wywłaszczony" i zero punktów.

---

małe wtrącenie: zamiast i <= ilosc-1 możesz robić i < ilosc

---

Może Cię wywłaszcza bo program za długo liczy (dla dużej ilości danych) lub duża ilość danych nie mieści się w pamięci. Może trzeba wymyślić inny sposób na rozwiązanie zadania.

---

Wyobraź sobie tablicę int na 30 000 argumentów gdzie int może zajmować 4 bajty - ile to będzie w KB, MB ?

Waga jest nie większa niż 200 więc mieści się w jednym bajcie. 

---

Dziękuję za odpowiedź!
30 000 intów po 4 bajty = 120 000 bajtów = 120 KB = 0.12 MB
Mam limit 32 MB co przy powyższym wyniku wygląda kosmicznie :/
Chyba spróbuję zrobić to zadanie kompletnie inaczej, bez żadnych sortowań.
A co do małego wtrącenia: tak zauważyłem to już, zupełnie nie wiem dlaczego tak to zrobiłem :D Chyba za długo już siedziałem przy tym zadaniu :)

---

Problem okazał się dużo bardziej prozaiczny niż się spodziewałem.
Kompletnie zapomniałem o pętli, która sprawdzała czy wszystko jest dobrze posortowane wypisując na ekranie wszystkie inty z tablicy. Teraz już wszystko działa jak należy.
Dziękuję za udzieloną pomoc!