Sortieralgorithmus

Hallo Com,
ich lerne zurzeit C++ und bin beim Thema Sortieralgorithmus angekommen.
Ich komme aber an einer Stelle nicht weiter:
Der Code funktioniert soweit, dass die zwei Zahlen nebeneinander gecheckt, und gegebenenfalls sortiert werden. Das aber nur einmal.
Sollen z.B. die Zahlen 4,5,54,567,4 und 2304 sortiert werden, klappt alles wunderbar, bis zu dem Punkt, an dem er bei der zweiten 4 angekommen ist, das sieht dann so aus:

4, 5, 54, 4, 567, 2304

Ich weiß nicht, wie ich es hinkriegen kann, dass er die ganze Kette so oft checkt und sortiert, bis alles stimmt.

Ich hoffe jemand kann mir helfen

grüße

Hier noch mein Code:

#include <iostream>
#include <stdlib.h>
#include "stdafx.h"

using namespace std;

void sort(long[],int);
void xchg(long &, long &);
void outputNumberSequence(int, long []);

int main(int argc, char *argv[])
{
    int retVal = 0;
    if(argc > 1)
    {
        long *numbers = (long *) malloc((argc - 1) * sizeof(char));

        for(int cnt = 1; cnt < argc; ++cnt)
            numbers[cnt - 1] = strtol(argv[cnt], 0, 10);

        cout << "unsorted: ";
        outputNumberSequence(argc, numbers);

        sort(numbers,argc);

        cout << "after sort: ";
        outputNumberSequence(argc, numbers);

        for(int cnt = 0; cnt < argc - 2; ++cnt)
            if(numbers[cnt] > numbers[cnt+1])
            {
                cout << "not sorted at position " << cnt + 1 << endl;
                retVal = -1;
            }
		if(retVal  = 0)
			cout << "sorted" << endl;
    }
	int a;
	cin >> a;
    return retVal;
}

void sort(long numbers[], int argc)
{

    for(int cnt=0; cnt < argc-1; ++cnt)
    {
        if (numbers[cnt]>numbers[cnt+1])
            xchg(numbers[cnt], numbers[cnt+1]);
        while(numbers[cnt]<numbers[cnt-1])
            xchg(numbers[cnt], numbers[cnt-1]);

    }
}

void xchg(long &a, long &b)
{
    long tmp = a;
    a = b;
    b = tmp;
}

void outputNumberSequence(int argc, long numbers[])
{
    for(int cnt = 0; cnt < argc - 1; ++cnt)
        cout << numbers[cnt] << " ";
    cout << endl;
}

PS: Ja, ich weiß, dass die while-Loop falsch ist, dass ist nähmlich genau die Stelle, wo ich nicht weiter komme.

Da hat doch dein Algo schon einmal was richtig gemacht mit dem Tausch. Ich glaube du musst ihn bloß noch sooft wieder durchlaufen lassen, bis es keinen Tausch mehr gibt, dann ist deine Liste sortiert.

Swordfish

LPGermanification schrieb:

void sort(long numbers[], int argc)
{
	bool sorted = false;
	
	while( !sorted ) {

		sorted = true;
		for(int cnt=0; cnt < argc-1; ++cnt)
		{
			if (numbers[cnt]>numbers[cnt+1]) {
				xchg(numbers[cnt], numbers[cnt+1]);
				sorted = false;
			}

		/*	while(numbers[cnt]<numbers[cnt-1])
				xchg(numbers[cnt], numbers[cnt-1]);

		wtf? */

		}
	}
}

void outputNumberSequence(int argc, long numbers[]) // fuer speichergroessen nimmst size_t
{
    for( int cnt = 0;
         cnt < argc - 1; // unschoen, warum erwartet outputNumberSequence nicht die laenge, sondern laenge + 1?
         ++cnt )
        cout << numbers[cnt] << " ";
    cout << endl;
}

// edit: steht auch auf http://de.wikipedia.org/wiki/Bubblesort#Algorithmus

Dankeschön

Noch mein Senf.

Meist wird in Schleifen ein Index [0...n) gezählt, also 0 bis ausschließlich n.

Du musst in Deinem Beispiel ständig irgendwelche offsets hinzuzählen oder abziehen.
Wie wäre es irgendwo am Anfang ein

--argc; ++argv;

einzubauen.
Dann hast Du genau argc zusätzliche Argumente an den Stellen argv[0]...argv[argc-1]. Du wirst sehen, die meisten der Offsets fallen dann weg.

Ausserdem wäre es sicherlich besser, wenn Deine beiden Funktionen, die auf dem array arbeiten die Parameter auch in der gleichen Reihenfolge annähmen.

Und

if(retVal  = 0)
  cout << "sorted" << endl;

ist natürlich ein Fehler...
Davor sollte Dich Dein Compiler warnen! Also Compiler-Warnungen einschalten.

Sicherlich ist das ganze eher ein C Programm, und es gibt noch einiges zu verbessern...aber Du fängst ja gerade damit an.

Hier das ganze nochmal ein wenig aufgehübscht. (Geht sicherlich noch besser und vorallem effektiver).
(mit C++11)

#include <vector>
#include <iterator>
#include <sstream>
#include <algorithm>
#include <iostream>

using namespace std;

void bubblesort(vector<int>& vec)
{
    for (auto it(begin(vec)); it != end(vec)-1; ++it)
        for(auto jt(it+1); jt != end(vec); ++jt)
            if (*jt < *it)
                swap(*jt, *it);
}

int main(int argc, char* argv[])
{
    cout << "vor dem sortieren:\n";
    for (auto i(1); i<argc; ++i)
        cout << argv[i] << "\n";
    vector<int> to_be_sorted;

    back_insert_iterator<vector<int> > it(to_be_sorted);

    transform(&argv[1], &argv[argc], it, [](char const* str)
                                                 {stringstream ss(str);
                                                 int t;
                                                 ss >> t;
                                                 return t;});

    bubblesort(to_be_sorted);
    cout << "nach dem sortieren:\n";
    for (auto& it : to_be_sorted)
    {
        cout << it << "\n";
    }
}

Swordfish

Der Tobi schrieb:

transform(&argv[1], &argv[argc], it, [](char const* str)
                                                 {stringstream ss(str);
                                                 int t;
                                                 ss >> t;
                                                 return t;});

Braucht das Lambda nicht einen return type?

Sone

Swordfish schrieb:

Der Tobi schrieb:

transform(&argv[1], &argv[argc], it, [](char const* str)
                                                 {stringstream ss(str);
                                                 int t;
                                                 ss >> t;
                                                 return t;});

Braucht das Lambda nicht einen return type?

Nein, du hugo.

Swordfish

Warum nicht?

Sone

Swordfish schrieb:

Warum nicht?

Weil er deduziert werden kann.

Swordfish

ISO/IEC 14882:2011(E) schrieb:

§5.1.2.4 If a lambda-expression does not include a trailing-return-type, it is as if the trailing-return-type denotes the following type:
— if the compound-statement is of the form
{ attribute-specifier-seq_opt return expression ; }
the type of the returned expression after lvalue-to-rvalue conversion (4.1), array-to-pointer conversion (4.2), and function-to-pointer conversion (4.3);
— otherwise, void.

...

Sone

Na gut, und weil es nur eine return Anweisung gibt

Sone schrieb:

Na gut, und weil es nur eine return Anweisung gibt

Sei einfach still wenn du keine Ahnung hast.

Der ganze Körper des Lambda-Ausdrucks darf nur aus einem einzelnen return-Statement bestehen.

Da weder mein Compiler gemeckert, noch das Ergebnis falsch war, nehme ich mal an, Sone hat ausnahmsweise mal recht. Wenn der Compiler den Rückgabetyp schon zur Compilezeit bestimmen kann, kann ich auf den Trailing Return Type verzichten.

bzw. sagt mein C++11 Buch:

->... ist optional und dient der Angabe des Rückgabetyps.Wird dieser weggelassen,
überlässt man dem Compiler, diesen automatisch zu ermitteln. In den
meisten Fällen schafft der Compiler das. Innerhalb von Templates, in wenigen
Sonderfällen oder zur Dokumentation können Sie den Typ hier angeben.

Swordfish

Der Tobi schrieb:

Wenn der Compiler den Rückgabetyp schon zur Compilezeit bestimmen kann, kann ich auf den Trailing Return Type verzichten.

Wenn /dein/ Compiler das kann, dann ist das dein Privatvergnügen. Der Standard ist in diesem Punkt glasklar, da gibt's nichts zu diskutieren.

ps@h4x0r: Danke fürs auf'n Leim geh'n, is eh witziger als dich hugo 'z schimpf'n