Quicksort

[julchatt]

Hallo Leute

ich bin ein Neuling in c++ und versuche ein Quicksort programm zu schreiben. Es fehlen mir jedoch Kenntnisse in C++, deshalb bin ich für jede Hilfe sehr dankbar.
Ich habe schon gegoogelt und nachgeforscht im Internet, aber es sind so viele Möglichkeiten wie man aus einer Text-Datei sortiert die Zahlen ausgibt und diese dann in eine andere Datei schreibt....habe hier Schwierigkeiten...help))

Die Aufgabe lautet so:

a->> Implementieren Sie den Quicksort aus der Vorlesung in C++. Verwenden Sie dabei die in der Vorlesung vorgestellte Lomuto-Partition. Es sollen Felder mit ganzen Zahlen sortiert werden, die aus einer Textdatei einzulesen sind. Die Eingabedaten sollen zeilenweise vorliegen. Die Ausgabe des sortierten Feldes soll ebenfalls in Textdatei geschrieben werden

b->> Generieren Sie Testdaten für das obige Programm für Feldlängen n1=100000,
n2=1000000 und n3=5000000 mit zufälligen Werten aus dem Intervall {0,...,ni}.

[wxSkip]

Wie sehen die Dateien aus? Wo liegt dein Problem? Beim Einlesen oder beim Sortieren?

[julchatt]

Hallo,

ich habe schon so viel im internet nachgeschaut, so viele Möglichkeiten gibts da...also es fehlt mir einfach irgendwie Ansatz wie ich die main() schreibe, dass ich aus einer .txt Datei Zahlen mit Hilfe des Quicksort-Algorithmus auf die console ausgebe und diese sortierte Folge dann in eine .txt Datei gespeichert wird und gleichzeitig muss ich die Testdaten für unterschiedliche Feldlänge generieren.

Ich habe bis jetzt nur die Quicksort Funktion, die ich gerade versuche in main aufzurufen, komme mir total blöd vor, dass es irgendwie nicht klappt, meine Kenntnisse in c++ sind wie gesagt noch ziemlich mangelhaft...ich habe viele puzzle Teile und weiß nicht wie ich diese zusammenfüge, dass das Programm vernünftig läuft...

Bin dankbar für jede Hilfe!

[cooky451]

bool readLine(const std::string &filename, std::vector<int> &buf);
void writeLine(const std::string &filename, const std::vector<int> &numbers);
void quicksort(std::vector<int> &numbers);

int main()
{
  std::vector<int> numbers;
  while (readLine("infile.txt", numbers))
  {
    quicksort(numbers);
    writeLine("outfile.txt", numbers);
  }
}

Jetzt musste nur noch die Funktionen oben mit Leben füllen.
(Was du dir angucken solltest: std::ifstream, std::ofstream, std::swap())

[SeppJ]

Programmieren != Bruchstücke aus dem Internet zusammensuchen

Programmier es selbst. Das ist der Sinn der Aufgabe. Wenn eine Aufgabe zuerst überwältigend erscheint, teil sie in Teilprobleme auf. Hier bieten sich als Teilprobleme Einlesen, Sortieren und ausgeben an. Diese sind unabhängig voneinander, bis auf das gemeinsame Datenfeld. Hierdurch ist auch schon klar, wie die main aussehen muss: Dur brauchst dort das gemeinsame Datenfeld. Dieses wird an die Einlesefunktion gegeben und dort gefüllt. Wenn's schick sein soll, dann gibst du der Einlesefunktion auch noch einen Dateinamen oder einen Stream mit auf dem Weg, um die Einlesefunktion so allgemein wie möglich zu halten. Dann wird das Datenfeld an die Sortierfunktion übergeben, die diese sortiert. Und dann an die Ausgabefunktion.

Jede Einlesen und Ausgeben sollten auf deinem Kenntnisstand recht einfach zu schreiben sein (ansonsten solltest du dir Sorgen machen), das interessante ist natürlich die Sortierfunktion. Hier hast du ja genaue Angaben aus der Vorlesung vorgegeben die hoffentlich reichen, das Problem zu lösen.

edit: Kurz: So wie cooky451 vorgegeben hat. Wobei ich nicht verstehe, was er da mit der Schleife will. Sinnvollerweise sollten doch wohl alle Daten gelesen werden, bevor man sortiert.

[julchatt]

Vielen Dank!!!!! Ich probiere es jetzt aus...

[cooky451]

SeppJ schrieb:

edit: Kurz: So wie cooky451 vorgegeben hat. Wobei ich nicht verstehe, was er da mit der Schleife will. Sinnvollerweise sollten doch wohl alle Daten gelesen werden, bevor man sortiert.

Ich hatte verstanden, dass er jede Zeile einzeln sortieren möchte. Das schien mir so am einfachsten. (Vielleicht nicht am performantesten, aber das dürfte hier wohl egal sein.)

[julchatt]

ich habe die meine .txt-Datei so auf die console ausgegeben...kann ich denn in diesem code-Stück auch die quicksort aufrufen, dass quasi beim Öffnen der Datei quicksort aufgerufen wird und sortiert auf der console erscheint?

//-----------------------------------------------------
FILE * pFile;
char mystring [50];

pFile = fopen ("text.txt" , "r");
if (pFile == NULL) perror ("Error opening file");
else {
if ( fgets (mystring , 100 , pFile) != NULL ) //fgets(zeile,256,file);
puts (mystring);
fclose (pFile);
}

//-----------------------------------------------------

mein quicksort sieht folgend aus:

void quicksort(int a[], int l, int r);

void quicksort(int a[], int l, int r){
if(l<r){
int s=partition(a, l, r);
quicksort(a, l, s-1); //sortiere linke Teilliste kleiner/gleich-Elemente
quicksort(a, s+1, r);

int partition(int a[], int l, int r){
int li, re, pivot, temp;
li = l; re = r;
// int s=mitte(a, links, rechts); //tri median
int s=rand()%(re-li+1)+li; //zufaellig
pivot = a[s];

do
{
while (a[li] <= pivot && li<re)
li++;
while (a[re] >= pivot && re>li)
re--;

if (li < re){
tausche(a, li, re);
li++;
re--;
}
}while (li < re);

if(li<=s && a[li]>=pivot || a[li]<pivot && li>s)
tausche(a, li, s);
else if(li<s && a[li]<pivot)
tausche(a, ++li, s);
else
tausche(a, --li, s);

return li;
}
/**********************************************
partition
**********************************************/
/int partition(int a[], int l, int r) {
pivot = a[r];
i = l-1;
for j=l to r-1 {
if( a[j] <= Pivot ) {
i = i+1;
vertausche( a[i], a[j] );
}
vertausche( a[i+1], a[r] )
return i+1
}
}/

/**********************************************
tausche
**********************************************/
void tausche(int a[],int l, int r){
int help = a[l];
a[l] = a[r];
a[r] = help;

}

[cooky451]

Willst du C oder willst du C++ schreiben? Denn das da oben ist reines C, aber du fragst nach C++.

[julchatt]

shit...klar...ja ich brauche es in C++ ...