Hilfe bei Implementation des quicksort

tobidope

Hallo,

ich versuche gerade den quicksort so zu implementieren, wie er in einer
clib stehen könnte, stoße dabei allerdings auf Probleme.

zu langsam
overflow des Funktionsstack, die Rekursion entartet

Durch die Variante des Algorithmus 'Median of Three' versuche ich dem
entgegenzuwirken, was aber nicht funktioniert.

Hier mein Code:

/*
 * Signatur der Vergleichsfunktion. Sind die dereferenzierten Elemente identisch
 * soll 0 zurückgegeben werden. Ist das erste größer als das zweite eine Zahl größer
 * 0 bzw. im anderen Fall eine Zahl kleiner 0.
 */
typedef int (*cmp_fct)(const void*, const void*);

/*
 * Die Funktion swap vertauscht den Inhalt der Variablen first und second
 * byteweise.
 */
static void
swap(void* first, void* second, size_t size)
{
	char* a = first;
	char* b = second;
	char temp;

	++size;
	while(--size) {
		temp = *a;
		*a = *b;
		*b = temp;
		++a, ++b;
	}
}

/* 
 * Es wird ein Zeiger auf das Element zurückgegeben, dessen Wert der
 * der mittler von left, mittleres Element zwischen left und right, right
 * ist
 */
static void*
median_of_three(void* left, void* right, size_t size, cmp_fct compare)
{
	ptrdiff_t diff = ((char*)right - (char*)left) / size;
	void* middle = (char*)left + (diff/2) * size;

	if(compare(left, middle) >= 0) /* left >= middle? */
		if(compare(right, middle) >= 0) /* right >= middle? */
			if(compare(left, right) >= 0) /* left >= right? */
				return right; /* left   >=  right  >= middle */
			else
				return left;  /* right  >   left   >= middle */
		else 
			return middle;    /* left   >=  middle >  right */
	else if(compare(left, right) >= 0) /* left >= right? */
		return left;          /* middle >   left   >= right */
	else if(compare(middle, right) >= 0) /* middle >= right */
		return right;         /* middle >= right   > left */
	else
		return middle;        /* right  >  middle  >=  left */
}

void
quicksort(void* ptr, size_t count, size_t elem_size, cmp_fct compare)
{
	qs(ptr, (char*)ptr + ((count-1) * elem_size), elem_size, compare);
}

static void
qs(void* links, void* rechts, size_t size, cmp_fct compare)
{
	char* i = links;
	char* j = (char*)rechts - size;

	char* pivot = median_of_three(links, rechts, size, compare);

	if(pivot != rechts) 
		swap(pivot, rechts, size);	
	pivot = rechts;

	do {
		while(compare(i, pivot) < 0) /* i < pivot */
			i += size;

		while(compare(j, pivot) >= 0 && j >= links) /* j >= pivot */
			j -= size;

		if(i < j)
			swap(i, j, size);

	} while(i <= j); /* bis i > j */

	swap(pivot, i, size);

	if(links < j)
		qs(links, j, size, compare);
	if(i + size < rechts)
		qs(i + size, rechts, size, compare);
}

Ich wäre sehr froh, wenn sich jemand mal den Code anschauen könnte und ihn
kompiliert, und mir sagt, was ich denn so falsch mache.

MfG
Tobias

666Blade*DC*666

also will ja keine unqualifizierten beiträge posten .. aber das was du da machst is doch nen bischen umständlich ... oder ?? wir haben quicksort, bubblesort .. usw. mal in der schule gemacht und die waren nur so 6 zeilen lang wenn überhaupt ... warum schreibste nicht ne eigene funktion nach dem prinzip von quicksort oder bubblesort ??

tobidope

666Blade[DC]666 schrieb:

also will ja keine unqualifizierten beiträge posten .. aber das was du da machst is doch nen bischen umständlich ... oder ?? wir haben quicksort, bubblesort .. usw. mal in der schule gemacht und die waren nur so 6 zeilen lang wenn überhaupt ... warum schreibste nicht ne eigene funktion nach dem prinzip von quicksort oder bubblesort ??

Du hast aber schon gesehen, dass dort unten der quicksort steht? Natürlich habe ich schon heapsort, bubblesort, ... implementiert. Aber der springende Punkt ist halt, dass generisches sortieren in ISO-C nun mal void-Zeiger und etwas mehr Aufwand braucht. Wenn du ein toller Programmiere bist, dann zeige mir doch mal, wie man "median of three" kürzer programmiert? Oder hast du überhaupt Ahnung von den Varianten des quicksort??

Gruß Tobias

666Blade*DC*666

Also .... beschreib doch einfach mal was du genau machen willst denn das was du da mit deinem rechts << links << rechts ... blabla .. machst in den kommentaren is nur schwer nachzuvollziehen gewesen ... die allemeine Definition müste so sein ..

Der Median, oder das 50% Quantil, einer Reihe von Zahlen ist per Definition die Zahl, die die geordnete Reihe der Werte in zwei gleichgroße Teile teilt. Liegt eine ungerade Anzahl von Werten vor, so entspricht der Median dem mittleren Wert der geordneten Reihe. Ist die Anzahl gerade, so wird das arithmetische Mittel der beiden mittleren Zahlen ermittelt.

Beispiel zur Ermittlung des Medians:
Der Median der Zahlenreihe 1 2 3 4 5 ist 3.
Der Median von 1 2 3 4 beträgt (2+3)/2=5/2=2.5.

.. ne ? .... und was willst du jez machen ??? Du hast nen Array von Zahlen und willst die Quicksort-optimierte Methode median of three verwenden um das ganze zu sortieren ???

beispiele zur funktionweise .. http://ad.informatik.uni-freiburg.de/lehre/ws9697/multimedia-praktikum/animationen/vortrag/beispiele/

SG1

666Blade[DC]666 schrieb:

Der Median, oder das 50% Quantil, einer Reihe von Zahlen

Da ist schon das Problem. Wer sagt, dass hier Zahlen sortiert werden? Es werden abstrakte Objekte sortiert, wobei die Ordnung durch cmp_fct definiert wird. Also muss man sich was anderes einfallen lassen.

Theoretisch kann man ja als Pivot-Element in Quicksort jedes beliebige Element nehmen. Also theoretisch auch einfach das erste. Dummerweise hat man dann genau im bereits sortierten Fall ein _SEHR_ unguenstiges Verhalten.

Mein Vorschlag waere jetzt einfach das mittlere Element zu nehmen. tobidope versucht jetzt noch was anderes: Er nimmt das erste, mittlere und letztes Element, vergleicht diese mittels cmp_fct, und nimmt dann dasjenige Element als Pivotelement, welches zwischen den beiden anderen liegt. Hab ich das soweit richtig verstanden?

666Blade*DC*666

Wenn du dir die ANimationen zu dem Link anschaust siehst du das das dem Nahe kommt was du gesagt hast. Prinzipiell ist mir das Verfahren bekannt ... aber wie willst du Objekte sortieren und warum ?? Elemente müssen doch nach einem ausgewählten schlüssel sortiert werden, der dann doch wieder aus Zahlen besteht oder ??

.. hab noch was zu Sortierverfahren gefunden ... http://sort4palmos.sourceforge.net/algorithmen/node38.html

SG1

666Blade[DC]666 schrieb:

aber wie willst du Objekte sortieren

Nach einer auf diesen Objekten definierten Ordnung. Wie diese aussieht ist irrelevant, einzig relevant ist, dass diese von cmp_fct compare implementiert wird.

und warum ??

Warum wollte man Telefonbucheintraege sortieren? Und was interessiert das denjenigen, der eine Bibliotheksfunktion implementiert?

Elemente müssen doch nach einem ausgewählten schlüssel sortiert werden, der dann doch wieder aus Zahlen besteht oder ??

nein?

.. hab noch was zu Sortierverfahren gefunden ... http://sort4palmos.sourceforge.net/algorithmen/node38.html

Das Verfahren ist bekannt, glaube ich.

666Blade*DC*666

das das verfahren bekannt ist hatte ich erwartet, aber da sind alle sortierverfahren aufgeführt und beschreiben und tipps zur optimierung enthalten ... ich dachte das das interessant sein könnte. Es gibt immer mehrere Lösungen und wenn du zu diesem konkreten Problem diese nicht findest, dann umgeht man sie am besten. Sorry das du so allwissend bist. Hatte nicht alle funktionsweisen so genau im kopf. Mach doch mal nen Lösungsvorschlag ... ?
Oder sag mir anhand welcher Schlüssel Objekte dann Sortiert werden ... ?

SG1

666Blade[DC]666 schrieb:

Oder sag mir anhand welcher Schlüssel Objekte dann Sortiert werden ... ?

Anhand von cmp_fct compare

SG1

SG1 schrieb:

666Blade[DC]666 schrieb:

aber wie willst du Objekte sortieren

.. hab noch was zu Sortierverfahren gefunden ... http://sort4palmos.sourceforge.net/algorithmen/node38.html

Das Verfahren ist bekannt, glaube ich.

Ups, hatte da nur Median-Of-Three gelesen, da steht ja noch mehr...

Ja, fuer kleine Mengen ein anderes Verfahren anzuwenden, waere hier wirklich eine Optimierungsmoeglichkeit. Microsoft macht das IIRC ab n <= 8.

SG1

Um den Stack zu schonen, kann man zuerst die kleinere der beiden Teilmengen sortieren. Die 2. Sortierung kann der Compiler dann als Endrekursion wegoptimieren. Also statt

tobidope schrieb:

if(links < j)
		qs(links, j, size, compare);
	if(i + size < rechts)
		qs(i + size, rechts, size, compare);

if ((j-links) < (rechts-(i+size))) {
	if(links < j)
		qs(links, j, size, compare);
	if(i + size < rechts)
		qs(i + size, rechts, size, compare);
} else {
	if(i + size < rechts)
		qs(i + size, rechts, size, compare);
	if(links < j)
		qs(links, j, size, compare);
}

SG1

tobidope schrieb:

zu langsam

die Rekursion entartet

Die beiden Punkte konnte ich nicht nachvollziehen. Wie bist Du da drauf gekommen?

tobidope

SG1 schrieb:

tobidope schrieb:

zu langsam

die Rekursion entartet

Die beiden Punkte konnte ich nicht nachvollziehen. Wie bist Du da drauf gekommen?

Ich habe meine sorts getestet. Mein heapsort und der qsort der C-Bibliothek gegen meinen qsort. Leider war der qsort doppelt so schnell wie heapsort und auch schneller als mein quicksort. Das große Problem ist aber, dass mein quicksort bei 100.000 Elementen, wenn ich mich recht entsinne, einen Abgang macht. Stack Overflow ich habe den Aufruf-Stack platt gemacht. Ich werde mal deinen Vorschlag die Rekursion je nach enstandener Feldgröße nach der Partition zu variieren testen. Außerdem bis 10 Elemente insertionsort. Mal sehen was passiert

Gruß Tobias

tobidope

Hallo SG1,

habe meine quicksort jetzt verbessert

static void qs(void *links, void *rechts, size_t size, cmp_fct compare)
{

    char *i = links;
    char *j = (char *) rechts - size;

    if (((char *) rechts - (char *) links) / size + 1 <= 16) /* Felder mit max. 16 Feldern mit insertionsort sortieren */
        return insertionsort(links,
                             ((char *) rechts - (char *) links) / size + 1,
                             size, compare);
    char *pivot = median_of_three(links, rechts, size, compare);

    if (pivot != rechts)
        swap(pivot, rechts, size);
    pivot = rechts;

    do {
        while (compare(i, pivot) < 0)   /* i < pivot */
            i += size;

        while (compare(j, pivot) >= 0 && j >= links)    /* j >= pivot */
            j -= size;

        if (i < j)
            swap(i, j, size);

    } while (i <= j);           /* bis i > j */

    swap(pivot, i, size);

    if (j - (char *) links > (char *) rechts - (i + size)) { /* Rekursion immer zuerst mit dem kleineren Restfeld fortführen,
                                                                um den Aufrufstacl zu entlaste */
        if (links < j)
            qs(links, j, size, compare);
        if (i + size < rechts)
            qs(i + size, rechts, size, compare);
    } else {
        if (i + size < rechts)
            qs(i + size, rechts, size, compare);
        if (links < j)
            qs(links, j, size, compare);
    }
}

Aber irgendwo ist immer noch der Wurm drin.

C-Quicksort
=============

Sortierdauer bei 10000 Elementen (in sec):
Best case:        0.00
Mid case:         0.00
Worst case:       0.01

Sortierdauer bei 100000 Elementen (in sec):
Best case:        0.03
Mid case:         0.06
Worst case:       0.04

 Heapsort
==========

Sortierdauer bei 10000 Elementen (in sec):
Best case:        0.01
Mid case:         0.00
Worst case:       0.01

Sortierdauer bei 100000 Elementen (in sec):
Best case:        0.08
Mid case:         0.10
Worst case:       0.09

 Quicksort
===========

Sortierdauer bei 10000 Elementen (in sec):
Best case:        0.00
Mid case:         0.00
Worst case:       0.19

Sortierdauer bei 100000 Elementen (in sec):
Best case:        0.04
Mid case:         0.06
Worst case:      17.78

Habe swap und median_of_three auf inline erzeugen lassen, aber der Algorithmus scheint noch nicht perfekt. Hints anyone?

Gruß Tobias