[C++] Quicksort

Za vajo smo dobili, da moramo narediti v c++ program, ki bo sortiral zaporedje z algoritmom quicksort. Samo delovanje algoritma razumem : razdelimo zaporedje na 2 podzaporedji. Levo od delilnega elementa so manjša števila desno so večja. i = dno (index 0) j = vrh + 1 (to mi glih ni najbolj jasno zakaj +1 ), w = polje[dno]. Delal sem po psevdokodi in spacal tole.. :

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

void vpis (int A[], int velikost)
{
	for (int i=0; i<velikost; i++)
	{
		A[i] = rand()%9 + 1;
	}
}

void izpis (int A[], int velikost)
{
	for (int i=0; i<velikost; i++)
	{
		cout << A[i] << " ";
	}
}

void zamenjaj (int& prvi, int& drugi)
{
	int temp = prvi;
	prvi = drugi;
	drugi = temp;
}

int Deli (int A[], int dno, int vrh)
{
	int w = A[dno];
	int i = dno;
	int j = vrh + 1;
	for (;;)
	{
		do
		{
			j--;
		}
		while (A[j] <= w);

		do
		{
			i++;
		}
		while (A[i] <= w);

		if (i<j)
		{
			zamenjaj (A[i], A[j]);
		}
		else
		{
			zamenjaj (A[j], A[dno]);
			return j;
		}
	}
}

void Hitro_Uredi (int A[], int dno, int vrh)
{
	if (dno<vrh)
	{
		int delilni_indeks = Deli (A, dno, vrh);
		Hitro_Uredi (A, dno, delilni_indeks-1);
		Hitro_Uredi (A, delilni_indeks+1, vrh);
	}
}

int main ()
{
	int velikost;
	int A[1000];
	int izbira;
	int dno;
	int vrh;
	do
	{
		cout << "Hitro uredi - izbira:" << endl;
		cout << "1 Vnos podatkov - rocni" << endl;
		cout << "2 Generiranje nakljucnih podatkov " << endl;
		cout << "3 Zagon algoritma Hitro uredi" << endl;
		cout << "4 Izpis zaporedja" << endl;
		cout << "5 Konec" << endl;
		cout << endl;
		cin >> izbira;

		switch (izbira)
		{
		case 1 :
			cout << "vpisi dolzino polja" << endl;
			cin >> velikost;
			for (int i=0; i<velikost; i++)
			{
				cout << "Vpisi " << i + 1 << " element zaporedja" << endl;
				cin >> A[i];
				cout << endl;
			}
			cout << endl;
			break;
		case 2:
			cout << "vpisi dolzino polja" << endl;
			cin >> velikost;
			vpis (A,velikost);
			cout << endl;
			break;
		case 3:
			Hitro_Uredi (A, 0, velikost);
			break;
		case 4:
			izpis (A, velikost);
			cout << endl;
			break;
		case 5:
			return 0;
			break;
		}
	}
	while (izbira != 5);
	system ("pause");
	return 0;
}

Nevem kaj imam narobe, ker zaporedje ne deluje...

Jaz bi opozoril na to, da en program za drugega ne more prav veliko povedati. Prevajalnik v opisanem primeru ne rece "warning" zato, ker bi bila tisto manj kriticna napaka, ampak zato ker nikoli ne more biti preprican, da res funkcija ne vraca rezultata. Programer bi moral biti potem dovolj pameten in tisto upostevati ali pa ignorirati.

V programu je pomoje tisto ok tako kot je.
Sicer govorim cisto na pamet, ampak jaz bi spremenil
while (A[j] <= w);

v

while (A[j] <= w && j > dno);

in

while (A[i] <= w);

v

while (A[i] >= w) && i < vrh);


j = vrh + 1 je v programu zato, ker takoj zmanjsas j potem pa sele gledas pogoj.
i = dno po drugi strani je zaradi tega ker kot delilno vrednost vzames vrednost prvega elementa
V zanki se sprehajas v bistvu med drugim (dno+1) in zadnjim indeksom (vrh) (pri cemer gre i od leve proti desni, j pa od desne proti levi).
Ko se i in j prekrizata, si naredil vse in takrat z "zamenjaj (A[j], A[dno]);" prvi element (tisti ki si ga izpustil) premaknes na ustrezno mesto nekje na "sredini".

MrBrdo je 26. maj 2010 ob 10:47 izjavil:

Glej dejstvo je da je to zelo slaba navada, taka funkcija se komot kje zacikla ob kakšnem nenavadnem vhodu, ali pa vrne nedefinirano vrednost (odloči se prevajalnik ali pa je kar nekaj random). Pa še kakšen drug problem je v tej funkciji, npr. da se j lahko pomanjša pod 0, in i lahko poveča čez velikost polja (= Access Violation), "for (;;)" pa je tudi primer slabega programiranja... V glavnem si funkcija zasluži kar pošten makeover Seveda ni rečeno da je problem v tej funkciji samo je res grdo napisana...

Problem je sigurno v tej funkciji (ce ni se kje drugje). Navsezadnje je to v bistvu implementacija QuickSorta. Zaciklat se program ne more. ker se, ce imas koncno mnogo elementov, i in j prej ali slej prekrizata in se vse skupaj ustvari (in ravno to ni takoj ocitno). Je pa problem, ce imas npr. vse elemente enake: tisto je en simpel primer, kdaj gresta indeksa cez rob arraya (in zaradi tega sem dodal check). Ampak sklepam, da v psevdokodi taki robni pogoji niso bili upostevani, ker je tisto bolj abstraktno.

Ali je neskoncna zanka grda je cisto odvisno od primera. Tukaj vse skupaj imho niti ni tako hudo, karsnakoli alternativa bi bila sigurno slabsa. Funkcija je cisto ok taka kot je (oz. taka kot je brez bugov).