QuickSort dla 100 000 liczb

Mam kod QuickSorta i wpisuje do niego liczby posortowane odwrotnie. Problem w tym, że program wywala dla ilosci liczb około 50 000, a ma działać nawet dla 100 000. Co zmienić, żeby działał poprawnie?

 

#include<iostream>
using namespace std;
 
int partition(int tablica[], int p, int r)
{
int x = tablica[p]; 
int i = p, j = r, w; 
while (true) 
{
while (tablica[j] > x) 
j--;
while (tablica[i] < x) 
i++;
if (i < j) 
{
w = tablica[i];
tablica[i] = tablica[j];
tablica[j] = w;
i++;
j--;
}
else 
return j;
}
}
 
int quicksort(int tablica[], int p, int r) 
{
int q;
if (p < r) 
{   
q = partition(tablica,p,r); 
quicksort(tablica, p, q);
quicksort(tablica, q+1, r); 
}
}
 
int main()
{
int ilosc_liczb, i;
cout << "Podaj ilosc licz do posortowania: ";
cin >> ilosc_liczb;
int *tablica = new int [ilosc_liczb];
 
	
		for (int i=0; i< ilosc_liczb; ++i)
		tablica[i]=0;
		
		for (int i=0; i<ilosc_liczb;++i)
		{
			tablica[0] = ilosc_liczb;
			tablica[i+1] = tablica[i] - 1;				
		}
 
quicksort(tablica,0,ilosc_liczb-1);
 
for (i = 0; i < ilosc_liczb; i++) 
cout << "tablica[" << i << "] = " << tablica[i] << endl;
 
delete [] tablica;
 
return 0;
}

korczyn napisał(a):

int *tablica = new int [ilosc_liczb];
...
for (int i=0; i<ilosc_liczb;++i)
{
        ...
        tablica[i+1] = ...
}

Wychodzisz poza zakres tablicy.

Co i jak zmienic by to naprawic?

Rusz głową. Sprawa jest banalna, zwłaszcza, że wyraźnie wskazałem co jest nie tak. Jeśli chcesz się odwołać do komórki i+1 to przecież i nie może wskazywać ostatniej komórki.

Poza tym to:

                for (int i=0; i< ilosc_liczb; ++i)
                tablica[i]=0;

jest zbędne, i tak te zera nadpisujesz nowymi wartościami.
Oraz

                for (int i=0; i<ilosc_liczb;++i)
                {
                        tablica[0] = ilosc_liczb;

Nie musisz tego przypisania tablica[0] = ilosc_liczb; wykonywać wiele razy, wystarczy raz.

Nie jestem aż tak świetny w programowaniu w C++, więc mógłby ktoś mi ktoś pomóc w rozwiązaniu takich zadań jak:

//W starozytnosci Rzymianie przybywali nad Morze Bałtyckie, aby nabyc bursztyny. Znani byli ze swojego
zamiłowania do porzadku, totez nic dziwnego, ze Pomorzanie, chcac im sie przypodobac, postanowili na ich
widok ustawic sie w szeregu. W dodatku nie byle jakim szeregu — pomiedzy kazdymi kolejnymi dwoma musiał
byc odstep równo jednego metra. Poza tym szereg musiał byc prostopadły lub równoległy do linii brzegu.
Tak samo oni, zbierajac sie do szeregu, musieli chodzic tylko równolegle lub prostopadle do morza — inaczej
pedantycznym gosciom mógłby zepsuc sie humor. Oblicz, ile sumarycznie musza przejsc Pomorzanie, aby
ustawic sie w szeregu.

Wejscie
W pierwszym wierszu standardowego wejscia znajduje sie jedna liczba N (1 6 N 6 106), oznaczajaca liczbe
Pomorzan.Wkolejnych N wierszach znajduja sie współrzedne poczatkowych ich pozycji, x i y (1 6 x; y 6 108).
Linia brzegu jest równoległa do osi X i znajduje sie bardzo daleko — powiedzmy, ze na prostej y =

Dzial praca zaprasza.

Jesli chcesz pomocy pokaz co sam zrobiles. Mozemy wtedy POMÓC. Bo pomoca nie jest robienie calego zadania za Ciebie.

Jak w tej pętli wstawie ilosc_liczb-1 lub i<=ilosc_liczb to też nie działa. Najpewniej źle zrozumiałem Twoje wskazówki. Choć i tak pewnie wyłożyłeś to jak laikowi, to ja nie mogę dostrzec błędu.

Krychu oto chodzi, że ja nie wiem jak się za to zadanie zabrać, jak zacząć.

korczyn napisał(a):

też nie działa
To nie musi być (i pewnie nie jest) jedyny błąd. Popraw jedno, napisz jak działa (dlaczego twierdzisz, że "źle") i lecimy dalej ;)

Zrobiłem coś takiego.

 

	
		for (int i=1; i<ilosc_liczb;++i)
		{
			tablica[0] = ilosc_liczb;
			tablica[i] = tablica[i-1] - 1;				
		}

Jak dobrze rozumiem to teraz nie mam tego i+1-ego elementu, lecz dalej dla ilosci liczb około 50 000 program się wysypuje.

podaj kod błędu

chodzi o to
http://screenshooter.net/4972688/aikcmvw
jakby co

osobiście podejrzewam stack overflow (0xC00000FD)