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;
}

http://ralphunden.net/?q=a-guide-to-introsort

paddy_de

Janjan schrieb:

http://ralphunden.net/?q=a-guide-to-introsort

das hatte ich auch schon entdeckt, bin ich aber leider nicht draus schlau geworden, weil es alles in java programmiert ist! ich brauche es aber in reinen C-Code. Sorry aber Java ist noch nicht ganz so mein!