Algo korrekt, und womöglich gar gut?

Bashar

Auch bei einem umgekehrt sortierten Array? Da ergibt sich jedesmal oben=0, müssen durchschnittlich ca. laenge/2 Einträge verschoben werden.

Tachyon

Bashar schrieb:

Auch bei einem umgekehrt sortierten Array? Da ergibt sich jedesmal oben=0, müssen durchschnittlich ca. laenge/2 Einträge verschoben werden.

Jo, stimmt. Das doofe memmove...

btw. scheint stabil zu sein da du nur bei < schiebst, und nicht bei <=
wegen memmove wird sehr viel geschoben, falls memmove allerdings 1:1 in einem prozessorbefehl abgebildet sein sollte und der speicherblock in einem oder zwei takten verschoben wird (egal wie groß), hat der algo tatsächlich eine o(n*log(n)) komplexität. ich werd's mal mit 1 Million Zufallszahlen versuchen und die laufzeit messen im vergleich mit stdlib::qsort bis dann @landauerin

Metatron

S.g. Landauerin!
Aus reiner Neugier habe ich Deinen RingSort() Algorithmus
auf die Probe gestellt und bezüglich Laufzeitverhalten mit
bubbleSort (in der Version von @wikibooks) sowie qsort (in
der Version, welche die stdlib zur Verfügung stellt) ver-
glichen.

Dazu habe ich das folgende kleine Testprogramm geschrieben:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

/* --------------------------------------------------------------\
|---PROGRAMM ZUM VERGLEICH DER LAUFZEIT VON SORTIERALGORITHMEN---|
\---------------------------------------------------------------*/

#define ARRAYGROESSE 100000

/* ----------------------------------\
|---------- BUBBLE SORT --------------|
|--------(c) by wikibooks ------------|
\-------------------------------------*/
void bubbleSort(int* Array, int size)
 {
    int swapped;
    int i, j, temp;
    for (i = 1; i < size; i++)
    {
        swapped = 0;    //this flag is to check if the array is already sorted
        for(j = 0; j < size - i; j++)
        {
            if(Array[j] > Array[j+1])
            {
                temp = Array[j];
                Array[j] = Array[j+1];
                Array[j+1] = temp;
                swapped = 1;
            }
        }
        if(!swapped){
            break; //if it is sorted then stop
        }
    }
 } /* Anmerkung: Einige Syntaxfehler der wikibooks Version mussten
   | ausgebessert werden (Variablen muessen in C am Funktionsbeginn
   \ definiert werden)												*/
/* -------------------------------------*/

/* ----------------------------------\
|---------- RING SORT ----------------|
\------------------------ -----------*/
void RingSort(int* zahl, int laenge){
	int i, oben, unten, hilfe;
	for(i = 1; i < laenge; ++i){
		unten = !(oben = i);
		do{
			hilfe = (oben + unten) >> 1;
			zahl[i] < zahl[hilfe] ? 
				(oben = hilfe) : 
				(unten = hilfe+1);
		}while(oben-unten);
		if(i-oben){
			hilfe = zahl[i];
			memmove(zahl+oben+1, zahl+oben, (i-oben) * sizeof(int));
			zahl[oben] = hilfe;
		}
	}
}
/* ----------------------------------*/

/* ----------------------------------------------\
|------VERGLEICHSFUNKTION FUER STD::QSORT()------|
\-----------------------------------------------*/
int vergleicher(const void* op1, const void* op2){
	return *((int*) op1) - *((int*) op2);
}
/* ---------------------------------------------*/

/* ----------------------------------------------\
|--------------- TESTPROGRAMM -------------------|
\-----------------------------------------------*/
int main(){
	/* -----  VARIABLEN ------ */
	int i;
	LARGE_INTEGER startZeit, endZeit, differenz;	/* zur Zeitmessung */
	int* probe_array_bubble, *probe_array_ring, *probe_array_quick;

	/* ---- ANWEISUNGEN ------ */
	QueryPerformanceFrequency(&differenz);
	printf("Willkommen beim Wettrennen der Sortieralgorithmen!\n"
		"Ein Array mit %d Zahlen wird jeweils durch bubbleSort(),\n"
		"RingSort(), sowie std::qsort() sortiert werden, und an- \n"
		"schliessend wird die jeweilige Laufzeit in der von \n"
		"QueryPerformanceCounter() gelieferten Zeiteinheit aus- \n"
		"gegeben.\n"
		"%I64d Query-Takte entsprechen 1 Sekunde \n\n",
		ARRAYGROESSE,
		differenz.QuadPart);

	/* das Array fuer bubbleSort() wird allokiert */
	probe_array_bubble = (int*) malloc(ARRAYGROESSE*sizeof(int));
	/* das Array fuer RingSort() wird allokiert*/
	probe_array_ring = (int*) malloc(ARRAYGROESSE*sizeof(int));	
	/* das Array fuer stdlib::qsort() wird allokiert */
	probe_array_quick = (int*) malloc(ARRAYGROESSE*sizeof(int));	

	/* die drei Arrays werden mit (den selben) Zufallszahlen gefuellt */
	srand((unsigned int) time(NULL));	
	for(i = 0; i < ARRAYGROESSE; ++i)
		probe_array_bubble[i] = rand();
	memcpy(probe_array_ring, probe_array_bubble, ARRAYGROESSE*sizeof(int));
	memcpy(probe_array_quick, probe_array_bubble, ARRAYGROESSE*sizeof(int));

	/* Hier wird die Laufzeit von bubbleSort() gemessen und  \
	\  anschliessend ausgegeben								*/						
	QueryPerformanceCounter(&startZeit);
	bubbleSort(probe_array_bubble, ARRAYGROESSE);
	QueryPerformanceCounter(&endZeit);
	differenz.QuadPart = endZeit.QuadPart - startZeit.QuadPart; 
	printf("Sortierdauer bubbleSort(): %I64d Query-Takte \n", differenz.QuadPart);
				/* WARNUNG: Bei sehr grossen Werten fuer ARRAYGROESSE (> 1 MIO)
				   benoetigt bubbleSort() 30 Minuten oder laenger. */

	/* Hier wird die Laufzeit von RingSort() gemessen und   \
	\  anschliessend ausgegeben								*/
	QueryPerformanceCounter(&startZeit);
	RingSort(probe_array_ring, ARRAYGROESSE);
	QueryPerformanceCounter(&endZeit);
	differenz.QuadPart = endZeit.QuadPart - startZeit.QuadPart;
	printf("Sortierdauer RingSort(): %I64d Query-Takte \n", differenz.QuadPart);

	/* Hier wird die Laufzeit von stdlib::qsort() gemessen und   \
	\  anschliessend ausgegeben									*/
	QueryPerformanceCounter(&startZeit);
	qsort(probe_array_quick, ARRAYGROESSE, sizeof(int), vergleicher);
	QueryPerformanceCounter(&endZeit);
	differenz.QuadPart = endZeit.QuadPart - startZeit.QuadPart;
	printf("Sortierdauer stdlib::qsort(): %I64d Query-Takte \n", differenz.QuadPart);

	fgetc(stdin);
	return 0;
}

Es wird stillschweigend vorausgesetzt, dass die Sortier-
funktionen jeweils korrekt implementiert sind (ich habe
Deine RingSort() Funktion mit copy+paste so übernommen,
wie sie hier steht).
Mittels QueryPerformanceCounter habe ich dann bei jeweils
unterschiedlich großen Werten für die symbolische Konstante
ARRAYGROESSE die Zeit gestoppt, wie lange bubbleSort(),
RingSort(), und qsort() benötigten, um das Array zu sortieren.

Bezüglich der Ergebnisse habe ich ein Bild zusammengestellt,
in dem mehrere Programmabläufe dokumentiert werden, hierzu
der Link:

http://www.geocities.com/justlikeapill99/sortierBild.jpg

Man sieht dabei recht gut, dass, je größer das zu sortierende
Array wird, RingSort() im Vergleich zu qsort() immer mehr an
Boden verliert, sprich: mit jeder Verzehnfachung der Arraygröße
wird der Unterschied immer deutlicher.
Interessanter Weise arbeitet Dein RingSort() bei kleineren
Arraygrößen (mit weniger als 5000 Einträgen) erheblich
schneller als qsort().
bubbleSort() liegt bereits bei Arrays mit 100 Elementen sowohl
hinter qsort() als auch RingSort() zurück.
Als bubbleSort auf meinem Rechner ein Array mit 1 Million
Einträgen sortieren sollte, war die Funktion nach 30 Minuten
noch immer nicht fertig, worauf mir der Geduldsfaden riss und
ich die bubbleSort Passage im Testprogramm auskommentierte, und
das Programm neu kompilierte.
Aber auch RingSort() benötigte bei 1 Million Zahlen bereits knapp
3 Minuten, um das Array zu sortieren. Nur qsort() 'zaubert' auch
bei derartig riesigen Arrays munter weiter, und benötigt weniger
als 1 Sekunde.

Die Schlussfolgerungen aus diesem Experiment:
(a) Bei kleineren Arrays mit < 5000 Einträgen ist RingSort() am
schnellsten.
(b) Bei größeren Arrays mit > 5000 Einträgen ist qsort() am
schnellsten, und der Vorteil gegenüber RingSort() wird mit zunehmender
Größe des Arrays immer deutlicher.
(c) bubbleSort() ist bereits bei Arrays mit 100 Einträgen langsamer
als die beiden anderen Algorithmen.
(d) Auch der Laufzeitunterschied zwischen RingSort() und bubbleSort()
wird immer deutlicher, je mehr Array-Elemente sortiert werden müssen.
Bei 100.000 Array-Elementen ist RingSort() bereits 30x schneller als
bubbleSort.
(e) In Fällen, in denen sehr viele kleinere Arrays (anstelle eines
einzigen großen Arrays) sortiert werden sollen, scheint RingSort()
gegenüber qsort() im Vorteil zu sein.
(f) RingSort() ist stabil, qsort() nicht. Wenn Daten nach mehreren
Kriterien hintereinander sortiert werden sollen, könnte man RingSort()
versuchen.
(g) In Summe betrachtet bleibt aber qsort() das Non-Plus-Ultra,
es ist immer wieder gespenstisch, wie schnell die Funktion riesige
Arrays mit abermillionen Elementen sortiert. In solchen Fällen ist
qsort() unschlagbar.

@Landauerin: qsort > RingSort > bubbleSort. Bis heute habe ich ehrlich
noch nie etwas von RingSort gehört. Für manche Situationen könnte
man den Algo wohl gar gebrauchen, werde es mir gut merken

mfg

Ich finde diesen Thread hier sehr interessant und klinke mich mit einem aktuellen Problem gerade mal hier ein. Ich habe hier ein Array of strukt:

typedef struct _tobesorted{
	char			*string1;	
	char			*string2[32];
	char			*string3[32];
	int			zahl1;
	int			zahl2;
	int			zahl3;
}tobesorted_t;

tobesorted_t		sort_this[10000];

Per Vorgabe, soll nun diese Struktur wahlweise nach Element 1, Element 2, ... Element x sortiert werden. Z.Z. benutze ich hierfür das Bubblesortverfahren. Mir war bislang nicht bewust, dass dieses Verfahren vergleichsweise langsam ist. Wie kann ich hier die Performance steigern. Ich habe leider keine Ahnung wie ich qsort auf die Struktur anwenden muß. Wer kann mir da helfen?

Machst du für jedes Element eine eigene Vergleichsfunktion, die du an qsort übergibst.

Guckst du:

#include <stdio.h>

typedef struct
{ 
    char *string1;    
    char *string2[32]; 
    char *string3[32]; 
    int	zahl1; 
    int	zahl2; 
    int	zahl3; 
}Test; 

int cmp_string1( const void *a, const void *b )
{
	return strcmp(((Test*)a)->string1, ((Test*)b)->string1 );
}

void view (Test* t, int n, char* s)
{
	int i=0;
	if(s)
		puts(s);
	while(i<n)
		puts(t[i++].string1);
}

int main( void ) 
{ 
	Test t[3] = {0};
	t[0].string1 = "b";
	t[1].string1 = "a";
	t[2].string1 = "c";

    view (t, 3, "unsorted:");
	qsort ((void*)t, 3, sizeof(Test), cmp_string1);
	view (t, 3, "sorted:");

   return 0; 
}

Bashar

Hallo Metatron,

könntest du das ganze mal auf C++ portieren und auch std::sort und std::stable_sort ausprobieren? Dass qsort für kleine Arrays langsam ist kann ich mir gut vorstellen, weil da einfach ziemlich viel Overhead in dieser Funktionspointerkiste drinsteckt.

Könntest du auch noch ein normales Insertion Sort gegen "Ring Sort" (= Insertion Sort mit binärer Suche, wie gesagt) setzen?

(f) RingSort() ist stabil, qsort() nicht. Wenn Daten nach mehreren
Kriterien hintereinander sortiert werden sollen, könnte man RingSort()
versuchen.

Es gibt aber auch stabile O(n log n)-Verfahren, z.B. Merge Sort (das sortiert allerdings nicht in-place).

Bashar schrieb:

könntest du das ganze mal auf C++ portieren und auch std::sort und std::stable_sort ausprobieren?

machs doch selber. den code hat er doch gepostet.

Big Brother schrieb:

qsort ((void*)t, 3, sizeof(Test), cmp_string1);

wozu das (void*) ?
muss das sein?

Bashar

+fricky schrieb:

machs doch selber. den code hat er doch gepostet.

Winapi-Code.

casting n00b schrieb:

wozu das (void*) ?
muss das sein?

nö, ist bestimmt ein versehen.

Bashar schrieb:

+fricky schrieb:

machs doch selber. den code hat er doch gepostet.

Winapi-Code.

doch nur für die messung. QueryPerformanceCounter ist im prinzip nix anderes als 'rdtsc (falls du 'ne x86 box hast).
LARGE_INTEGER ist eine struct aus 2 32-bit werten. 'long long' sollte es auch tun.