hi, ich bin gerade dabei das ich ein Sotierverfahren schreibe mit einem Menue und die Zahlen bzw. Buchstaben soll von einer Textdatei an das C-Programm übergeben werden !
Aber irgendwie sotiert, Insortionsort, Heapsort, Shellsort, Quicksort nicht so wie ich mir das vorstelle !
Denke, ich hab irgendwie einen Parameterfehler ... Bitte schaut euch mal mein Problem an !
Grüße !!!
Code
/*-----------------------------------------------------------------------------\
Legende zur besseren Lesung: ||
---------------------------- ||
Bookmark0: includes ||
Bookmark1: main ||
Bookmark2: menü ||
Bookmark3: insertionsort_hilfe ||
Bookmark4: shellsort_hilfe ||
Bookmark5: heapsort_hilfe ||
Bookmark6: quicksort_hilfe ||
Bookmark7: scanfield ||
||
------------------------------------------------------------------------------*/
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
//-includes---------------------------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
#include<conio.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream.h>
#include<time.h>
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
//-Prototypes-------------------------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
void insertionsort_hilfe();
void shellsort_hilfe();
void heapsort_hilfe();
void quicksort_hilfe();
void insertionsort(char *, int);
void shellsort(char*, int);
void quicksort(char *, int, int);
void buildheap(char *, int);
void downheap(char *, int , int);
void exchange(char *, int , int);
void heapsort(char *, int);
void start();
void beenden();
void mitwirkende();
void vorwort();
int scanfield(char*, int);
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
//-Hauptfunktion----------------------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
int main(int argc, char* argv[])
{
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Variablendeklarationen---------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int zd=1; //zähler als Abbruchbedingung für die Schleifen zum Dateieinlsesen
int index=0; //index zur Speicherung der einzelnen Zeichen in das feld "zeichenfeld"
char chd; //Einzelzeichen für die Eingabe <J> <N> in der Schleife zum öffnen der Datei
long groesse; //Variable zur Speicherung der benötigten Größe des Feldes
char filename[255]; //Feld zur Eingabe der zu öffnenden Datei, falls dies nicht per Kommandozeile
//geschehen ist
FILE* datei;
char *zeichenfeld; //das Feld wo die Zeichen der Datei hineingeschreiben werden
int auswahl=0, wahl=0; //die beiden Variablen für das Menü
int scanfieldv=0; //Variable für scanfield
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Abschnitt zum auslesen der Datei-----------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Aufruf einer Datei, falls sie nicht übergeben worden ist!
if(argc<2) { //wenn argc <2 ist dann ist kein Kommandozeilenargument übergeben worden
clrscr();
textcolor(10);
cprintf("\r\aSie haben dem Programm keine Datei uebergeben!\n");
cprintf("\rBitte wenden Sie sich an die Hilfe, oder geben Sie jetzt den\n");
cprintf("\rDateinamen ein.\n\n");
while(zd!=0) { //eine Abbruchbedingung um die Wiedereingabe nicht zu einer
//unendlosschleife zu machen
printf("\nBitte geben Sie den Dateinamen an: (Endung auch) ");
scanf("%s",&filename); //Wenn kein Kommandozeilenargument übergeben wird wird der
printf("\n\n"); //Benutzer aufgefordert einenn Dateipfad einzugeben
datei=fopen(filename,"rb");
if(datei==NULL) { //Wenn der NULL- Zeiger übergeben wird, wird man gefragt ob
//man den dateinamen/pfad nocheinmal eingeben möchte
clrscr();
printf("Die Datei konnte nicht geoeffnet werden!\n\n");
fflush(stdin);
printf("Wollen Sie es nocheinaml versuchen? <J> <N>");
scanf("%c",&chd);
if(chd=='N' || chd=='n') { //Die Abbruchbedingung um das Programm zu beenden
clrscr();
printf("\tAuf Wiedersehen!");
printf("\t<mit Taste Beenden>");
getch();
exit(1);
}
}
else
zd=0;
}
}
//Falls Sie übergeben worden ist
else { //Wenn argc 2 oder größer ist, weiß man dass ein Kommandozeilen Argument übergeben
//worden ist
while(zd!=0) { //eine Abbruchbedingung um die Wiedereingabe nicht zu einer
//unendlosschleife zu machen
datei=fopen(argv[1], "rb");
if(datei==NULL) { //Wird der NULL- Zeiger übergeben kann man den Dateipfad auch
// während des Programmaublaufes noch ändern
clrscr();
printf("Ihre uebergebene Datei konnte nicht geoeffnet werden!\n");
fflush(stdin);
printf("Wollen Sie eine andere Datei oeffnen? <J> <N> ");
scanf("%c",&chd);
if(chd=='N' || chd=='n') { //Die Abbruchbedingung um das Programm zu beenden
clrscr();
printf("\tAuf Wiedersehen!");
printf("\t<mit Taste Beenden>");
getch();
exit(1);
}
else
zd=0;
}
}
}
//Hier ist die Datei bereits erfolgreich geöffnet, nun wird der Inhalt der Datei
//in ein Feld gespeichert, sodass das Feld an die einzelenen Sortierverfahren
//übergeben werden kann
//durchsuchen der Datei, um zu wissen wieviele zeichen benötigt werden
fseek (datei, 0, SEEK_END); //Der Dateizeiger wird an das Ende gesetzt
groesse = ftell(datei); //Die Position wird als groesse gespeichert
rewind(datei); //die datei wird geschlossen und wieder geöffnet
zeichenfeld =(char *) malloc(groesse); //Speicherallokation für das Feld "zeichenfeld"
index = 0;
int zaehler=0;
while(1) //Endlosschleife mit Abbruchbedingung zur Speicherung
{
zaehler++; //der einzelnen zeichen in der Datei
int c = fgetc (datei); //das Zeichen wird auf c gelegt
if (c == EOF) //Abbruchbedingung wenn das Dateiende ereicht ist
break;
zeichenfeld[index++] = (char)c; //Speicherung der Zeichen in das dafür vorgesehene Feld
}
zaehler=zaehler-1;
printf("%d\n", zaehler); //Zählt wieviele Elemente in der Datei sind
//for (index=0; index<groesse; index++) //Test zur Ausgabe
// putchar (zeichenfeld[index]); //Funktioniert! :-)
//getch();
//scanfieldv=scanfield(zeichenfeld,groesse); //noch nicht fertig
clrscr();
start(); //Aufruf des Titelbildes
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Menü---------------------------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
while(1) {
clrscr();
textcolor(10);
printf("\n\r");
cprintf("\r .. \n");
cprintf("\r MMMMMMM EEEE NNN N U U \n");
cprintf("\r M M M E--- N NN N U U \n");
cprintf("\r M M M EEEE N NNN UUUU \n");
cprintf("\r ---------------------------\n");
printf("\n\n");
printf("\rBitte treffen Sie eine Auswahl....");
printf("\n\n\n\n");
printf("\t -1- Insertion- Sort \n");
printf("\t -2- Shell- Sort \n");
printf("\t -3- Heap- Sort \n");
printf("\t -4- Quick- Sort \n");
printf("\n");
printf("\t -5- Mitwirkende \n");
printf("\t -6- Vorwort \n");
printf("\t -7- Beenden \n");
printf("\n\n\t Ihre Auswahl: ");
scanf("%d",&auswahl);
fflush(stdin); //um den Tastaturpuffer zu leeren, sonst kann es zu einem
//Fehler kommen
switch(auswahl) { //switch- Anweisung für die Auswahl der Menü-Funktionen
case 1:
m1: //goto Sprungmarke, dass nach aufruf der Hilfe man wieder in
//dieses Menü gelangt, m bedeutet menü
textcolor(10);
clrscr();
printf("\t +++ Insertionsort +++");
printf("\n\n");
printf("\t\r -1- Start\n");
printf("\t\r -2- Hilfe\n");
printf("\t\r -3- Hauptmenue\n\n");
printf(" Ihre Auswahl:");
scanf("%d",&wahl);
switch(wahl){
case 1: clrscr(); insertionsort(zeichenfeld, zaehler); continue;
case 2: clrscr(); insertionsort_hilfe(); goto m1;
case 3: continue; }
case 2:
m2: //goto Sprungmarke, dass nach aufruf der Hilfe man wieder in
//dieses Menü gelangt
textcolor(10);
clrscr();
printf("\t +++ Shellsort +++");
printf("\n\n");
printf("\t\r -1- Start\n");
printf("\t\r -2- Hilfe\n");
printf("\t\r -3- Hauptmenue\n\n");
printf(" Ihre Auswahl:");
scanf("%d",&wahl);
switch(wahl){
case 1: clrscr(); shellsort(zeichenfeld, zaehler); continue;
case 2: clrscr(); shellsort_hilfe(); goto m2;
case 3: continue; }
case 3:
m3: //goto Sprungmarke, dass nach aufruf der Hilfe man wieder in
//dieses Menü gelangt
textcolor(10);
clrscr();
printf("\t +++ Heapsort +++");
printf("\n\n");
printf("\t\r -1- Start\n");
printf("\t\r -2- Hilfe\n");
printf("\t\r -3- Hauptmenue\n\n");
printf(" Ihre Auswahl:");
scanf("%d",&wahl);
switch(wahl){
case 1: clrscr(); heapsort(zeichenfeld,zaehler);continue;
case 2: clrscr(); heapsort_hilfe(); goto m3;
case 3: continue; }
case 4:
m4: //goto Sprungmarke, dass nach aufruf der Hilfe man wieder in
//dieses Menü gelangt
textcolor(10);
clrscr();
printf("\t +++ Quicksort +++");
printf("\n\n");
printf("\r\t -1- Start\n");
printf("\r\t -2- Hilfe\n");
printf("\r\t -3- Hauptmenue\n\n");
printf("\r Ihre Auswahl:");
scanf("%d",&wahl);
switch(wahl){
case 1: clrscr(); quicksort(zeichenfeld,0,zaehler); continue;
case 2: clrscr(); quicksort_hilfe(); goto m4;
case 3: continue; }
case 5: clrscr(); mitwirkende(); continue;
case 6: clrscr(); vorwort(); continue;
case 7: clrscr(); beenden(); continue;
default:printf("\n\nSie haben eine Falsche eingabe gemacht!"); getch();
//Fall für falsche Eingabe
}
}
//hier wird kein Return code benötigt, da der code hier nie erreicht wird
//durch die Endlosschleife des Menüs, die beendigung erfolgt durch die
//Funktion beenden
} //main-----------------------------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
//-Funktionen-------------------------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\\
void start()
{
clrscr();
printf("\n");
textcolor(15);
cprintf("\r\n1238912345678912345675678912345678912345678912345678912483456789");
cprintf("\r\n8912345678912345678912345678912345675675678912345678912345678343");
cprintf("\r\n8912345678912345675678923456756756789123912345678912345445678343");
printf("\n\n");
textcolor(10);
cprintf("\r+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ \n");
textcolor(15);
cprintf("\r--------------------------------------------------------------- \n");
printf("\n");
printf("\r <<<<<<<<< ======= ======== ======= ======== >>>>>>>>> \n");
printf("\r <<<<<<<<< || || || || || || >>>>>>>>> \n");
printf("\r <<<<<<<<< ======= || || ||===|| || >>>>>>>>> \n");
printf("\r <<<<<<<<< || || || || == || >>>>>>>>> \n");
printf("\r <<<<<<<<< ======= ======== || == || >>>>>>>>> \n");
printf("\n");
textcolor(15);
cprintf("--------------------------------------------------------------- \n");
textcolor(10);
cprintf("\r+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ \n");
textcolor(15);
cprintf("\r\n1238912345678912345675678912345678912345678912345678912483456789");
cprintf("\r\n8912345678912345678912345678912345675675678912345678912345678343");
cprintf("\r\n1238912345678912345675678912345678912345678912345678912483456789");
printf("\n\n\n\t\t\t <Taste druecken>\n");
getch();
clrscr();
} //Funktion2_Start
//******************************************************************************
void mitwirkende()
{
printf("\t Brandstetter Markus:\n\n");
printf("geboren am 28.9.1988; Hobbys/Freizeitbeschaeftigungen: Computer, \n");
printf("Schlagzeug, Fortgehen,Auto fahren,...\n");
printf("Wohnhaft in Hagenberg");
printf("\n\n\n");
printf("\t Troppmaier Michael:\n\n");
printf("geboren am 11.1.1988; Hobbys/Freizeitbeschaeftigungen: Auto fahren \n");
printf("(Ford Orion), Fortgehen,...\n");
printf("\n\n\n");
printf("\t Zoepfl Juergen:\n\n");
printf("geboren am 17.10.1988; Hobbys/Freizeitbeschäeftigungen: Computer, \n");
printf("forgehen, Webdesign, ... \n");
printf("Wohnhaft in Villaring");
getch();
} //Funktion3_Mitwirkende
//******************************************************************************
void vorwort()
{
textcolor(10);
printf("\n");
cprintf("-------------------------------------------------- \n");
printf("\r vv vv oooo rrrr w w w oooo rrrr ttttt \n");
printf("\r vv vv o o rrrr w w w o o rrrr t \n");
printf(" vv oooo r \\ wwwwwww oooo r \\ t \n");
cprintf("-------------------------------------------------- \n");
printf("\n");
printf("Die gesamte 2ahi im Jahrgang 04/05 musste auf die Anweisung \n");
printf("der beiden Proffessoren, Herrn Poeschko und Frau Hofer, in einem \n");
printf("Team ein Projekt ausarbeiten, wie es schon manche Klassen vor uns \n");
printf("machen mussten. \n");
printf("\n");
printf("Es gibt 9 Gruppen zu jeweils 3 Mitgliedern, in unserer Gruppen sind \n");
printf("dies: Markus Brandstetter (Projektmanagement), Jürgen Zoepfel \n");
printf("(Hauptentwickler) und Troppmaier Michael der sich der Dokumentation \n");
printf("widmete.\n");
printf("\nDarueber hinaus gab es 3 Aufgabenstellungen, die die jeweiligen \n");
printf("Gruppenleiter sich untereinander auslosten. Unsere Gruppe erhielt \n");
printf("die Projektnummer 1. Das Projekt handelt ueber 4 verschieden Sortier-\n");
printf("verfahren. Unsere Loesung der Aufgabenstellung ist dieses Programm. \n");
printf("\n");
printf("Wir hoffen Sie werden viel Spass beim Ausprobieren haben.\n");
printf("\n");
cprintf("Copyright by MJM 2005\n");
cprintf("\rAll rights reserved");
getch();
} //Funktion4_Vorwort
//******************************************************************************
void insertionsort_hilfe()
{
/*int i;
int test_array[] = { 5, 2, 7, 9, 1, 4, 3, 8, 6 };
int N = sizeof(test_array)/sizeof(int);
*/
textcolor(15);
cprintf("\r I NN N SSSSS EEEEE RRRRR TTTTT I OOOOO NN N \n");
cprintf("\r I N NN N S E R R T I O O N NN N \n");
cprintf("\r I N NN N SSSSS EEEEE RRRRR T I O O N NN N \n");
cprintf("\r I N NNN S E R == T I O O N NNN \n");
cprintf("\r I N NN SSSSS EEEEE R == T I OOOOO N NN \n");
printf("\n");
printf(" ssss \n");
printf(" s (Sortieren \n");
printf(" ssss oooo rrrr ttttt durch \n");
printf(" s o o r--r t Einfuegen) \n");
printf(" ssss oooo r \\ t \n");
printf("\n\n");
printf("Zu Anfang und nach jedem Schritt des Verfahrens besteht die zu \n");
printf("sortierende Folge a0, ..., an-1 aus zwei Teilen: Der erste Teil \n");
printf("a0, ..., ai-1 ist bereits aufsteigend sortiert, der zweite Teil \n");
printf("ai, ..., an-1 ist noch unsortiert. \n");
printf("\n\n");
printf("Das Element ai wird als naechstes in den bereits sortierten Teil \n");
printf("eingefuegt,indem es der Reihe nach mit ai-1, ai-2 usw. verglichen \n");
printf("wird. Sobald ein Element aj mit ajai gefunden wird, wird ai hinter \n");
printf("diesem eingefuegt. Wird kein solches Element gefunden,wird ai an \n");
printf("den Anfang der Folge gesetzt. ");
getch();
clrscr();
printf("Damit ist der sortierte Teil um ein Element laenger geworden. \n");
printf("Im naechsten Schritt wird ai+1 in den sortierten Teil eingefuegt \n");
printf("usw. Zu Anfang besteht der sortierte Teil nur aus dem Element a0; \n");
printf("zum Schluss aus allen Elementen a0, ..., an-1. \n");
printf("\n\n");
printf("|- der rechte Teil ist bereits sortiert!\n\n");
printf("Beispiel: 6 8 1 4 5 3 7 2\n\n");
printf("6|8 1 4 5 3 7 2 \n");
printf("6 8|1 4 5 3 7 2 \n");
printf("1 6 8|4 5 3 7 2 \n");
printf("1 4 6 8|5 3 7 2 \n");
printf("1 4 5 6 8|3 7 2 \n");
printf("1 3 4 5 6 8|7 2 \n");
printf("1 3 4 5 6 7 8|2 \n");
printf("1 2 3 4 5 6 7 8| \n");
getch();
clrscr();
/*insertion(test_array, N-1);
printf("Die Sortierte Reihenfolge lautet: \n\n\n\n");
for(i = 0; i < N; i++)
printf(" %d ", test_array[i]);
printf("\n");
getch();
*/
}//Funktion6_insertion_hilfe
//******************************************************************************
void shellsort_hilfe()
{
/*int i;
int test_array[] = { 5, 0, 2, 7, 9, 1, 4, 3, 8, 6 };
int N = sizeof(test_array)/sizeof(int);
*/
textcolor(15);
cprintf("\rSSSSSS H H EEEEEE L L S SSSS OOOOOOO RRRRRRR TTTTTTT \n");
cprintf("\rS H H E L L S O O R R T \n");
cprintf("\rSSSSSS HHHHHH EEEEEE L L SSSSSS O O RRRRRRR T \n");
cprintf("\r S H H E L L S O O R == T \n");
cprintf("\rSSSSSS H H EEEEEE LLLLLL LLLLLL SSSSSS OOOOOOO R == T \n");
printf("\n");
printf("\rDie Idee des Verfahrens ist, die Daten als zweidimensionales \n");
printf("Feld zu arrangieren und spaltenweise zu sortieren Dadurch wird eine \n");
printf("Grobsortierung bewirkt. Dann werden die Daten als schmaleres \n");
printf("zweidimensionales Feld angeordnet und wiederum spaltenweise sortiert.\n");
printf("Dann wird das Feld wiederum schmaler gemacht usw. Zum Schluss s \n");
printf("besteht das Feld nur noch aus einer Spalte. \n\n");
printf("Werden die Feldbreiten geschickt gewählt, reichen jedesmal wenige \n");
printf("Sortierschritte aus, um die Daten spaltenweise zu sortieren bzw. \n");
printf("am Ende, wenn nur noch eine Spalte vorhanden ist,vollständig zu \n");
printf("sortieren. Die Effizienz von Shellsort hängt von der Folge der \n");
printf("gewählten Feldbreiten ab. \n");
printf("\n");
printf("Beispiel: 5 4 3 2 1\n\n");
printf("5(0) 4(1) -> 3 2 -> 1 2 \n");
printf("3(2) 2(3) -> 5 4 -> 3 4 -> 1 2 3 4 5 \n");
printf("1(4) -> 1 -> 5 \n");
getch();
clrscr();
/*shellsort(test_array, N-1);
printf("Die Sortierte Reihenfolge lautet: \n\n\n\n");
for(i = 0; i < N; i++)
printf("%d ", test_array[i]);
printf("\n");
getch();
*/
} //Funktion8_shellsort_hilfe
//******************************************************************************
void heapsort_hilfe()
{
textcolor(15);
cprintf("\r H H EEEEE AAAA PPPPP SSSSS OOOOO RRRRR TTTTT \n");
cprintf("\r H H E AA AA P P S O O R R T \n");
cprintf("\r HHHHH EEEEE AA AA PPPPP SSSSS O O RRRRR T \n");
cprintf("\r H H E AAAAAAAAAA P S O O R == T \n");
cprintf("\r H H EEEEE AA AA P SSSSS OOOOO R == T \n");
printf("\n\n");
printf("Der Sortieralgorithmus Heapsort( auch Haldensortierung) arbeitet \n");
printf("nach dem Prinzip, dass er das vorhandene Feld zum sortieren \n");
printf("zerlegt und die einzelnen Teilfelder vergleicht und sortiert. \n");
printf("Diese Zerlegung erfolgt dadurch, dass das Feld in einen Binaerbaum \n");
printf("umgewandeltw wird bzw. als solcher aufgefasst wird. Solch ein Baum \n");
printf("wird Heap genannt.\n");
printf("\n");
cprintf("Ein Heap muss prinzipiell folgende Eigenschaften erfuellen : \n\n");
printf("\r- binaerer Aufbau (jeder Knoten hat hoechstens zwei Nachfolger) \n");
printf("- balanciert( rechtes Blatt ist immer nachfolgender Nachbar des \n");
printf(" linken Blatts der Wurzel) \n");
printf("- lueckenlos( linkslastig - lueckenlose Zuordnung in einer Ebene von\n");
printf(" links nach rechts) \n");
printf("- die Unterbaeume sind wieder Heaps \n");
printf("- die Wurzel ki hat als Nachfolger die Werte k2i und k2i+1 \n");
getch();
clrscr();
printf(" k1 \n");
printf(" / \\ \n");
printf(" k2 k3 \n");
printf(" / \\ / \\ \n");
printf(" k4 k5 k6 k7 \n");
printf(" / \\ / \\ / \n");
printf(" k8 k9 k10 k11 k12 \n");
printf("\n\n");
printf("- k1 ist dadei die Wurzel von k2 und k3 \n");
printf("- k1 bis k6 sind Knoten \n");
printf("- die Nachfolger eines Knoten sind die Blaetter (z.B. k8 und \n");
printf(" k9 von k4 )\n\n");
printf("Zum Sortieren mit Heapsort muss der Baum die Heapbedingung erfüllen .\n");
printf("Heapbedingung : die Wurzel enthält den maximalen Wert aller Knoten.\n");
printf("Zum Herstellen der Heapbedingung wird ein Knoten mit seinen \n");
printf("Nachfolgern verglichen.\n");
printf("Somit steht an erster Stelle das groeßte Element des Feldes oder Heaps.\n");
printf("Dieses wird aus dem Heapbaum entfernt, indem das erste mit dem \n");
printf("letzten Element getauscht wird. Das groeßte Element am Ende der Folge \n");
printf("wird waehrend des nächsten Durchlaufs nicht mehr beachtet. \n");
printf("So erhaelt man bei jedem herstellen der Heapbedingung den groeßten \n");
printf("Wert des Heap. Die Heapbedingung wird so lange hergestellt,\n");
printf("bis der Baum nur noch aus zwei Elementen besteht. Das Feld liegt \n");
printf("nun sortiert vor.\n");
getch();
} //Funktion9_heapsort_hilfe
//******************************************************************************
void quicksort_hilfe()
{
textcolor(15);
cprintf("\r QQQQQ U U I CCCCC K KK SSSSS OOOOO RRRRR TTTTT \n");
cprintf("\r Q Q U U I C K KK S O O R R T \n");
cprintf("\r Q Q U U I C KK SSSSS O O RRRRR T \n");
cprintf("\r Q Q U U I C K KK S O O R == T \n");
cprintf("\r QQQQQ UUUUU I CCCCC K KK SSSSS OOOOO R == T \n");
printf("\n\n");
printf("Der Sortieralgorithmus Quicksort arbeitet nach dem Prinzip 'Teile \n");
printf("und Herrsche',also dem Sortieren durch Zerlegen in einzelne Teilfolgen. \n");
printf("Quicksort ist dabei ein rekusiver Sortieralgorithmus.\n");
printf("\n");
printf("Bei Quicksort wählt man sich zunaechst ein willkuerliches Vergleichs- \n");
printf("element. Im Idealfall währe dies die Mitte zwischen Minimum- und \n");
printf("Maximumwert, so dass die Folge in zwei gleich grosse Teilfolgen\n");
printf("zerlegt wuerde. Um durch die Ermittlung dieses Wertes keine Sortier- \n");
printf("zeit zu verlieren nimmt man im allgemeinen den Wert in der Mitte der \n");
printf("Folge als Vergleichselement. \n");
printf("\n");
printf("Nun laest man die linke Variable von der Anfangsstelle vorwaerts laufen, \n");
printf("bis man ein Element findet, das groesser oder gleich dem Vergleichselement \n");
printf("ist. Die rechte Variable laeuft vom Ende der Folge rueckwärts, bis ein \n");
printf("Element gefunden wurde, das kleiner oder gleich dem Vergleichselement ist. \n");
printf("Ist die linke Variable nicht groesser als die rechte Variable \n");
printf("werden beide Elemente getauscht. \n");
getch();
clrscr();
printf("Dies wiederholt man, bis die linke Variable groesser als die rechte ist.\n");
printf("Dadurch erhaelt man zwei Folgen,eine kleiner als das Vergleichselement \n");
printf("und eine groesser als das Vergleichselement. ");
getch();
clrscr();
/*init_test_array();
quicksort(test_array, test_array+MAX);
printf("Die Sortierte Reihenfolge lautet: \n\n\n\n");
print_test_array(); */
} //Funktion7_quicksort-hilfe
//******************************************************************************
void beenden()
{
char ch;
//Abfrage ob man wirklich sicher ist, ob man das Programm schließen will
printf("Sind Sie wirklich sicher? <J> <N> ");
scanf("%c",&ch);
//Abfrage auf Zeicheneingabe (j,J, n,N)
if(ch=='J' || ch=='j') {
printf("\n\n\t Auf Widersehen!\n");
textcolor(15);
printf("\t<mit Taste beenden>");
getch();
exit(1);
}
else if(ch=='n' || ch=='N')
printf(""); //sinnlose Anweisung, weil er bei der eingabe von n bzw. N wieder
//in das Hauptmenü zurückspringen soll
//Falls eine Falsche eingabe erfolgt, wird man aufgefordert dies nocheinmal
//zu tun
else {
printf("Falsche eingabe, bitte versuchen Sie es nocheinmal!");
getch();
clrscr();
beenden();
}
} //Funktion5_Beenden
//******************************************************************************
int scanfield(char* zeichenfeld, int groesse)
{
//Diese Funktion durchsucht das Array ob es nur aus Zahlen oder nur aus
//Buchstaben besteht, da sonst wenn das Feld gemischt wäre keine ordnungsgemäße
//sortierung erfolgen kann
//Rückgabewert 1: es sind nur integer Werte im Feld
//Rückgabewert 2: es sind nur Buchstaben im Feld
//Rückgabewert 3: es ist gemischt -> darf nicht sein
int z1=0, z2=0, z=0;
while(z<=groesse) {
if(zeichenfeld[z]>=0 && zeichenfeld[z]<=9) {
z1++;
z++;
} /*
else if((zeichenfeld[z] >= '65' && zeichenfeld[z] <= '90') ||
(zeichenfeld[z] >= '97' && zeichenfeld[z] <= '122')) {
z2++;
z++;
} */
}
if(z1==0)
return 2;
else if(z2==0)
return 1;
else if(z1!=0 && z2!=0)
return 3;
}
//------------------------------------------------------------------------------
//---Insertion Sort-------------------------------------------------------------
void insertionsort(char *zeichenfeld, int zaehler)
{
int index=0;
int index_klein=0;
int wert_klein=0;
int i=0;
// Schleife von links -1 nach rechts
for(index=1; index<=zaehler; index++) {
// aktuelle Position zwischenspeichern
wert_klein=zeichenfeld[index];
//kleineren Wert als wert_klein wird gesucht
//Schleife durchläuft von aktueller Position von rechts nach links
for(index_klein=index; zeichenfeld[index_klein-1] > wert_klein && index_klein > 0;index_klein--)
//Wenn Vorgänger größer als aktuelles Element ist, dann in wert_klein
zeichenfeld[index_klein] = zeichenfeld[index_klein-1];
//gespeichertes Element an neue Position -> Lücke auffüllen
zeichenfeld[index_klein]=wert_klein;
// printf("Die Sortierte Reihenfolge lautet: \n\n\n\n");
//int i=0;
for(i = 0; i < zaehler; i++)
printf("%c", zeichenfeld[i]);
printf("\n");
getch();
}
} // Insertion Sort
//------------------------------------------------------------------------------
void shellsort(char * zeichenfeld,int zaehler) {
int i, j, temp, n,x;
// Anfangswert für die Distanz errechnen
for ( n = 1; n <= zaehler/9; n = 3*n+1);
for ( ; n > 0; n /= 3) {
for (i = n; i <= zaehler; i++) {
temp = zeichenfeld[i];
// Größer als temp und nicht elemente
// sowie >= und nicht >
for(j = i; j >= n && zeichenfeld[j-n] > temp; j -= n) {
zeichenfeld[j] = zeichenfeld[j-n];
}
zeichenfeld[j] = temp;
}
for(x = 0; x < zaehler; x++)
printf("%c ", zeichenfeld[x]);
printf("\n");
getch();
}
} //Shellsort
//------------------------------------------------------------------------------
void quicksort(char *zeichenlfeld, int links, int rechts){
int i=0;
int zaehler=0;
zaehler = rechts;
if(rechts>links){
int i=links-1,j=rechts,tmp;
for(;;){
while(zeichenlfeld[++i]<zeichenlfeld[rechts]);
while(zeichenlfeld[--j]>zeichenlfeld[rechts]);
if(i>=j)
break;
tmp=zeichenlfeld[i];
zeichenlfeld[i]=zeichenlfeld[j];
zeichenlfeld[j]=tmp;
}
tmp=zeichenlfeld[i];
zeichenlfeld[i]=zeichenlfeld[rechts];
zeichenlfeld[rechts]=tmp;
quicksort(zeichenlfeld,links,i-1);
quicksort(zeichenlfeld,i+1,rechts);
}
for(int i=0;i<zaehler;i++)
printf("%c\n ",zeichenlfeld[i]);
getch();
}
//------------------------------------------------------------------------------
void buildheap(char* zeichenfolge, int zaehler)
{
int v,z;
v=zaehler/2-1;
while (v>=0)
{
downheap(zeichenfolge,v,zaehler);
v--;
}
printf("\n");
for(z=0;z<=zaehler;z++)
{
printf("wert %c\n", zeichenfolge[z]);
}
}
//------------------------------------------------------------------------------
void downheap(char* zeichenfolge, int v, int zaehler)
{
int w;
w=2*v+1;
while (w<zaehler)
{
if(w+1<zaehler)
{
if(zeichenfolge[w+1]>zeichenfolge[w])
w++;
}
if(zeichenfolge[v]<zeichenfolge[w])
break;
exchange(zeichenfolge,v,w);
v=w;
w=2*v+1;
}
}
//------------------------------------------------------------------------------
void heapsort(char* zeichenfolge, int zaehler)
{
int v;
int z=0;
buildheap(zeichenfolge,zaehler);
v=zaehler-1;
while(v>0)
{
exchange(zeichenfolge,0,v);
downheap(zeichenfolge,0,v);
v--;
}
/* printf("\n");
for(z=0; z<=zaehler; z++)
printf("wert %d \n", zeichenfolge[z]);
heapsort(zeichenfolge,zaehler);
*/
printf("\n");
for(z=0;z<=zaehler;z++)
printf("wert %c\n", zeichenfolge[z]);
getch();
}
//------------------------------------------------------------------------------
void exchange(char* zeichenfolge, int i, int j)
{
int h;
h=zeichenfolge[j];
zeichenfolge[i]=zeichenfolge[j];
zeichenfolge[j]=h;
}
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
Alles anzeigen