Introsort

P

paddy_de

Grünschnabel
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:
Code: 
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:
Code: 
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;
}
 
sheel hat gesagt.:
Scheint ja nicht so trivial zu sein...
http://ralphunden.net/?q=a-guide-to-introsort hat eine lange Erklärung mit Javabeispiel

Schaut leicht portierbar aus.
Zum Vergrößern anklicken....

das hab ich auch schon gefunden, aber leider finde ich es nicht leicht protierbar. Bin noch nicht so eins mit Java und daher recht aufgeschmissen. Es soll ja meist recht einfach sein, Quelltext zwischen Java und C zu protieren und andersrum, aber ich bekomme es leider nicht hin! Vielleicht kann mir ja auch dabei jemand weiterhelfen!

danke!
 
Beispiel die erste Methode:

Java: 
private static Sortable [] createMedianOf3KillerArray ( int length )
{
    if (( length %2)==1)
        return null;
    int k= length /2;
    Sortable [] a = new Sortable [ length ];
    for (int i=1; i<=k; i++)
    {
        if ((i \%2) == 1)
        {
            a[i -1] = new SortableInteger (i);
            a[i] = new SortableInteger (k+i);
        }
        a[k+i -1] = new SortableInteger (2*i);
    }
    return a;
}

wird zu

C++: 
private static Sortable *createMedianOf3KillerArray ( int length )
{
    if (( length %2)==1)
        return NULL;
    int k= length /2;
    Sortable *a = new Sortable [ length ];
    for (int i=1; i<=k; i++)
    {
        if ((i \%2) == 1)
        {
            a[i -1] = new SortableInteger (i);
            a[i] = new SortableInteger (k+i);
        }
        a[k+i -1] = new SortableInteger (2*i);
    }
    return a;
}

Viel anders ist ja nicht...Nur kleine Sachen in Zeile 1, 4 und 6
Ein grober Unterschied ist aber, das du keinen GargabeCollector hast.
Dh wenn du die allokierten Arrays nicht mehr brauchst,must du irgendwann nach dem Funktionsaufruf ein delete[] machen.
 
Zuletzt bearbeitet:
ok danke, aber da komme ich ehrlich gesagt nicht so wirklich mit zurecht! hab bislang wenig c++ gemacht und naja ich will ja nicht einfach nur was rauskopieren und dann läufts...ich will ja schon auch verstehen, was ich dann da programmiere!! Kannst du mir vielleicht ein beispiel in reinem C Code zeigen meine beiden Sortierprogramme die ich bislang geschrieben habe sind ja auch reiner C-Code!


trotzdem danke für die Antwort!
 
Ohne Klassen kann man die Lösung von der Seite nicht sinnvoll weiterverwenden...besser von vorne anfangen. Erklärung des Algorithmus ist ja auch dort.
Ich muss es mir selber einmal durchlesen.
 
ja ich versuche es auch sinnvoll umzusetzen, aber das ist nicht so einfach! ich hab ja eine struktur bei mir gebaut und diese struktur fülle ich mit inhalt! sodass es nachher wie ein array aufgebaut ist! nun will ich auf dieses "Array" das introsort anwenden!
wie gesagt quicksort und heapsort waren beide kein problem, aber nun die umsetzung mit introsort bekomm ich einfach nicht hin! ich muss ja irgendwie herausifinden, wann ich nicht mehr quicksort verwenden möcht und er auf heapsort wechseln soll...aber wie mach ich das am besten?
 
Hi.
paddy_de hat gesagt.:
ja ich versuche es auch sinnvoll umzusetzen, aber das ist nicht so einfach! ich hab ja eine struktur bei mir gebaut und diese struktur fülle ich mit inhalt! sodass es nachher wie ein array aufgebaut ist! nun will ich auf dieses "Array" das introsort anwenden!
wie gesagt quicksort und heapsort waren beide kein problem, aber nun die umsetzung mit introsort bekomm ich einfach nicht hin! ich muss ja irgendwie herausifinden, wann ich nicht mehr quicksort verwenden möcht und er auf heapsort wechseln soll...aber wie mach ich das am besten?
Zum Vergrößern anklicken....
Bitte halte dich an die Netiquette, insbesondere Groß-/Kleinschreibung. Danke!

Laut Java-Algorithmus (und auch in der C++ STL Implementierung der GCC) wird eine max. Tiefe berechnet durch Log2(upper_index - lower_index) * 2. Erreicht die rekursive introsort_loop das Tiefenlimit (also depth_limit == 0), dann wird Heapsort eingesetzt.

Gruß
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück