ich bin ganz neu hier, ich möchte nach längerer Abstinenz wieder meine C++ Kenntnisse ausbauen. Auf meinem Rechner programmiere ich mit Code::Blocks 10.05 mit Gnu GCC und Visual Studio 2008.
Auf einer Seite habe ich hier den Sortieralgorithmus Bubblesort entdeckt und bisschen rumexperimentiert. Dabei gibt es bei den Ausgaben nach dem Sortieren an einer Stelle einen Unterschied den ich mir einfach nicht erklären kann. Verursacht wird er durch die Funktion BubbleSort_normal(matrix,size); Aber hier erst einmal der Code.
Code: Alles auswählen
#include <iostream>
#include <time.h>
using namespace std;
// Prototypen
void BubbleSort_normal (int *values, int n);
void BubbleSort_verbessert(int *values, int n);
void BubbleSort_sehrgut(int *values, int n);
void array_ausgabe(int *values, int n);
void BubbleSort_normal(int *values, int n)
{
int tmp; // Hilfsvariable zum Vertauschen von Werten
// durch das ganze Feld gehen
for (int i = 0; i < n; i++)
{
// am Ende beginnen das kleinste Element zu suchen
for (int j = n - 1; j >= i; j--)
{
// prüfen ob das Element kleiner als der Vorgänger ist
if (values[j] < values[j - 1])
{
// Werte vertauschen
tmp = values[j];
values[j] = values[j - 1];
values[j - 1] = tmp;
}
}
}
}
void BubbleSort_verbessert(int *values, int n)
{
int limit; // limit: gibt den Index des ersten unsortierten Elements an
int lastmove; // lastmove: Index der letzten Vertauschung
// beim ersten Durchlauf ist das Limit 1,
// d.h. alle Elemente werden geprüft
limit = 1;
do
{
// es wurde noch nichts vertauscht
lastmove = 0;
// am Ende beginnend durch den unsortierten
// Teil des Feldes gehen
for (int i = n - 1; i >= limit; i--)
{
// Wert ist kleiner als der vorhergehende
if (values[i] < values[i - 1])
{
// vertauschen
int help = values[i];
values[i] = values[i - 1];
values[i - 1] = help;
// Position der Änderung merken
lastmove = i;
}
}
// alle Elemente vor dem letzten Tausch sind bereits sortiert
// deshalb können wir beim nächsten mal dort stoppen
limit = lastmove + 1;
// solange sortieren, bis nichts mehr geändert wird
} while (lastmove != 0);
}
void BubbleSort_sehrgut(int *values, int n)
{
int left, // left: linker Ausgangspunkt, Startpunkt bei der Suche nach dem größten Element
// Endpunkt bei der Suche nach dem kleinsten Element
right, // right: rechter Ausgangspunkt, Startpunkt bei der Suche nach dem kleinsten Element
// Endpunkt bei der Suche nach dem größten Element
lastmove; // lastmove: speichert den Index der letzten Vertauschung
// Anfang des Arrays
left = 0;
// Ende des Arrays
right = n - 1;
// die letzte Vertauschung auf die Anzahl setzen; wird nichts vertauscht wird sowohl left als auch right
// lastmove und der Algorithmus bricht ab
lastmove = n;
int *vec = new int[n];
int help;
do
{
// von rechts nach links das kleinste Element suchen
// und ganz nach links verschieben
for (int i = right; i > left; i--)
{
// prüfen ob das Element kleiner als das vorhergehende ist
if (vec[i] < vec[i - 1])
{
// vertauschen
help = vec[i];
vec[i] = vec[i - 1];
vec[i - 1] = help;
// Index der Vertauschung merken
lastmove = i;
}
}
// bis zur Vertauschung sind alle Elemente sortiert
left = lastmove;
// von links nach rechts das größte Element suchen
// und ganz nach links verschieben
for (int i = left; i < right; i++)
{
// prüfen ob das Element größer als das nachfolgende ist
if (vec[i] > vec[i + 1])
{
// vertauschen
help = vec[i];
vec[i] = vec[i + 1];
vec[i + 1] = help;
// Index der Vertauschung merken
lastmove = i;
}
}
// nach der Vertauschung sind alle Elemente sortiert
right = lastmove;
// sortieren bis sich die sortierten Bereiche überschneiden oder nichts verändert wurde
} while (left < right);
// !!Heap Speicher wieder freigeben!!
delete [] vec;
}
void array_ausgabe(int *values, int n)
{
for (int i = 0; i < n; ++i)
{
cout << "i: " << i << " "<< values[i] << " " << endl;
}
cout << endl << endl;
}
int main()
{
int matrix[] = { 23, 11, 28, 67, 3, 9, 71, 32, 3999 , 15 , 54, 982, 10333 };
// die Anzahl der Elemente berechnen
int size = sizeof(matrix) / sizeof(int);
cout << endl << endl << size << " Elemente in matrix" << endl << endl;
cout << "matrix vor der Sortierung: " << endl;
array_ausgabe(matrix, size);
BubbleSort_normal(matrix,size);
//BubbleSort_verbessert(matrix, size);
// BubbleSort_sehrgut(matrix, size);
cout << "matrix nach der Sortierung: " << endl;
array_ausgabe(matrix, size);
return 0;
}
Mit Code::Blocks gnu Compiler
matrix vor der Sortierung
i: 0 23
i: 1 11
i: 2 28
i: 3 67
i: 4 3
i: 5 9
i: 6 71
i: 7 32
i: 8 3999
i: 9 15
i: 10 54
i: 11 982
i: 12 10333
matrix nach der Sortierung
i: 0 9
i: 1 11
i: 2 15
i: 3 23
i: 4 28
i: 5 32
i: 6 54
i: 7 67
i: 8 71
i: 9 982
i: 10 3999
i: 11 10333
i: 12 4634440
Mit Visual Studio
matrix vor der Sortierung:
i: 0 23
i: 1 11
i: 2 28
i: 3 67
i: 4 3
i: 5 9
i: 6 71
i: 7 32
i: 8 3999
i: 9 15
i: 10 54
i: 11 982
i: 12 10333
matrix nach der Sortierung:
i: 0 3
i: 1 9
i: 2 11
i: 3 15
i: 4 23
i: 5 28
i: 6 32
i: 7 54
i: 8 67
i: 9 71
i: 10 982
i: 11 3999
i: 12 10333
Also der Gnu Compiler unterschlägt jeweils das kleinste Element und fügt statt dessen als letztes int Element einen undefinierten Wert ein.
Hat jemand eine Idee was hier für ein Fehler vorliegen könnte?
Viele Grüße aus Cottbus
