Java Editor Sortieralgorithmen - Hilfe bei "einfacher Kellersortierung" nötig :)

G

ghost_zerOX

Mitglied
Moin Leute!

Das hier ist mein erster Post bzw. meine erste Frage und ich bin hier ein Neuling! :)
Meine Frage richtet sich an die Umsetzung von Sortieralgorithmen mit dem Java Editor.

Ich möchte nicht lang herumreden, jedoch noch kurz etwas erläutern:
In der Schule "lernen" wir Java bei einem 70 jährigen Lehrer, der die ganze Zeit Quellcode an die Tafel malt, wir diesen abschreiben und dann irgendwie versuchen im Editor umzusetzen...

Ich für meinen Teil komme mit ihm als Person super klar, verstehe aber selber nur wenig, bzw. stoße mehr und mehr an meine Grenzen.
Ich habe nun die Sortalgorithmen Bubble, Bucket, Insertion, Selection hinbekommen. Diese haben wir soweit auch einigermaßen im Unterricht besprochenn, jedoch erhielten wir nun alle eine Mail, wo drin stand, dass diese Programme aufgrund eines Fehlers irgendwas vertauschen und falsch sortieren, obwohl der Code stimmt... Dies kommt eventuell davon, dass wir in der Schule mit einer alten Javaversion arbeiten und zu hause mit der aktuellen. Hierbei passiert es dann auch, dass, wenn man im jFrame arbeitet, der Editor in der Schule nur beim Einfügen eines Buttons oder Ähnlichem einen Fehler anzeigt, da das Programm den Code selbst an die falsche Stelle schreibt...

Nun aber sollen wir ein Programm zur "einfachen Kellersortierung" programmieren.
Aber hierzu finde ich nichts im Internet.
Daher meine Frage: Was ist das bzw. würde mir ggf. der wahre englische Begriff reichen, um danach zu googeln, um dass dann in ein Programm zu fassen...


Ich möchte anmerken, dass ich es sehr schade finde, dass Informatikunterricht im 21. Jahrhundert so bedauerlich ist, aber ich weiß wirklich nicht weiter und hoffe daher auf Rat und Hilfe hier!



VIELEN LIEBEN DANK!
 
Nach Datum sortieren Nach Zustimmungen sortieren
M

Meniskusschaden

Top Contributor
ghost_zerOX hat gesagt.:
Nun aber sollen wir ein Programm zur "einfachen Kellersortierung" programmieren.
Aber hierzu finde ich nichts im Internet.
Daher meine Frage: Was ist das bzw. würde mir ggf. der wahre englische Begriff reichen, um danach zu googeln, um dass dann in ein Programm zu fassen...
Zum Vergrößern anklicken....
Keller ist ein anders Wort für Stapel oder Stack. Ein einfacher Sortier-Algorithmus könnte mit zwei Stacks und einer Hilfsvariablen realisiert werden:
Aus dem Eingabestack mit den unsortierten Daten werden die Elemente sukzessive über die Hilfsvariable in den zunächst leeren Ausgabestack geschrieben. Falls dabei im Ausgabestack die Sortierfolge verletzt würde, werden vor dem Einfügen der Hilfsvariablen so viele Elemente wie nötig wieder vom Ausgabestack entnommen und an der Hilfsvariablen vorbei in den Eingabestack zurück geschrieben.
 
Zustimmen 0
G

ghost_zerOX

Mitglied
Ok. Vielen Dank erst einmal für eure Antworten! :)

BestGoalkeeper hat gesagt.:
Diese Liste verlangt keine Vollständigkeit: https://de.wikipedia.org/wiki/Liste_von_Algorithmen#Sortieralgorithmen

aber sicher, dass er nicht Insertionsort meint? https://www.quora.com/Is-insertion-sort-in-place

Sortiert ihr Lists oder Arrays?
Zum Vergrößern anklicken....
Meniskusschaden hat gesagt.:
Keller ist ein anders Wort für Stapel oder Stack. Ein einfacher Sortier-Algorithmus könnte mit zwei Stacks und einer Hilfsvariablen realisiert werden:
Aus dem Eingabestack mit den unsortierten Daten werden die Elemente sukzessive über die Hilfsvariable in den zunächst leeren Ausgabestack geschrieben. Falls dabei im Ausgabestack die Sortierfolge verletzt würde, werden vor dem Einfügen der Hilfsvariablen so viele Elemente wie nötig wieder vom Ausgabestack entnommen und an der Hilfsvariablen vorbei in den Eingabestack zurück geschrieben.
Zum Vergrößern anklicken....
Meniskusschaden hat gesagt.:
Mein Algorithmus-Vorschlag ist jedenfalls ein InsertionSort. Man könnte aber natürlich auch andere Sortierverfahren mit Stacks realisieren. Bis jetzt schränkt die Aufgabenstellung das ja noch nicht ein.
Zum Vergrößern anklicken....

Soweit ich das beurteilen kann soriteren wir Arrays und ich glaube, dass nicht Insertion gemeint ist, da wir das bereits gemacht haben und er von einem "neuen Verfahren" sprach.
BestGoalkeeper hat gesagt.:
Wieso nennt man es dann nicht Insertionsort. ;)

@ghost_zerOX : Anstatt nur einem Array hast du zwei und das Verfahren sollte ähnlich sein...
Zum Vergrößern anklicken....



Den Programmcode, der wahrscheinlich nicht sonderlich anschaulich ist, packe ich mal in die Dateianhänge. Dazu noch die Aufabenstellung, damit vielleicht noch einiges klar wird.

aufgabe.jpeg

Wir haben davon noch nie etwas gehört, sollen es aber jetzt programmieren...

Ich werde es jetzt einmal mit Stack probieren, glaube aber dass das schief geht.
 

Anhänge

  • Sortieren2.zip
    19,4 KB · Aufrufe: 1
Zustimmen 0
K

kneitzel

Gast
Also der Keller ist vergleichbar mit einem Stack. Aber das Vorgehen ist leider nicht komplett beschrieben meine ich.

Grundregeln sind einfach:
- Auf den Stack können immer nur kleinere Werte als das aktuell oberste geschoben werden.
- Von der unsortierten Liste kommen die Elemente in den Keller / auf den Stack, so möglich.
- Ist oberes nicht möglich, dann wandert das oberste Element vom Keller in die sortierte Liste.

Was meiner Meinung nach fehlt ist: Der erste Schritt ist nur möglich, wenn das letzte Element auf der sortierten Liste kleiner ist, als das erste Element auf der unsortierten Liste. Ist dies nicht der Fall, dann müssen erst Elemente von der sortierten Liste in den Keller, bis dies zutrifft.

Das kann man leicht testen, indem man am Ende des Beispiels noch eine -1 einfügt oder so. Die muss ja irgendwie bis an den Anfang kommen. Dazu müssen dann ja alle Elemente aus der sortierten Liste erst raus genommen werden um dann die -1 an den Anfang zu setzen.

Edit: Verschrieben - die zusätzliche Regel betrifft die erste Grundregel - nicht die letzte.
 
Zustimmen 0
G

ghost_zerOX

Mitglied
kneitzel hat gesagt.:
Also der Keller ist vergleichbar mit einem Stack. Aber das Vorgehen ist leider nicht komplett beschrieben meine ich.

Grundregeln sind einfach:
- Auf den Stack können immer nur kleinere Werte als das aktuell oberste geschoben werden.
- Von der unsortierten Liste kommen die Elemente in den Keller / auf den Stack, so möglich.
- Ist oberes nicht möglich, dann wandert das oberste Element vom Keller in die sortierte Liste.

Was meiner Meinung nach fehlt ist: Der erste Schritt ist nur möglich, wenn das letzte Element auf der sortierten Liste kleiner ist, als das erste Element auf der unsortierten Liste. Ist dies nicht der Fall, dann müssen erst Elemente von der sortierten Liste in den Keller, bis dies zutrifft.

Das kann man leicht testen, indem man am Ende des Beispiels noch eine -1 einfügt oder so. Die muss ja irgendwie bis an den Anfang kommen. Dazu müssen dann ja alle Elemente aus der sortierten Liste erst raus genommen werden um dann die -1 an den Anfang zu setzen.

Edit: Verschrieben - die zusätzliche Regel betrifft die erste Grundregel - nicht die letzte.
Zum Vergrößern anklicken....

Ok. Das habe ich inhaltlich soweit verstanden, nur habe ich noch immer keine Ahnung, wie ein solcher Stack als Code aussieht.

Das einzige, was ich gerade hinbekommen habe ist, dass ich einem Array erst einmal diese unsortierten Zahlen aus Aufgabe 1 gegeben habe und mir diese auf einem Textfeld ausgeben lasse:

Java: 
[/B]
stackunsortiert = new int[6];   
int[] stackunsortiert = {6,5,1,3,2,4};
    
    //Ausgabe
    for (i=0; i<6; i++) {
         inhaltstack = jTstack.getText();
         inhaltstack=inhaltstack+stackunsortiert[i]+"; ";
         jTstack.setText(inhaltstack);
      }
[B]
 
Zustimmen 0
K

kneitzel

Gast
Also generell ist die Implementierung ein Detail, das frei gewählt werden kann. Das kann man zur Not in eine Klasse kapseln und lässt sich dann jederzeit auswechseln.

Möglichkeiten:
a) Es gibt einen Stack im Java Framework. (java.util.Stack)
b) Eine eigene dynamische Implementation wie eine einfach verkettete Liste ist denkbar.
c) Man kann einfach ein Array nutzen. Du willst ein Array der Größe n erzeugen, also brauchst Du einen Stack, der maximal n Element hält. So ein Array kannst Du erstellen. Dann hast Du einen Zähler, der angibt, wie viele Elemente bereits hinzugefügt wurden. Einfügen fügt an diese Stelle ein Wert ein und erhöht um ein. Herausnehmen eines Elements nimmt das Element von (diesem Zähler - 1) und reduziert den Zähler um eins. Das wäre ggf. die einfachste Implementation eines Stacks für so eine Aufgabe.

Das ist natürlich erst einmal keine komplette Liste von Möglichkeiten ...
 
Zustimmen 0

Aktuelle Jobs

Neue Themen


Oben