KJ187 Geschrieben 12. Juli 2004 Teilen Geschrieben 12. Juli 2004 So, haben in letzter Zeit verschiedene Sortier Algorithmen in der Schule gehabt, Thema ANSI C Ich poste hier mal meinen code, hoffe das ihr davon was habt ;-) Über Feedback würd ich mich freuen ;-) Behandelt werden: Bubblesort, Quicksort, Shellsort, Selectsort, Insertsort /* ============================================================================ Autor : Julian Kleinhans Beschreibung: Sortieralgorithmus Verfahren mit Performance-Test ============================================================================ */ /* ============================================================================ Include-Dateien ============================================================================ */ #include <stdio.h> #include <stdlib.h> #include <time.h> /* ============================================================================ Praeprozessoranweisungen ============================================================================ */ #define ANZAHL 500000 #define ANZAHLZUZA 100 #define INIT_TIME 0 #define OK 0 #define ENDE 'x' /* ============================================================================ Globale Variablen ============================================================================ */ int iArray[ANZAHL]; /* Globaler Array, in dem sortiert werden soll */ /* ============================================================================ Funktionsprototypen ============================================================================ */ int func_BubbleSort (); int func_QuickSort (); int func_SelektionSort (); int func_InsertionSort (); int func_ShellSort (); int func_AllSort (void); void sort_BubbleSort (); void sort_QuickSort (); void sort_SelektionSort (); void sort_InsertionSort (); void sort_ShellSort (); void ErzeugeZufallszahlen (void); void Ausgabe (void); /* ============================================================================ Funktion main() ============================================================================ */ int main(void) /* Rückgabewert: 0 ==> alles OK 1 ==> es ist ein Fehler aufgetreten Es werden keine Argumente übergeben! */ { char cItem; do { system("cls"); printf("\n\n"); printf("\tSORTIERALGORITHMEN - HAUPTMENUE (2004 by Julian Kleinhans)\n"); printf("\t==========================================================\n"); printf("\n\n"); printf("\ta: BubbleSort\n"); printf("\tb: QuickSort\n"); printf("\tc: SelektionSort\n"); printf("\td: InsertionSort\n"); printf("\te: ShellSort\n"); printf("\tf: Alle\n\n"); printf("\tx: Ende\n"); printf("\n\n"); printf("\tAuswahl: "); scanf("%c",&cItem); fflush(stdin); cItem = tolower(cItem); switch(cItem) { case 'a': { func_BubbleSort(); break; } case 'b': { func_QuickSort(); break; } case 'c': { func_SelektionSort(); break; } case 'd': { func_InsertionSort(); break; } case 'e': { func_ShellSort(); break; } case 'f': { func_AllSort(); break; } case 'x': { break; } default: { printf("\tUngueltige Auswahl - bitte nochmal probieren!\n\n\n"); system("pause"); } } } while (cItem != ENDE); return OK; } /* ============================================================================ Funktion func_BubbleSort() ============================================================================ */ int func_BubbleSort( ) { clock_t start; clock_t finish; float fGesTime; /*=================================================================================*/ system("cls"); printf("\tBubbleSort Algorithmus\n"); printf("\t============================================================\n\n"); ErzeugeZufallszahlen(); printf("\n\n\tUnsortiert\n"); printf("\t==================================================\n"); Ausgabe(); /*=================================================================================*/ start = clock(); sort_BubbleSort(iArray,ANZAHL); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\n\n\tSortiert\n"); printf("\t==================================================\n"); Ausgabe(); printf("\n\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n\n",ANZAHL,fGesTime); system("Pause"); /*=================================================================================*/ return OK; } /* ============================================================================ Funktion sort_BubbleSort() Bubble Sort ist ein recht einfaches Sortierverfahren. Dabei wird das vollständige Array durchlaufen, und jedes Mal - wenn notwendig - werden die benachbarten Elemente miteinander getauscht. Nach jedem Durchlauf bekommt immer das letzte Element einen festen Platz. Daher macht es auch Sinn, eine rückwärts zählende Schleife von dieser Position an einzusetzen. ============================================================================ */ void sort_BubbleSort(int array[], int elemente) { int i,temp; while(elemente--) for(i = 1; i <= elemente; i++) if(array[i-1]>array[i]) { temp=array[i]; array[i]=array[i-1]; array[i-1]=temp; } } /* ============================================================================ Funktion func_QuickSort() ============================================================================ */ int func_QuickSort( ) { clock_t start; clock_t finish; float fGesTime; /*=================================================================================*/ system("cls"); printf("\tQuickSort Algorithmus\n"); printf("\t============================================================\n\n"); ErzeugeZufallszahlen(); printf("\n\n\tUnsortiert\n"); printf("\t==========\n"); Ausgabe(); /*=================================================================================*/ start = clock(); sort_QuickSort(iArray,iArray+ANZAHL); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\n\n\tSortiert\n"); printf("\t========\n"); Ausgabe(); printf("\n\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n\n",ANZAHL,fGesTime); system("Pause"); /*=================================================================================*/ return OK; } /* ============================================================================ Funktion sort_QuickSort() Ein oft eingesetzter Algorithmus ist Quicksort, da seine Implementierung nicht allzu schwer ist. Aufgrund ihrer häufigen Verwendung wurde diese Funktion in die ANSI C-Bibliothek mit aufgenommen (qsort). Quicksort funktioniert nach dem Prinzip "Teile und herrsche", also rekursiv. Die Daten werden immer in zwei Teile zerlegt und wieder sortiert. Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die Rekursion beendet sich, wenn das Teilstück aus nur noch einem Element besteht. ============================================================================ */ void sort_QuickSort(int *links, int *rechts) { int *ptr1 = links; int *ptr2 = rechts; int w, x; x = *(links + (rechts - links >> 1)); do{ while(*ptr1 < x) { ptr1++; } while(*ptr2 > x){ ptr2--; } if(ptr1 > ptr2) { break; } w = *ptr1; *ptr1 = *ptr2; *ptr2 = w; }while(++ptr1 <= --ptr2); if(links < ptr2) { sort_QuickSort(links, ptr2); } if(ptr1 < rechts) { sort_QuickSort(ptr1, rechts); } } Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
KJ187 Geschrieben 12. Juli 2004 Autor Teilen Geschrieben 12. Juli 2004 /* ============================================================================ Funktion func_SelektionSort() ============================================================================ */ int func_SelektionSort( ) { clock_t start; clock_t finish; float fGesTime; /*=================================================================================*/ system("cls"); printf("\tSelektionSort Algorithmus\n"); printf("\t============================================================\n\n"); ErzeugeZufallszahlen(); printf("\n\n\tUnsortiert\n"); printf("\t==========\n"); Ausgabe(); /*=================================================================================*/ start = clock(); sort_SelektionSort(iArray,ANZAHL); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\n\n\tSortiert\n"); printf("\t========\n"); Ausgabe(); printf("\n\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n\n",ANZAHL,fGesTime); system("Pause"); /*=================================================================================*/ return OK; } /* ============================================================================ Funktion sort_SelektionSort() Dieser Algorithmus sucht sich als Erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Der Vorteil von "Selektion Sort" liegt darin, dass jedes Element höchstens einmal bewegt wird. ============================================================================ */ void sort_SelektionSort(int array[], int elemente) { int i,j,mini,temp; for(i=0; i<elemente; i++) { mini=i; for(j=i+1; j<=elemente; j++) { if(array[j] < array[mini]) mini=j; } temp=array[mini]; array[mini]=array[i]; array[i]=temp; } } /* ============================================================================ Funktion func_InsertionSort() ============================================================================ */ int func_InsertionSort( ) { clock_t start; clock_t finish; float fGesTime; /*=================================================================================*/ system("cls"); printf("\tInsertionSort Algorithmus\n"); printf("\t============================================================\n\n"); ErzeugeZufallszahlen(); printf("\n\n\tUnsortiert\n"); printf("\t==========\n"); Ausgabe(); /*=================================================================================*/ start = clock(); sort_InsertionSort(iArray,ANZAHL-1); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\n\n\tSortiert\n"); printf("\t========\n"); Ausgabe(); printf("\n\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n\n",ANZAHL,fGesTime); system("Pause"); /*=================================================================================*/ return OK; } /* ============================================================================ Funktion sort_InsertionSort() Das Prinzip von "Insertion Sort" (=sortieren durch direktes Einfügen) ist relativ einfach. Die einzelnen Elemente werden wieder von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links weitergereicht. Und das so lange, bis dass bewegte Element größer oder gleich dem Element ist, das an der im Augenblick abgefragten Position liegt. Der Platz für das Element, das verschoben wird, ist frei. Diese Lücke wird mit dem entsprechenden Wert an der richtigen Stelle gefüllt. ============================================================================ */ void sort_InsertionSort(int array[], int elemente) { int i,j,temp; for(i=1; i<=elemente; i++) { temp=array[i]; /*aktuelles Element zwischenspeichern*/ for(j=i; array[j-1] > temp && j > 0; j--) /* So lange der Vorgänger größer ist als das aktuelle Element in temp … */ array[j] = array[j-1]; /*gespeichertes Element an neue Position*/ array[j]=temp; } } /* ============================================================================ Funktion func_ShellSort() ============================================================================ */ int func_ShellSort( ) { clock_t start; clock_t finish; float fGesTime; /*=================================================================================*/ system("cls"); printf("\tShellSort Algorithmus\n"); printf("\t============================================================\n\n"); ErzeugeZufallszahlen(); printf("\n\n\tUnsortiert\n"); printf("\t==========\n"); Ausgabe(); /*=================================================================================*/ start = clock(); sort_ShellSort(iArray,ANZAHL-1); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\n\n\tSortiert\n"); printf("\t========\n"); Ausgabe(); printf("\n\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n\n",ANZAHL,fGesTime); system("Pause"); /*=================================================================================*/ return OK; } /* ============================================================================ Funktion sort_ShellSort() Shellsort ist eine Erweiterung von "Insertion Sort". Anstatt jedes benachbarte Element wie bei "Insertion Sort" zu vergleichen und zu sortieren, vergleicht "Shellsort" jedes n-te Element (bei beliebigem Anfangselement). Damit ist es möglich, Elemente zu sortieren, die in größeren Entfernungen voneinander liegen. Ist der Abstand für n beispielsweise 4, dann setzen sich folgende Gruppen von Elementen mit dem Index 0, 4, 8, 12 … und 1, 5, 9, 13 … 2, 6, 10, 14 … 3, 7, 11, 15 … usw. zusammen. Diese Gruppen werden einzeln sortiert. Danach wird n verringert, und dann werden die Gruppen n-1 sortiert. So lange, bis n==1 ist, und somit im letzten Durchlauf keine Unterteilung mehr stattfindet. Ist n gleich von Anfang an 1, könnten Sie sich den Aufwand sparen, da dies dem "Insertion Sort"-Algorithmus entspräche. Natürlich ist n abhängig von den Werten, die sortiert werden. Man spricht dabei von Distanzfolgen. Je besser diese Folge, desto schneller werden die Daten sortiert. Die Suche nach der optimalen Folge ist Aufgabe des Programmierers. ============================================================================ */ void sort_ShellSort(int array[], int elemente) { int i,j,temp,n; for(n=elemente; n>0; n/=4) /*Distanzfolge für n*/ for(i=n+1; i<=elemente; i++) { temp=array[i]; for(j=i; j>n && array[j-n]>temp; j-=n) array[j]=array[j-n]; array[j]=temp; } } Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
KJ187 Geschrieben 12. Juli 2004 Autor Teilen Geschrieben 12. Juli 2004 /* ============================================================================ Funktion func_AllSort() ============================================================================ */ int func_AllSort(void) { clock_t start; clock_t finish; float fGesTime; /*=================================================================================*/ ErzeugeZufallszahlen(); system("cls"); if(ANZAHL >= 1000000){ printf("\tHaha, dann viel Spass beim warten\n"); printf("\t============================================================\n\n\n"); }else{ printf("\tBitte warten Sie einen Moment\n"); printf("\t============================================================\n\n\n"); } start = clock(); sort_BubbleSort(iArray,ANZAHL); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\tBubbleSort:\n"); printf("\t============================================================\n"); printf("\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n",ANZAHL,fGesTime); start = clock(); sort_QuickSort(iArray,iArray+ANZAHL); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\tQuickSort:\n"); printf("\t============================================================\n"); printf("\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n",ANZAHL,fGesTime); start = clock(); sort_SelektionSort(iArray,ANZAHL); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\tAuswahlSort:\n"); printf("\t============================================================\n"); printf("\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n",ANZAHL,fGesTime); start = clock(); sort_InsertionSort(iArray,ANZAHL-1); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\tInsertionSort:\n"); printf("\t============================================================\n"); printf("\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n",ANZAHL,fGesTime); start = clock(); sort_ShellSort(iArray,ANZAHL-1); finish = clock(); fGesTime = (float)(finish - start) / (float)CLOCKS_PER_SEC; printf("\tShellSort:\n"); printf("\t============================================================\n"); printf("\tDauer der Sortierung von %i Zufallszahlen : %.2f Sekunden\n\n\n\n\n",ANZAHL,fGesTime); system("pause"); /*=================================================================================*/ return OK; } /* ============================================================================ Funktion ErzeugeZufallszahlen() ============================================================================ */ void ErzeugeZufallszahlen(void) { int i; srand(INIT_TIME); for (i = 0; i < ANZAHL; i++) { iArray[i] = 1 + (rand() % ANZAHLZUZA); } } /* ============================================================================ Funktion Ausgabe() ============================================================================ */ void Ausgabe(void) { int i; for (i = 0; i < ANZAHL; i++) { if(i < 9){ printf("\tZahl 0%i: %i\n",(i + 1),iArray[i]); }else{ printf("\tZahl %i: %i\n",(i + 1),iArray[i]); } } } Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.