Introsort

[paddy_de]

hey also ich habe folgendes Problem! Ich möchte gerne Introsort in mein C-Programm implementieren! Im Internet per google suchmaschine findet man leider keine vernünftigen Beiträge dazu! Habe dort bisher nur was für Delphi oder Java gefunden und das wurde mir auch bei längerer Betrachtung nicht ganz schlüssig. Hoffe ihr könnt mir weiterhelfen! Ich poste gleich noch meine quciksort (3-Median-Methode) und meine heapsort funktionen, die ich ja eigentlich für meinen introsort verwenden können müsste.

QuickSort:

static void quickSort(NUMBERS_t *pNumbers, int iLeft, int iRight)

{

	int i, j, iMedian;


	if (iRight > iLeft)

	{

		i = iLeft - 1;

		j = iRight;


		if (iRight - iLeft > 3)

		{

			iMedian = iLeft + (iRight - iLeft) / 2;


			if (pNumbers[iLeft].iRandom > pNumbers[iMedian].iRandom)

				swapp(&pNumbers[iLeft].sizeIndex, &pNumbers[iMedian].sizeIndex, &pNumbers[iLeft].iRandom, &pNumbers[iMedian].iRandom);


			if (pNumbers[iLeft].iRandom > pNumbers[iRight].iRandom)

				swapp(&pNumbers[iLeft].sizeIndex, &pNumbers[iRight].sizeIndex, &pNumbers[iLeft].iRandom, &pNumbers[iRight].iRandom);


			if (pNumbers[iRight].iRandom > pNumbers[iMedian].iRandom)

				swapp(&pNumbers[iRight].sizeIndex, &pNumbers[iMedian].sizeIndex, &pNumbers[iRight].iRandom, &pNumbers[iMedian].iRandom);

		}


		for ( ; ; )

		{

			while(pNumbers[++i].iRandom < pNumbers[iRight].iRandom)

				;


			while(pNumbers[--j].iRandom > pNumbers[iRight].iRandom)

				;


			if (i >= j)

				break;


			swapp(&pNumbers[i].sizeIndex, &pNumbers[j].sizeIndex, &pNumbers[i].iRandom, &pNumbers[j].iRandom);

		}


		swapp(&pNumbers[i].sizeIndex, &pNumbers[iRight].sizeIndex, &pNumbers[i].iRandom, &pNumbers[iRight].iRandom);


		quickSort(pNumbers, iLeft, i-1);

		quickSort(pNumbers, i+1, iRight);

	}


}


static void swapp(size_t *sizeIndexA, size_t *sizeIndexB, int *iRandomA, int *iRandomB)

{

	size_t sizeIndexTmp;

	int iRandomTmp;


	sizeIndexTmp = *sizeIndexA;

	iRandomTmp = *iRandomA;


	*sizeIndexA = *sizeIndexB;

	*iRandomA = *iRandomB;


	*sizeIndexB = sizeIndexTmp;

	*iRandomB = iRandomTmp;

}

HeapSort:

static void heapSort(NUMBERS_t *pNumbers, int n)

{

	int i;

	int iRandomTmp;

	size_t sizeIndexTmp;


	construction(pNumbers, n);


	for (i = 0; i < n; i++)

		printf("%d, %d\n", pNumbers[i].sizeIndex, pNumbers[i].iRandom);


	for (i = n-1; i >= 0; i--)

	{

		sizeIndexTmp = pNumbers[0].sizeIndex;

		iRandomTmp = pNumbers[0].iRandom;


		pNumbers[0] = pNumbers[i];


		pNumbers[i].sizeIndex = sizeIndexTmp;

		pNumbers[i].iRandom = iRandomTmp;


		downHeap(pNumbers, i, 0);

	}

}


static void construction(NUMBERS_t *pNumbers, int n)

{

	int i;


	i = n / 2 - 1;


	for (; i >= 0; i--)

		downHeap(pNumbers, n, i);

}


static void downHeap(NUMBERS_t *pNumbers, int n, int i)

{

	int j;

	int iRandomTmp;

	size_t sizeIndexTmp;


	sizeIndexTmp = pNumbers[i].sizeIndex;

	iRandomTmp = pNumbers[i].iRandom;


	if (i < 0)

		return;


	while (i < n / 2)

	{

		j = i + i + 1;


		if (j + 1 < n && pNumbers[j].iRandom < pNumbers[j+1].iRandom)

			j++;


		if (iRandomTmp >= pNumbers[j].iRandom)

			break;


		pNumbers[i] = pNumbers[j];

		i = j;

	}


	pNumbers[i].sizeIndex = sizeIndexTmp;

	pNumbers[i].iRandom = iRandomTmp;

}

[Klotzkopp]

hey also ich habe folgendes Problem! Ich möchte gerne Introsort in mein C-Programm implementieren!

...

Hoffe ihr könnt mir weiterhelfen!

Da wäre jetzt eine etwas genauere Problembeschreibung hilfreich. Oder vielleicht eine Frage.

Was mir aufgefallen ist:

iMedian = iLeft + (iRight - iLeft) / 2;

Das ist eine umständliche Schreibweise für

iMedian = (iRight + iLeft) / 2;

und das ist kein Median, sondern ein einfaches arithmetisches Mittel.

[paddy_de]

ja ok das ist ja aber nur eine Vriablen Deklaration! Das Problem ist ganz einfach, dass ich nicht weiß, wie ich nun aus meinen beiden Sortierprogrammen einen Introsort baue. Habe auf zahlreichen Seiten gelesen, dass dieser in bestimmten Fällen schneller ist als die beiden oben beschriebenen, vorallem, wenn der worst case auftritt! Ich müsste ja nun irgendetwas um meine Programme herum programmieren, dass entscheidet, wann welche Sortiermethode verwendet werden soll. Und das ist genau mein Problem, wo ich nicht weiter komme, weil ich nicht weiß, wie ich das am besten machen soll, deshalb habe ich dieses Topic ins Forum gepostet.

Vielleicht hat ja jemand schoneinmal soetwas gemacht und kann mir weiterhelfen, oder ein bißchen SourceCode zur verfügung stellen!

danke!

[Klotzkopp]

ja ok das ist ja aber nur eine Vriablen Deklaration!

Ich wollte dich nur darauf aufmerksam machen, dass deine Quicksort-Implementierung (entgegen deiner Beschreibung) nicht Median-of-3 verwendet, um das Pivotelement auszuwählen, sondern einfach das Element in der Mitte des Arrays benutzt.

Ich müsste ja nun irgendetwas um meine Programme herum programmieren, dass entscheidet, wann welche Sortiermethode verwendet werden soll.

Nicht drumherum. In der Quicksort-Implementierung wird unter bestimmten Bedingungen (Rekursionstiefe, Arraygröße) auf einen anderen Algorithmus umgeschaltet. Statt also sich selbst aufzurufen, ruft die Quicksort-Funktion einen anderen Sortieralgorithmus auf.

[paddy_de]

ok das klingt losgisch, nur wie bekomme ich raus, wann die entsprechende Rekursionstiefe erreicht ist, um z.B. von quicksort auf heapsort zu wechseln?

ich hab auch schon etwas code gefunden, wo genau das Problem behandelt wird, nur leider ist der code in Java geschrieben und das auf C umzusetzen klappt noch nicht so recht!

ralphunden.net

[Klotzkopp]

ok das klingt losgisch, nur wie bekomme ich raus, wann die entsprechende Rekursionstiefe erreicht ist, um z.B. von quicksort auf heapsort zu wechseln?

Der Beispielcode, auf den du verlinkt hast, ermittelt zu Anfang die maximale Rekursionstiefe aus dem Logarithmus der Arraygröße. Die wird als zusätzlicher Parameter übergeben und bei jedem Rekursionsschritt um 1 verringert. Ist der Wert bei 0 angelangt, wird auf Heapsort umgestellt.

[paddy_de]

alles klar danke, dann weiß ich jetzt glaub ich, wie ich es hinbekomme!