canlot hat geschrieben:DER CODE IST VON MIR. Ich hab denn selbst entworfen und keine anderen Sortalgorithmen angeguckt, weil ich selber was lernen will. Das Problem ist nur, dass das Programm mir nicht mehr gehorchen will.
Eigentlich wollte ich denn Algorithmus so schreiben: arr[a] soll sich mit arr[ b] vergleichen(bei meinen vorigen Code hab ich b=0 gesetzt), arr[a] soll immer um eins steigen und wenn es ein Wert gefunden hat, dann soll arr[ b] denn übernehmen und weiter vergleichen. Dadurch soll der letzte also der größte Wert dann in newar gespeichert werden. Der Wert temp speichert denn letzen größten Wert und stellt eine Bedingung dar damit man denn letzen größten Wert auslässt:
Also, nach dem ich gestern Abend ja angekündigt hab, dass ich das auch zurecht biegen kann, muss ich dir leider sagen, dass das SO nicht funktioniert.
Grund dafür ist folgender: (oben Eingabe, unten Ausgabe)
5 | 4 | 4 | 3
x | x | x | x
Du suchst zu erst den größten Wert, sprich die 5:
5 | 4 | 4 | 3
5 | x | x | x
Nun suchst du einen Wert, der kleiner als 5 ist und gleichzeitig der größte unter diesen in Frage kommenden Werten ist.
Dabei wirst du zwangsläufig auf die 4 kommen.
5 | 4 | 4 | 3
5 | 4 | x | x
So, und jetzt haben wir das Dilemma.
Mit deiner Methode (dem ECHT kleiner .. also < temp) wirst du nun einen Wert suchen, der kleiner als 4 ist.
Damit
verlierst du die zweite 4 aus deiner Eingabe, du findest die 3
5 | 4 | 4 | 3
5 | 4 | 3 | x
Der letzte Wert würde bei deinem ursprünglichen Code mit Speichermüll gefüllt werden, arr[big] ja nicht definiert ist. (b kann sich nun nicht mehr ändern)
Wenn du anstatt dem ECHT kleiner ein KLEINER GLEICH benutzt hast du folgendes Problem:
Du findest den nächsten Wert, der KLEINER GLEICH 4 ist und auch am größten unter diesen: Das ist die 4.
5 | 4 | 4 | 3
5 | 4 | 4 | x
Jetzt suchst du wieder nach einem Wert KLEINE GLEICH 4 ... und voila, du findest wieder eine 4!
5 | 4 | 4 | 3
5 | 4 | 4 | 4
Und schon haben wir die 3 (bzw alles, was dahinter kommen würde) verloren!
Dieses Problem ist SO, mit deinem Algorithmus nicht lösbar!
Du müsstest dir höchstens merken, welche Wert aus der Eingabe du schon benutzt hast und dann nur unter denjenigen suchen, die noch nicht in der Ausgabe platziert wurden.
Hier ist mal, was ich daraus noch zusammengezaubert hab:
Code: Alles auswählen
#include <stdio.h>
#include <limits.h>
int main(int argc, char** argv)
{
/*****************************************************************************
* Eingabe - Feld, welches sortiert werden soll
*/
const int SIZE = 10;
int eingabe[SIZE];
eingabe[0] = 345;
eingabe[1] = 435;
eingabe[2] = 16;
eingabe[3] = 18;
eingabe[4] = 17;
eingabe[5] = 3070;
eingabe[6] = 165;
eingabe[7] = 453;
eingabe[8] = 166;
eingabe[9] = 300;
/*****************************************************************************
* Sortieren
*/
// Platz fuer das fertig sortierte Feld, wir sortieren NICHT in situ!
int ausgabe[SIZE];
// Wo in ausgabe muessen wir als naechstes etwas ablegen?
int platzier_iterator = 0;
// Wir speichern uns, welchen Wert wir zuletzt in ausgabe geschrieben haben
// und wo (Index) wir diesen Wert in eingabe (!!) gefunden hatten!
// Fuer den ersten Durchgang brauchen wir einen Wert, der groesser ist, als
// alles, was in eingabe steht. Also nehmen wir INT_MAX!
int zuletzt_platziert_index = -1;
int zuletzt_platziert_wert = INT_MAX;
// Wir platzieren nach einander die Werte in ausgabe
while (platzier_iterator < SIZE)
{
/* Zu erst suchen wir den Wert, welcher (ohne die schon platzierten Werte)
* in eingabe am groessten ist!
*/
// Wo suchen wir als naechstes in eingabe?
int such_iterator = 0;
// Wir speichern uns, welchen Wert wir schon gefunden haben, der unsere
// Anforderungen erfuellen koennte. Wir speichern uns auch, wo wir diesen
// Wert im eingabe gefunden haben.
int gesucht_index = 0;
int gesucht_wert = INT_MIN;
// Die eigentliche Suche
while (such_iterator < SIZE)
{
// Wir haben einen Wert, der kleiner/gleich als der zuletzt platzierte
// Wert ist. Diese Ueberpruefung ist notwendig, um schon platzierte Werte
// aus der Suche auszuschliessen!
if (eingabe[such_iterator] <= zuletzt_platziert_wert)
{
// Nicht den zuletzt platzierten Wert nehmen, das ist ein Ansatz, der
// manchmal Abhilfe schafft, aber eben nicht immer!!!
if (such_iterator != zuletzt_platziert_index)
{
// Wir haben einen Wert gefunden, der groesser als unser bisheriger
// Wert ist. Den merken wir uns!
if (eingabe[such_iterator] > gesucht_wert)
{
// Wir merken uns den Wert und auch den Ort, an dem wir ihn gefunden
// haben!
gesucht_index = such_iterator;
gesucht_wert = eingabe[such_iterator];
}
}
}
// Weitersuchen!
such_iterator++;
}
/* Wir haben den gesuchten Wert gefunden und platzieren ihn nun an der
* richtigen Stelle!
*/
// Platzieren!
ausgabe[platzier_iterator] = eingabe[gesucht_index];
// Und wir muessen auch im naechsten Durchgang noch wissen, welchen Wert wir
// hier gerade platziert haben! Und auch, von wo!
zuletzt_platziert_wert = eingabe[gesucht_index];
zuletzt_platziert_index = gesucht_index;
// Weiter, um den naechsten Wert zu platzieren!
platzier_iterator++;
}
/*****************************************************************************
* Ausgabe des fertig sortierten Feldes
*/
printf("(");
int print_iterator = 0;
while (print_iterator < SIZE)
{
printf(" %d ", ausgabe[print_iterator]);
print_iterator++;
}
printf(")\n");
return 0;
}
Problem ist wie gesagt, sobald gleiche Werte vorkommen zerlegt es das Programm.
Das liegt daran, dass der Algorithmus SO nicht funktioniert.
Hoffe du verstehst, wo das Problem liegt
