quicksort

hi,
ich habe ein kleines Problem mit dem quicksort.
Der lautet bei mir so:

qsort(array, durchlaeufe, sizeof (entry), compare_entry);

mit dem compare, das die Einträge der Größe nach sortiert.

int compare_entry (const void * a, const void * b);

int compare_entry(void const *a, void const *b) 
{ 
   int const m = ((entry const *)a)->val; 
   int const n = ((entry const *)b)->val; 
   if (m > n) return 1; 
   else if (n > m) return -1; 
   else return 0; 
}

alles wird sortiert, wie ich es will, jedoch, wenn mehrere gleiche Einträge sind, würde ich gern die Zahl, in der das erste gleiche Element auftritt an 1. Position haben. ZB:
(2,3,1,4,1,5,1,6)
wird sortiert zu:
(1,1,1,2,4,5,6). Dieses erlange ich, jedoch wenn ich dann array[0].val aufrufe, so gibt mir das Programm nicht immer die 3. Position aus, sondern manchmal die 5. und manchmal die 7. Ich hoffe ihr versteht mich.
Wie kann ich beim Sortieren auch die vorherigen Positionen sortiert erhalten?

Bashar

Das geht nicht, QuickSort ist kein stabiler Sortieralgorithmus.

http://de.wikipedia.org/wiki/Stabiles_Sortierverfahren

Bashar schrieb:

QuickSort ist kein stabiler Sortieralgorithmus.

Dann macht man ihn halt über die Vergleichsfunktion stabil.

int compare_entry(void const *a, void const *b)
{
   int const m = ((entry const *)a)->val;
   int const n = ((entry const *)b)->val;
   if (m > n) return 1;
   else if (n > m) return -1;
   return a - b; // Anhand von Adresse einen eindeutigen Unterschied feststellen
}

Was nicht passt, wird passend gemacht.

_--

Das mit dem Pointer wird wohl nicht funktionieren, da sich ja die Adressen der Elemente auch immer wieder ändern.

Man bräuchte schon eine zusätzliche Info die man in den einzelnen Structs ablegt.

Die Zeiger sind direkt aus dem Array entnommen und dass es prinzipiell klappt (ich gebe zu, mein Code ist einfach so dahingeschrieben), siehst bei Betrachtung der Dokumentation:

<a href= schrieb:

Array Sort Function">If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary.

:xmas2:

stimmt leider,
es wird der Fehler ausgegeben:

error C2036: 'const void *': Unbekannte Größe

Ist es denn möglich, bei einer Sortierung, wenn mehrere gleiche Werte sind, den letzten kleinsten Wert außer der Null auszugeben?
Muss man da nicht nur ein wenig an dem Code ändern??