Was hat "qsort", was ich nicht habe? :-/

Hallo erstmal...
Also...folgendes Programm:

#include <iostream>

using namespace std;

int QSortCompare(const void* pElem1, const void* pElem2)
{
	int* p1 = (int*)pElem1;
	int* p2 = (int*)pElem2;
	if (*p1 < *p2)
		return -1;
	if (*p1 > *p2)
		return +1;
	return 0;
}

void Sort1(int aiElems[], size_t count)
{
	size_t i, min;
	for (; count--; ++aiElems)
	{
		min = 0;
		for (i = 1; i <= count; ++i)
		{
			if (aiElems[i] < aiElems[min])
				min = i;
		}
		swap(*aiElems, aiElems[min]);
	}
}

void Sort2(int aiElems[], size_t count)
{
	size_t i, j, k, min, max;
	for (i = 0, j = count - 1; i < j; ++i, --j)
	{
		min = i;
		max = j;
		for (k = i; k <= j; ++k)
		{
			if (aiElems[k] < aiElems[min])
				min = k;
			if (aiElems[k] > aiElems[max])
				max = k;
		}
		swap(aiElems[i], aiElems[min]);
		if (i == max)
			max = min;
		swap(aiElems[j], aiElems[max]);
	}
}

inline void Sort3(int aiElems[], size_t count)
{
	qsort(aiElems, count, sizeof (int), QSortCompare);
}

void RandInit(int aiElems[], size_t count)
{
	while (count--)
		*aiElems++ = rand();
}

void Copy(int aiDestination[], const int aiSource[], size_t count)
{
	while (count--)
		*aiDestination++ = *aiSource++;
}

bool IsSorted(int aiElems[], size_t count)
{
	for (size_t i = 0; i < count - 1; ++i)
	{
		if (aiElems[i] > aiElems[i + 1])
			return false;
	}
	return true;
}

long double GetSortTime(void (*SortFunc)(int[], size_t), int aiElems[], size_t count)
{
	clock_t start, finish;
	start = clock();
	SortFunc(aiElems, count);
	finish = clock();
	return (long double)(finish - start) / CLOCKS_PER_SEC;
}

int main()
{
	srand(time(NULL));

	const size_t SIZE = 20000;
	const size_t ROUNDS = 10;
	int a[SIZE];
	int temp[SIZE];
	long double dTime1 = 0, dTime2 = 0, dTime3 = 0;

	for (size_t i = 1; i <= ROUNDS; ++i)
	{
		cout << "Starte Runde " << i << " von " << ROUNDS << endl;
		RandInit(a, SIZE);
		Copy(temp, a, SIZE);
		dTime1 += GetSortTime(Sort1, a, SIZE);
		if (!IsSorted(a, SIZE))
			return 1;
		Copy(a, temp, SIZE);
		dTime2 += GetSortTime(Sort2, a, SIZE);
		if (!IsSorted(a, SIZE))
			return 2;
		Copy(a, temp, SIZE);
		dTime3 += GetSortTime(Sort3, a, SIZE);
		if (!IsSorted(a, SIZE))
			return 3;
		cout << "Fertig..." << endl;
	}
	dTime1 /= ROUNDS;
	dTime2 /= ROUNDS;
	dTime3 /= ROUNDS;
	cout << "Durchschnittliche Sortierzeit:\n";
	cout << "\tSort1: " << dTime1 << " Sekunden\n";
	cout << "\tSort2: " << dTime2 << " Sekunden\n";
	cout << "\tSort3: " << dTime3 << " Sekunden\n";
	return 0;
}

Liefert in 99,999% aller Test folgende (oder ähnliche) äusserst deprimierende Ausgabe:
Starte Runde 1 von 10
Fertig...
[...]
Starte Runde 10 von 10
Fertig...
Durchschnittliche Sortierzeit:
Sort1: 1.2062 Sekunden
Sort2: 0.9829 Sekunden
Sort3: 0.0078 Sekunden

Weiß irgendjemand, wie qsort das macht?? Ich kann mir irgendwie schlecht vorstellen, dass dieses Ding mehr als 100 mal schneller als meine Funktionen ist.

Jester

qsort implementiert den Quick-sort Algorithmus, der hat im Mittel einen Aufwand von O(n*logn) Du implementierst soweit ich das überflogen habe einen Algorithmus mit O(n²). Das heißt mit einer größeren Datenmenge wirst Du noch weiter abgehängt. Google halt mal nach Quicksort, es gibt tausende von Seiten die den Algorithmus erklären.

MfG Jester

und nich vergessen von debug auf release umzustellen

Bashar

qsort ist höchstwahrscheinlich (wie der Name schon andeutet) über QuickSort implementiert. Ich bin zwar nicht so der Algorithmen-Crack, aber meiner Meinung nach sind deine Sortierfunktionen simple Sortierverfahren (der erste sieht wie Insertion Sort aus) mit O(n²)-Komplexität, d.h. die Laufzeit ist für große Felder zum Quadrat der Anzahl der Feldelemente proportional. Quicksort ist schon etwas ausgefeilter und erreicht im durchschnittlichen Fall eine O(n logn)-Laufzeit.

Jup. Dein Sortieralgorithmus ist nicht nur 100mal langsamer, sondern um Größenordnungen langsamer. Wenn du die Zahl der Elemente noch weiter vergrößerst, bist du nochmal um ein Vielfaches langsamer.
Aber gräme dich nicht: Genau deshalb gibt es ja den Sortieralgorithmus in der Standardbibliothek.
qsort ist übrigens nicht sehr schwer zu verstehen. Wenn es dich unbedingt interressiert, dann google mal einfach danach. Anzumerken ist aber, das qsort alleine auch noch nicht sehr schnell ist. Meistens lässt man eine Collection mit qsort nur vorsortieren und heizt dann z.B. nochmal mit Insertionsort drüber.

Hmm... danke!
Aber kann mir jetzt noch jemand sagen was das ganze auf 12.-Klasse-beschäftige-mich-nur-in-der-Freizeit-damit-isch (= nicht grade für Mathe-/Informatikstudenten )heisst???
Was bitte bedeutet O(...)? Ok... irgendwas mit Zugriffszeit... oder zumindest so in der Art
Aber wie kommt man bitte darauf?

SideWinder

O ist die Laufzeit eines Algorithmus.

n die Anzahl der Elemente

O(1) ... konstante Laufzeit
O(log(n)) ... logarithmisch
O(n) ... linear
O(n * log(n)) ... n*log(n)
O(n²) ... quadratisch
O(2^n) ... exponentiell

Imho ist O mit dem worst case gleichzusetzen, BestCase ist die Omega-Notation.
AverageCase gibts auch noch.

Wie man drauf kommt? Ist Standard - ich hätte es in der Schule gelernt wenn ichs nicht schon gewusst hätte.

MfG SideWinder

Hier eine schöne Seite.

Was hat &quot;qsort&quot;, was ich nicht habe? :-/

Was hat "qsort", was ich nicht habe? :-/