Unterschiedliche Quicksorts vergleichen

[cart]

Ich habe hier 3 verschiedene Arten von Quicksort und soll diese vergleichen. Erstmal der Code:
quicksort.h:

#ifndef QUICKSORT_H_
#define QUICKSORT_H_

#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include "Item.h"
#include "Array.h"

typedef double Item;

#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define lessThanEqual(A,B) (key(A) <= key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)

int partition (Item a[], int p, int r);
int newpartition (Item a[], int l, int r);
void quicksort_median ( Item a[], int p, int r);
void quicksort_orig ( Item a[], int p, int r);
void quicksort_new ( Item a[], int p, int r);

#endif /*QUICKSORT_H_*/

quicksort.c:

#include "quicksort.h"

int partition (Item a[], int p, int r) {
	int i,j;
	Item x = a[r];
	i = p-1;
	for (j=p; j<=r-1; j++) {
		if ( lessThanEqual(a[j],x) )
		{
			i++;
			compexch( a[i] , a[j] );
		}
	}
	compexch( a[i+1] , a[r] );

	return (i+1);
}

int newpartition (Item a[], int l, int r) { 
	int i = l-1, j = r; Item v = a[r];
	for ( ; ; ) { 
		while (less(a[++i], v));
		while (less(v, a[--j])) 
			if (j == l) break;
		if (i >= j) break;
		exch(a[i], a[j]);
	}
	exch(a[i], a[r]);
	return i;
}

void quicksort_median ( Item a[], int p, int r) {
	int q;
	if ( p <r ) {
		compexch(a[p], a[(r+p)/2]);
		compexch(a[p], a[r]);
		compexch(a[r], a[(r+p)/2]);
		q = partition( a , p , r );
		quicksort_median(a , p   , q-1 );
		quicksort_median(a , q+1 , r   );
	}
}

void quicksort_orig ( Item a[], int p, int r)
{
	int q;
	if ( p <r ) {
		q = partition( a , p , r );
		quicksort_orig(a , p   , q-1 );
		quicksort_orig(a , q+1 , r   );
	}
}

void quicksort_new ( Item a[], int p, int r)
{
	int q;
	if ( p <r ) {
		q = newpartition( a , p , r );
		quicksort_new(a , p   , q-1 );
		quicksort_new(a , q+1 , r   );
	}
}

Am schnellsten ist quicksort_new, das sich allerdings nur durch die Art von partition von dem orig unterscheidet. Ich habe schon rumgegoogelt und diverse Lexika durchsucht. Natürlich habe ich auch die Aufrufe gezählt, die sind allerdings nahezu identisch: 4.000 Aufrufe Abweichung bei 13.000.000 Aufrufen insgesamt und 10.000.000 Elementen pro Array. Das ist also wohl nicht der Grund, warum newpartition einen Vorteil von etwa 30% bringt. Kann mir jemand erklären, warum es soviel schneller ist? Achja, die 30% Geschwindigkeit sind nicht Abhängig von der Menge der Elemente in dem zu sortierenden Array (getestet mit: 10, 100, 1.000, 10.000, 100.000, 1.000.000, 10.000.000, 20.000.000 Elementen).

 

[4GT_DosX]

Der einzige Unterschied muss an den Partitionen liegen. Die Variablendeklarationen in den Partitionen gleichen sich.
In der alten Variante wird die For Schleife durchlaufen bis die Abbruchbedingung gegeben ist.
In der new Variante wird eine leere For Schleife losgelassen, mit zwei breaks als Aussprungpunkt. Da die Vergleiche (Lesezugriffe) und Erhöhungen/Austauschungen (Schreibzugriffe) sich zwischen beiden nicht so extrem unterscheiden, würd ich sagen dass sich die Durchläufe der Schleife unterscheiden - insbesondere durch

if(j==l) break;

Dieser Befehl findet sich im alten nämlich nicht. Einfach mal nen Debugger anschmeissen und schauen wie oft die Schleife bei identischem Wert im Array und selber Arraygröße in beiden Verfahren durchläuft.

 

[Whcttyh]

welche aufrufe hast du gezählt? ich könnte mir vorstellen, dass es in partition mehr vertauschungen als in newpartition gibt, da in newpartition die elemente über größere distanzen vertauscht werden. ist jetzt aber nur geraten, vermutlich ganz falsch

 

[cart]

Hmm ja, dass es an newpartition im Vergleich zu partition liegt ist klar. Ich habe allerdings die Durchläufe der for-Schleifen counten lassen und es sind bei 10.000.000 Elementen pro Array bei beiden etwa 13.000.000 Durchläufe, bei newpartition allerdings etwa 4.000 weniger. Ob es wirklich nur daran liegt, dass die Abbruchbedingung bei newpartition öfter erreicht wird als bei der alten?

 

[4GT_DosX]

Es bringt dir in solch einen Fall nicht viel, den Algorithmus im Großen zu untersuchen - daraus wird man einfach nicht schlau. Nimm dir lieber ein Array in der Größe von 10 oder kleiner und versuch es daran manuell nachzuvollziehen.
Ich hab mir die Quelltexte mal auf Integer umgeschrieben, da ich die "Item.h" nicht habe und an nem 10er Array ausprobiert. Da merkt man zB dass die Schleife in newpartition deutlich schneller beendet wird als im alten Teil.

partition
For-Schleifendurchläufe: 22
davon Umwechslungen: 12
partition_new
For-Schleifendurchläufe: 11
davon Umwechslungen: 5

bei folgendem Array: int array_a[10]={8,6,0,9,3,1,7,4,5,2};

 

[cart]

K werd ich mal machen. Thx für den Tipp