Tipps & Tricks
Bubble- Merge- Quick- Sort
|
#include "stdio.h" #include "stdlib.h" #include "time.h" // globales Hilfsfeld für Merge-Sort int Hilfsfeld[100000]; // Funktion soll Feld erzeugen; Zeiger als Rückgabewert(Anfangsadresse des Feldes) int* ErzeugeFeld (int Anzahl) { int* Zeiger; // Initialisieren des Zufallszahlengenerators srand(time(NULL)); // Dynamisches Array; Speicher reserviert; (int*), da malloc ein void zurückgibt Zeiger=(int*)malloc(Anzahl*sizeof(int)); // Feld befüllt; Start bei 1.Position =0; solange < Anzahl for (int i=0;i < Anzahl; i++) // mit Zufallszahlen füllen Zeiger[i]=rand(); return Zeiger; // liefert den Wert zurück } // Startadresse als Zeiger; Größe des Feldes void BubbleSort(int* Feld, int Anzahl) { int Fertig; // Merker, ob getauscht oder nicht int Temp; // Dummy for (int d=1;d<Anzahl;d++) // Durchlaufscheife { Fertig=1; // wir sind fertig // Durchläufe = Anzahl -1, da bis zum Vorletzten vergleichen kann; werden die // Durchlaufanzahl höher, wird der vorletzte Tauschwert nach vorne verschoben ( Anzahl-d) for (int e=0;e<Anzahl-d;e++) if (Feld[e]>Feld[e+1]) // Vergleich Zahl mit Nachfolger { Fertig=0; // nicht getauscht, nicht fertig Temp=Feld[e]; Feld[e]=Feld[e+1]; Feld[e+1]=Temp; } // wenn ich einmal nicht in der Tauschanweisung war, wird hier abgebrochen if (Fertig==1) break; } } void QuickSort(int* Feld, int Links, int Rechts) // welches Feld, Startindex (links), Endindex (rechts) { int TE; // Trennelement int LZ; // Zeiger von links int RZ; // Zeiger von rechts int Temp; // zum Tauschen // anders ausgedrückt: mehr als 1 Element und Feldende; prüfen,ob mindestens 2 Elemente if (Rechts>Links) { TE=Feld[Rechts]; // Wert der ganz rechts steht, wird als Trennelement festgelegt LZ=Links; // Index von Links festgelegt, wo der Zeiger steht; hier zum Start Index = 0 RZ=Rechts-1; // Index von Rechts festgelegt; Rechts - 1, da Rechts schon das TE ist do { while(Feld[LZ]<TE) // solange Wert an der Position des Linkszeigers < ist als das TE LZ++; // laufe weiter while(Feld[RZ]>=TE && RZ>LZ)// RZ>LZ = Überkreuzung der Zeiger RZ--; // laufe zurück if(LZ<RZ) // Zeiger haben sich noch nicht erreicht { Temp=Feld[LZ]; // Tauschen Feld[LZ]=Feld[RZ]; Feld[RZ]=Temp; } }while(LZ<RZ); // solange sich die Zeiger nicht treffen oder nicht aneinander vorbeilaufen // Trennelement einfügen (tauschen) Temp=Feld[LZ]; Feld[LZ]=TE; Feld[Rechts]=Temp; // Wert aus Temp wird an Rechts geschrieben QuickSort(Feld,Links,LZ-1); // nun haben wir 2 Felder, hier wird das linke Feld sortiert QuickSort(Feld,LZ+1,Rechts); // hier wird das rechte Feld sortiert } } void ShakerSort(int* Feld, int Anzahl) { int Fertig; // Merker, ob getauscht oder nicht int Temp; // Dummy for (int d=1;d<Anzahl;d++) // Durchlaufscheife { Fertig=1; // wir sind fertig for (int e=d-1;e<Anzahl-d;e++) // Durchläufe = Anzahl -1, da bis zum Vorletzten vergleichen kann; werden die // Durchlaufanzahl höher, wird der vorletzte Tauschwert nach vorne verschoben ( Anzahl-d) if (Feld[e]>Feld[e+1]) // Vergleich Zahl mit Nachfolger { Fertig=0; // nicht getauscht, nicht fertig Temp=Feld[e]; Feld[e]=Feld[e+1]; Feld[e+1]=Temp; } // wenn ich einmal nicht in der Tauschanweisung war, wird hier abgebrochen if (Fertig==1) break; Fertig=1; for (int a=Anzahl-d-1;a>=d;a--) if (Feld[a-1]>Feld[a]) { Fertig=0; Temp=Feld[a]; Feld[a]=Feld[a-1]; Feld[a-1]=Temp; } // wenn ich einmal nicht in der Tauschanweisung war, wird hier abgebrochen if (Fertig==1) break; } } // links und rechts für Start und Ende, weil Teilfolgen benötigt werden void MergeSort(int* Feld, int links, int rechts) { int mitte; // zum Teilen in der Mitte int rz; // Rechtszeiger int lz; // Linkszeiger //printf(" %d %d %d\n" ,MergeSort(Feld, links, rechts); // Zum Testen if (rechts>links) // mind. 2 Elemente { //Teilfolgen erzeugen mitte=(rechts+links)/2; // Bestimmen der Mitte // Rekursion zum Weiterteilen, teilt solange bis nur noch 2 Elemente da sind // wird immer wieder neuaufgerufen, bis er fertig ist; linke Seite jetzt fertig MergeSort(Feld,links, mitte); // Dann geht er hierhin und teilt die rechts Seite bis nur noch 2 Elemente da sind, // dann fertig; dann ist die rechte Seite fertig MergeSort(Feld,mitte+1,rechts); // Zusammenführen der Teilfolgen ins Helfsfeld // dabei rechte Teilfolge drehen for (int i=links;;i<=mitte;i++) hilfsfeld[i]=Feld[i]; // ins Hilfsfeld werden die Werte des Feldes kopiert; linke Teilfolge for (int i=mitte+1;i<=rechts;i++) hilfsfeld[mitte+rechts+1-i]=Feld[i]; // rechte Teilfolge, kopieren in Hilfsfeld // Kopieren ins Originalfeld, dabei sortieren lz=links; //Start des linken Zeigers rz=rechts; // Start des rechten Zeigers for (int i=links;i<=rechts;i++) // von links nach rechts im Originalarray if (hilfsfeld[lz]<hilfsfeld[rz]) { Feld[i]=hilfsfeld[lz]; // setze im Originalarray links das Element aus hilfsfeld, wo der lz steht lz++; // lz nach rechts } else { Feld[i]=hilfsfeld[rz]; rz--; } } } void main() { int* Daten; // Zeiger für die Rückgabe const int Menge=10000; // Elemente int Start; // für Zeitanzeige int Ende; // für Zeitanzeige for (int i=0;i<5;i++) // mehrere Durchläufe { Daten=ErzeugeFeld(Menge); Start=clock(); // Start als Systemzeit BubbleSort(Daten,Menge); // weil BubbleSort oben eine Prozedur ist, kein Rückgabewert Ende=clock(); printf("BubbleSort: %d\n", Ende-Start); //Zeitanzeige Daten=ErzeugeFeld(Menge); Start=clock(); QuickSort(Daten,0,Menge-1); // Rechts ist Menge-1= Index ( bei 100 gehts von 0-99) Ende=clock(); printf("QuickSort: %d\n", Ende-Start); // Zeitanzeige Daten=ErzeugeFeld(Menge); Start=clock(); ShakerSort(Daten,Menge); // Rechts ist Menge-1= Index ( bei 100 gehts von 0-99) Ende=clock(); printf("ShakerSort: %d\n", Ende-Start); // Zeitanzeige*/ } //Daten=ErzeugeFeld(Menge); //ShakerSort(Daten,Menge); //for (int i=0;i<Menge;i++) // Anzeige // printf("%d\n", Daten[i]); } |
Sie benötigen den Status Voll-User, um diese Datei herunterzuladen...
Bewerten
Anmelden/Registrieren
