[ need help ] zahlensortierungsporgram!

[saNz]

Moin moin !

Hab da ganz schieke Hausaufgaben @ Turbopascal auf, und zwar soll ein Programm, von dem Benutzer Zahlen einlesen die er eingibt, und diese dann von klein aufsteigend sortieren und ausgeben.

z.B. User gibt 57123 ein
Prog gibt aus 12357

Hab schonmal angefangen, aber da ich kA wie ich das machen soll hab hab ich das an der Stelle mal ausgelassen.

program zahlensortierung;
uses crt;

var zahlen:integer;

begin
clrscr;
writeln (' dann gib mal dein Zahlensortiment ein! ');
readln (zahlen);
...
end.

ja echt kein Plan wie das funktionieren soll, wäre cool wenn jemand code vervollständigen könnte,

greeTz
saNz

[Cyrus1985]

Hi,

ich denke für dein Problem ist am einfachsten der BubbleSort-Algorithmus angemessen!

Schreib die unsortierten Zahlen in ein Array, und dann lass Schleifen durchlaufen wie es hier genau beschrieben wird:

http://de.wikipedia.org/wiki/Bubblesort


Dort findest du auch komplexere Sortieralgorithmen, die effizienter sind. Ist aber in deinem Fall glaube ich nicht notwendig.

[saNz]

Hi,

ich denke für dein Problem ist am einfachsten der BubbleSort-Algorithmus angemessen!

Schreib die unsortierten Zahlen in ein Array, und dann lass Schleifen durchlaufen wie es hier genau beschrieben wird:

http://de.wikipedia.org/wiki/Bubblesort


Dort findest du auch komplexere Sortieralgorithmen, die effizienter sind. Ist aber in deinem Fall glaube ich nicht notwendig.

könnte das mal jemand fertig schreiben!? ;/ ich blick das nix, bräuchte nen fertigen syntax wenn ich selber drauf kommen soll.

mfg

[Cyrus1985]

könnte das mal jemand fertig schreiben!? ;/ ich blick das nix, bräuchte nen fertigen syntax wenn ich selber drauf kommen soll.

mfg

hab leider selbst wenig Ahnung von der Turbo Pascal Syntax, aber ich hab ne fertige Implementierung für TP gefunden:


program bubble;
uses crt;
const max = 5; { Festlegung für Größe des Feldes }
TYPE tfeld = array[1..max] of integer;
VAR feld : tfeld;
i : integer; procedure tausch (Var f: tfeld; a,b: integer); {---tauscht Zahlen---}
var c : integer;
begin
c := f[a];
f[a] := f[b];
f[b] := c;
end;

procedure ausgabe(f : tfeld);{---Ausgabe im Textmodus---}
begin
for i := 1 to max do write(f[i],' ');
writeln;
end;

procedure bubblesort(VAR f : tfeld);
VAR get : boolean;
k : integer;
BEGIN
k := 1;
REPEAT
get := false;
for i := max downto k do
If f[i] < f[i-1] Then
begin
tausch(f,i,i-1);
get := true; {boolsche Variable bei Tausch auf true gesetzt }
end;
k := k + 1;
UNTIL get = false; { Abbruchbedingung }
END;

Begin {Hauptprogramm}
clrscr;
randomize;
init(feld); {Initialisierung des zu sortierenden Feldes }
ausgabe(feld);
bubblesort(feld);
ausgabe(feld);
readln;
End.



vielleicht hilfts ja was ;)

[saNz]

danke danke danke!!!

Aber, so weit waren wir noch nicht ;] ich kom damit überhaupt nicht klar, könnte nur an nen fertigen source mir das erklären >.< greeTz

[saNz]

Habs gepackt ;]

program sortieren;
uses crt;
var A, B, C:integer;
procedure tauschen (var x, Y:integer);
var zwischenwert:integer;
begin
zwischenwert :=X;
X:= Y;
Y := Zwischenwert ;
end;
begin
clrscr;
writeln ('1zahl');
readln (A);
writeln ('2zahl');
readln (B);
writeln ('3zahl');
readln (C);
if A > B then tauschen (A,B);
if B > C then tauschen (B,C);
if A > B then tauschen (A,B);
writeln ('',A,' - ',B,' - ',C,'');
readkey;
end.

greeTz

[Scavi]

Nicht besonders nutzerfreundlich wenns nur für 3 Zahlen geht. Was verstehst du denn nicht an dem Bubblesort?

[Xpyder]

Also, Bubblesort funzt so:
Man durchläuft eine Schleife für alle Werte-1,
und vergleicht immer, ob zwei benachbarte Werte schon
in der "richtigen" Reihenfolge stehen. (d.h. der erste
muß kleiner oder gleich dem zweiten sein).
Sind sie das, passiert nix. Sind sie's nicht, werden sie
"sortiert", also getauscht.
(Werte-1, weil ja mit Nachfolger gecheckt wird. Der
letzte Wert hat ja keinen Nachfolger mehr!)
So. Wenn man nun drüber nachdenkt, kommt man zu dem
Ergebnis, daß jetzt natürlich noch nicht alle Werte
sortiert sind, aber: auf jeden Fall steht der größte Wert
als letzter, weil er halt auf jeden Fall "durchgetauscht"
wurde.
Also verringert man die Anzahl Werte um 1 und wiederholt
das ganze für den Rest... Und so weiter. Bis die Anzahl
Werte nur noch 1 ist.

{Angenommen, die Zahlen stehen im Array Zahl[1..255]
Dummy ist zum Tauschen, i und j sind Schleifenvariablen.
Anzahl ist die Anzahl eingegebener Daten}
var i,j,Anzahl:word;
zahl:array[1..255]of byte;
dummy:byte;
begin
writeln('Beispiel:');
Anzahl:=25;
randomize;
for j:=1 to Anzahl do zahl[j]:=random(100); {Damit simuliere ich jetzt mal zufällige Zahlen}
for j:=1 to Anzahl do write(zahl[j]:3);writeln; {Und die gebe ich aus}

if Anzahl>1 then {Natürlich nur sortieren, wenn mehr als 1 Wert!}
for i:=Anzahl-1 downto 1 do
for j:=1 to i do
if Zahl[j]>Zahl[j+1] then
begin Dummy:=Zahl[j];Zahl[j]:=Zahl[j+1];Zahl[j+1]:=Dummy;end; {Beide tauschen!}

for j:=1 to Anzahl do write(zahl[j]:3);writeln;{Und wieder ausgeben, damit man sieht, daß sortiert wurde}
end.


So, und jetzt das ganze nochmal für den Fall, daß es ein String sein soll,
den jemand eingibt:

{Dummy ist zum Tauschen, i und j sind Schleifenvariablen.
Anzahl ist die Anzahl eingegebener Daten - also die Stringlänge.
Dummy muß hier natürlich ein Char sein - weil Strings wie ein "Array of char" funktionieren.}
var i,j,Anzahl:word;
zahl:string;
dummy:char;
begin
write('Bitte Wert eingeben:');
readln(zahl); {Hier Wert-Eingabe}
Anzahl:=length(zahl); {Länge ermitteln}

{Die Sortiererei ist GENAU DIESELBE}
if Anzahl>1 then {Natürlich nur sortieren, wenn mehr als 1 Wert!}
for i:=Anzahl-1 downto 1 do
for j:=1 to i do
if Zahl[j]>Zahl[j+1] then
begin Dummy:=Zahl[j];Zahl[j]:=Zahl[j+1];Zahl[j+1]:=Dummy;end; {Beide tauschen!}

writeln(zahl);{Und wieder ausgeben, damit man sieht, daß sortiert wurde}
end.


Kleiner Tip:
Ich benutze nie sowas wie Anzahl:=length(zahl), sondern definiere das so:
var anzahl:byte absolute zahl;
Damit steht anzahl gleich auf dem 1. Byte des Strings, das die Länge angibt.

Achja, und Dinge wie j+1 kann man auch mit succ(j) ausdrücken.
Für Anzahl-1 kann man auch pred(Anzahl) schreiben.
Das Ergebnis ist jeweils dasselbe, aber inc, dec, succ und pred erzeugen
in Pascal schnelleren Code.


Großer Tip:
Für größere Mengen lohnt sich eventuell folgendes "Tuning" des Verfahrens:

Man merkt sich einfach in jeder "inneren" Schleife, an welcher Stelle als
erstes und an welcher als letztes sortiert wurde. Beide rechnet man minus 1.
(Außer die "erste" Stelle ist bereits 1!)
Und das sind für den nächsten Durchlauf die neuen Start- und End-Werte für
die innere Schleife. Gab es KEINE Sortierung mehr, oder nur EINE (d.h.
erster und letzter Wert sind gleich - oder nicht definiert), dann ist das
Feld fertig sortiert.
Die äußere Schleife ist in diesem Fall auch keine FOR-Schleife mehr, sondern
eine REPEAT UNTIL Schleife. (Wobei halt nach UNTIL die Abbruchbedingung
steht - nämlich, daß nichts mehr zu sortieren ist.)

Falls Interesse an dieser Lösung (also falls Du's nicht selber
hinkriegst), laß es mich wissen.

Hoffe, das hilft.

[saNz]

Danke :) nun hab's das gecheckt :)

[Diogenes]

Here's your rersident moderator.

@saNz: Schon, daß du's gecheckt hast, aber wenn Du Hilfe willst, schreib's vorne in den Titel - "need help" und ähnliches versteht sich fast von selbst, aslo kannst - nein, sollst - es weglassen, denn man will ja vor allem wissen, weswegen man Dir helfen soll.

[drstar]

Nur so am Rande: Bei großen Zahlenmengen ist der Bubblesort-Alghorithmus nicht die beste Wahl, der Quicksort leistet dann wesentlcih schnellere Dienste...

Bei TP7 werden einige Demoprogramme mitgeliefert, schau dir mal DIRDEMO.PAS an, da wird vom Quicksort-Alghorithmus Gebrauch gemacht... Bei Hilfe einfach mailen an:

drstar@lycos.de

[Scavi]

Nur so am Rande: Bei großen Zahlenmengen ist der Bubblesort-Alghorithmus nicht die beste Wahl, der Quicksort leistet dann wesentlcih schnellere Dienste ...bloss weil Quicksort so heißt, bedeutet dies nicht, dass er immer schnell ist. Der worst case ist ebenfalls quadratisch! O(n²)

[drstar]

Ich hab mal BubbleSort gegen Quicksort antreten lassen, mit folgendem Resultat:

Bei geringen Zahlenmengen ist Bubblesort schneller.
Grund: Durch die Rekursion in Quicksort entsteht zusätzlicher Verwaltungsaufwand, der sich bei geringen Zahlenmengen einfach nicht rechnet.

Bei großen Zahlenmengen ist die Sache jedoch genau umgekehrt. Auf nem 486er hatte ich bei 10000 Zahlen ungefähr folgende Werte:

Quicksort: 4,2 sec

Bubblesort: irgendwas über 30 sec...

[Scavi]

Dann probiere mal eine umgekehrt sortierte Liste zu sortieren und eine sortierte Liste.

[Diogenes]

Dann probiere mal eine umgekehrt sortierte Liste zu sortieren und eine sortierte Liste.
Das sind Extremfälle.

[Scavi]

Das sind Extremfälle. Yup, die aber den worst case hervorrufen.