BubbleSort, QuickSort, MergeSort, ShakerSort

4 Sortierroutinen in Prozeduren. Ausgeführt werden sie in der main, wo die als Vergleich die Schnelligkeit in Millisekunden angezeigt wird.

Code:

 

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

int Hilfsfeld[100000];// globales Hilfsfeld für MergeSort
int* ErzeugeFeld (int Anzahl)// Funktion soll Feld erzeugen; Zeiger als Rückgabewert(Anfangsadresse des Feldes)
{
int* Zeiger;
srand(time(NULL)); // Initialisieren des Zufallszahlengenerators
Zeiger=(int*)malloc(Anzahl*sizeof(int));// Dynamisches Array; Speicher reserviert; (int*), da malloc ein void zurückgibt
for (int i=0;i < Anzahl; i++) // Feld befüllt; Start bei 1.Position =0; solange < Anzahl
Zeiger[i]=rand(); // mit Zufallszahlen füllen
return Zeiger; // liefert den Wert zurück
}


BubbleSort


void BubbleSort(int* Feld, int Anzahl)// Startadresse als Zeiger; Größe des Feldes
{
int Fertig;// Merker, ob getauscht oder nicht
int Temp; // Dummy

for (int d=1;d {
Fertig=1; // wir sind fertig
for (int e=0;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;
}
if (Fertig==1) break; // wenn ich einmal nicht in der Tauschanweisung war, wird hier abgebrochen
}
}


QuickSort


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

if (Rechts>Links)// anders ausgedrückt: mehr als 1 Element und Feldende; prüfen,ob mindestens 2 Elemente
{
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] LZ++;// laufe weiter
while(Feld[RZ]>=TE && RZ>LZ)// RZ>LZ = Überkreuzung der Zeiger
RZ--; // laufe zurück

if(LZ {
Temp=Feld[LZ];// Tauschen
Feld[LZ]=Feld[RZ];
Feld[RZ]=Temp;
}

}while(LZ
// 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
}
}

 

ShakerSort


void ShakerSort(int* Feld, int Anzahl)
{
int Fertig;// Merker, ob getauscht oder nicht
int Temp; // Dummy

for (int d=1;d {
Fertig=1; // wir sind fertig
for (int e=d-1;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;
}
if (Fertig==1) break; // wenn ich einmal nicht in der Tauschanweisung war, wird hier abgebrochen
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;
}
if (Fertig==1) break; // wenn ich einmal nicht in der Tauschanweisung war, wird hier abgebrochen
}
}

 

MergeSort


void MergeSort(int* Feld, int links, int rechts)// links und rechts für Start und Ende, weil Teilfolgen benötigt werden
{
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
MergeSort(Feld,links, 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,mitte+1,rechts);//dann geht er hierhin und teilt die rechts Seite bis nur noch 2 Elemente da sind, dann fertig; dann ist die rechte Seite fertig

// 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] {
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 //    printf("%d\n", Daten[i]);
}

Kommentar schreiben

Momox.de - Einfach verkaufen.