Hilfe bei Implementation des quicksort

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