Algo korrekt, und womöglich gar gut?

[Landauerin]

Schönen Abend, zum Zeitvertreib programmiere ich manchmal in C, und da ist mir heute doch tatsächlich ein Geistesblitz gekommen, wie ich in Zukunft ein Feld außerdem noch sortieren könnte. Leider kenne ich mich im Theorie Bereich nicht sonderlich gut aus, deshalb kann ich nicht mit 100% Sicherheit sagen, ob die Funktion funktioniert, wie schnell oder langsam sie im Vergleich zu anderen bekannten Sortier-Methoden ist, usw. Ich habe der Funktion einige Dutzend Male Arrays mit zufälligen Zahlen und zufälliger Größe anvertraut, und bisher hat sie immer funktioniert. Schön wär's natürlich, wenn jemand mit Sicherheit sagen könnte, dass der Algo funktioniert. Ich hab das Ding mal RingSort genannt, nachdem ich sämtliche wikipedia-Einträge durchgestöbert habe und nichts zu finden war, das ähnlich funktioniert.

#include <string.h>
#include <stdio.h>

/* Hier der Versuch, diesen 'RingSort' Algo zu verwenden */
void RingSort(int* zahl, int laenge){
	int i, oben, unten, hilfe; /* (Kommentar 1) s.u. */
	for(i = 1; i < laenge; ++i){ /* (Kommentar 2) s.u. */
		unten = !(oben = i);
		do{ /* ---> (Kommentar 3) s.u. */
			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;
		}
	}
}

/* Testprogramm */
int main(){
	int i;
	int probe_array[] = {25,38,65,12,22,1,-2,6,9,5};
	3
	RingSort(probe_array, 10);

	for(i = 0; i < 10; ++i)
		printf(" %d ", probe_array[i]);

	fgetc(stdin);
	return 0;
}

/* (K1) -> mit Ausnahme dieser vier lokalen Variablen in_place. Die Funktion ist nicht rekursiv, d.h. die vier Var. müssen nur ein einziges Mal bereitgestellt weerden */
/* (K2) -> jedes Element aus dem Array wird nur ein einziges Mal zum Thema, keine doppelt und dreifach verschachtelten Schleifen wie bei so manch anderem
Algo */
/* (K3) -> mit dieser Telefonbuch-Suchvariante findet sich das richtige Plaetzchen auch bei 65000 Elementen im Array nach spätestens 16 Vergleichen */
/* (K4) -> Stabil? -> Keine Ahnung, gute Frage ... weiss nicht mal was das sein soll ? dass der Algo nur sporadisch funktioniert vielleicht? */

So, wenn mir jetzt noch ein Fachmann betätigen könnte, dass der Algo gar einwandfrei korrekt funktioniert, wäre mir sehr geholfen. Bezüglich der Einschätzung der Landauer-O-Laufzeit oder wie das heißt -> kenne mich da wie gesagt nicht so aus wie die Leute in der Wiki, die auessere Schleife wird genau einmal durchlaufen, die innere log(n) oft. Womöglich trifft O(n*log(n)) tatsächlich auf RingSort() zu ?
-> Danke wenn sich jemand damit auskennt _ ansonsten werd' ich wohl weiterhin mit BubbleSort herumspielen, weil mir qsort oder mergesort zu kompliziert sind

[Gast]

Zumindest hast du eine Schleife schön im memmove versteckt

[Bashar]

Wieso schreibst du den Code absichtlich unleserlich?

[Tachyon]

Landauerin schrieb:

[...]nachdem ich sämtliche wikipedia-Einträge durchgestöbert habe und nichts zu finden war, das ähnlich funktioniert.[...]

Quicksort?

[Bashar]

Das ist offensichtlich kein Quicksort. Es handelt sich um Insertion Sort, wobei gegenüber der Standardvariante eine binäre Suche verwendet wird. Die Komplexität ist aber trotzdem O(n^2) (=> Standardübungsaufgabe zu Insertion Sort )

[Tachyon]

Bashar schrieb:

Das ist offensichtlich kein Quicksort. Es handelt sich um Insertion Sort, wobei gegenüber der Standardvariante eine binäre Suche verwendet wird. Die Komplexität ist aber trotzdem O(n^2) (=> Standardübungsaufgabe zu Insertion Sort )

Ja? Also ich komme immer auf O(N log(N)).

[öla]

Warum steht in Zeile 27 eine 3?

[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...

[josi1]

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

[Rüüdiger]

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?

[Big Brother]

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

[Big Brother]

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).

[+fricky]

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.

[casting n00b]

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.

[+fricky]

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.