Sortieralgoritmus schlägt fehl

Techniker

Hallo, wir haben in der Schule ein Programm erstellt, bei dem man ein Array mit Zahlen hatt und diese Sortieren muss. Nun, eigentlich sollte es kein Problem sein.
Erkennt ihr dort irgendeinen Fehler? Weder ich, noch mein Lehrer (der etwa ne 1/4h davor saß) noch sonst irgendjemand aus unserer Klasse konnte ihn finden.
Es wird alles ausgeführt und sortiert. Nur es hört zu früh auf...

(bei 45 kommt danach die 20...)

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

int main(int argc, char* argv[])
{
	int leange = 20, zwischenspeicher;
	int feld[]={23,12,45,26,76,88,123,2,34,56,0,98,44,64,23,78,8,82,50,20};

	cout<<sizeof(feld)/4;

	for(int i=0; i<leange;i++)
	{
		for(int j=i+1; j<leange;j++)
		{
			if(feld[j-1]>feld[j])
			{
				zwischenspeicher = feld[j];
				feld[j] = feld[j-1];
				feld[j-1] = zwischenspeicher;
			}
		}

	}
	for(int a=0;a<20;a++)
		cout<<feld[a]<<" ";

	cout<<endl;
	system("pause");
	return 0;
}

wäre echt froh über Hilfe...

Könnte es sein, dass statt ... j=i+1 ... j=0 stehen muss ?

C++ Forumbot

Dieser Thread wurde von Moderator/in estartu aus dem Forum MFC (Visual C++) in das Forum C++ verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Oder besser:

for(int i=0; i<leange;i++)
{
for(int j=1; j<leange;j++)
{
if(feld[j-1]>feld[j])
{
zwischenspeicher = feld[j];
feld[j] = feld[j-1];
feld[j-1] = zwischenspeicher;
}
}

}

zero_gravity

Erstmal ist mir aufgefallen, dass du länge mit 25 initialisierst, das Feld aber nur 20 Elemente hat...

Außerdem sind die Indexgrenzen der inneren Schleife falsch. Da du von links nach rechts durch die Liste iterierst, können die ausgetauschten Elemente ja nur zum Ende der Liste wandern. Es müsste also heißen:

for(int i=0; i<leange;i++)
    {
        for(int j=1; j<leange-i;j++)
        {
            if(feld[j-1]>feld[j])
            {
                zwischenspeicher = feld[j];
                feld[j] = feld[j-1];
                feld[j-1] = zwischenspeicher;
            }
        }

    }

Das heißt, du fängst jedes mal wieder am Anfang der Liste an, aber nach jedem Durchlauf kannst du ein Element früher aufhören, da die Elemente am Ende die richtige Reihenfolge haben.

Und soetwas:

int leange = 25, zwischenspeicher;

ist zwar syntaktisch korrektes C++, aber grauenhafter Stil.

Techniker

Vielen dank.
Ich hab es gelöst

aaaalso:

das mit den 25 war mein versehen. Ich dachte ich hätte es schon rückgängig gemacht. Aber naja egal.

Könnte es sein, dass statt ... j=i+1 ... j=0 stehen muss ?

Nein weder noch. Ihr hattet recht mit eurem j=1 UND laenge - i
3)

int leange = 20, zwischenspeicher;

Mhm, das hat uns unser Lehrer so beigebracht. Wärst du der meinung, dass man:
int leange = 20;
int zwischenspeicher; schreibt oder
int leange = 20, int zwischenspeicher; ?
Weil von der Ordnung her gefällt mir der Code von unserem Lehrer da am besten

zero_gravity

Techniker schrieb:

int leange = 20, zwischenspeicher;

Mhm, das hat uns unser Lehrer so beigebracht. Wärst du der meinung, dass man:
int leange = 20;
int zwischenspeicher; schreibt oder
int leange = 20, int zwischenspeicher; ?
Weil von der Ordnung her gefällt mir der Code von unserem Lehrer da am besten

int laenge = 20;
int zwischenspeicher;

ist zwar am meisten zu tippen, aber es erhöht meiner Meinung nach sehr die Übersichtlichkeit. Wenn man beides in eine Zeile schreibt, impliziert das, das die beiden Variablen semantisch eng miteinander verbunden sind, obwohl sie in Wirklichkeit überhaupt nichts miteinander zu tun haben.

Natürlich ist das alles Geschmackssache, und wenn du es so am übersichtlichsten findest, will ich dich nicht davon abbringen.

blub* 0

Machs so wies dir besser gefällt.
Ich schreib auch gerne jede Initialisierung,
ob mit oder ohne Zuweisung in eine neue Zeile.
Gibt aber auch genug Leute die das so machen wie
du beschreibst.

Nein weder noch. Ihr hattet recht mit eurem j=1 UND laenge - i

Wenn ich dich richtig versteh is das falsch.

for(int j=1; j<laenge;j++) // so

for(int j=0; j<laenge-1;j++) // oder so
// dann muss halt der code danach so aussehen:

    for(int i=0; i<leange;i++)
    {
        for(int j=0; j<laenge-1;j++)
        {
            if(feld[j]>feld[j+1])
            {
                zwischenspeicher = feld[j+1];
                feld[j+1] = feld[j];
                feld[j] = zwischenspeicher;
            }
        }
    }

Unser Lehrer wäre zum Beispiel ein Verfechter der zweiten Variante.

Gruß,

Max

#edit: ah, sry jetz hab ich erst verstanden warum -i
Klar, kann man machen, ist eine ganz nette Optimierung.
Funktioniert auch mit beiden Varianten die ich oben
gepostet hab.

Dein Algorithmus nennt sich "Bubblesort". "Die Blasen steigen noch oben".
Er hat einen quadratischen Aufwand. Es gibt auch noch schnellere Algorithmen wie z.B. Quicksort. Du kannst Dich mal in einem Algorithmen-Buch informieren.

Fellhuhn

#include <algorithm>
//...

std::sort(feld[0], feld[laenge]);

*D*Evil

namespace algorithm
{
    template<typename iterator_type>
    void bubble_sort(iterator_type first, iterator_type last)
    {
        iterator_type j;
        for (iterator_type i(first); i != last; ++i)
            for (j = first; j < i; ++j)
                if (*i < *j) std::iter_swap(i, j);
    }
}; // algorithm

int main()
{
    int array[10] = { 0, 1, 2, 3, 5, 6, 7, 8, 9 };
    algorithm::bubble_sort(array, array + 10);
}

...