Eigener Sort-Algorithmus Java

[xActionx]

Hey Leute,

ich versuche derzeit eine eigene Funktion zu schreiben, die mir ein Array aus Chars sortiert. (und ja ich weiß, dass es dafür eine fertige gibt. Die möchte ich aber nicht benutzen )

Bisher sieht mein Code wie folgt aus:

public class sort {
	public static void main(String args[]) { 

char[] input;
input = new char[4];

input[0] = 'c';
input[1] = 'a';
input[2] = 'x';
input[3] = 'b';

int length = input.length;

char letter;
int i = 0;
int j = 1;

while (i < length) {
	while (j  < length) {
		if (input[j] < input[j - 1]) {
			letter = input[j];    
               		input[j] = input[j-1];  
               		input[j-1] = letter;  
			}
		j++;
		}
	i++;
	}

System.out.println(input[0]);
System.out.println(input[1]);
System.out.println(input[2]); 
System.out.println(input[3]);

	}
}

Wenn nur 3 Chars im Array sind funktioniert der Algorithmus problemlos. Sobald der 4. jedoch dazu kommt wirft er was durcheinander. Ich sitze jetzt schon einige zeit dran und bekomme es nicht auf die Reihe.
Aber vllt gibt es hier ja jemand intelligenteren der das drauf hat.

Achja vllt sollte ich noch anmerken, dass ich das ganze möglichst ohne for-Schleifen lösen möchte.

MFG

P.S. Das ganze kann auch in C/C++ oder Ruby geschrieben sein. Das kann ich übersetzen

 

[Malkolm]

Du setzt j nie zurück. Am Anfang der i schleife solltest du so was wie j=i+1 reinsetzen.

 

[GottesMissionar]

Funktioniert mit 3 Chars auch nicht. teste mal mit den Werten
X
C
A

Das Ergebnis dürfte dann
C
A
X
sein, wenn ich das vom Handy aus richtig sehe.


Überleb dir anhand dieses Beispiels warum es nicht geht und teile uns deine Gedanken mit. ich helf dir gerne beim Mitdenken.

 

[Crysis nerd]

Puh, also es gibt so einige Sortier-Algorithmen. D.h. komplett unterschiedliche Herangehensweisen, sowas zu lösen. Ein Klassiker am Anfang ist Bubblesort, aber ich würde dir lieber Selectionsort empfehlen, da ich den noch einfacher finde. Das Grundprinzip ist folgendes:

• Speicher dir in einer int-variable eine "Grenze" in deinem Array: Links von der Grenze ist alles sortiert, rechts davon alles unsortiert.
• Solange noch nicht das ganze Array sortiert ist (also solange die "Grenze" noch nicht der Array-Länge entspricht)
  • Suche im unsortierten Teil des Arrays das Minimum
  • Tausche das Minimum mit dem ersten Element des unsortierten Teils
  • Erhöhe deine "Grenze" um 1, da ja jetzt ein Element mehr sortiert ist.

Das ganze ist hier mal visualisiert: https://www.youtube.com/watch?v=92BfuxHn2XE
Dort sieht man, wie immer das Minimum gesucht wird und ganz nach links im Array gepackt wird.

Also wenn du so etwas angehst: Am Besten vorher mal genau überlegen, wie es funktionieren soll. Und erst dann programmieren.

Viel Glück!

EDIT: Hier in Rust implementiert Rust Playground

 

[sepei]

Wie oben schon erwähnt hast du dein J nie zurückgesetzt.
Hier mal der ausgebeserte funktionierende Code:

Ideone.com - eH51r4 - Online Java Compiler & Debugging Tool

public class sort {

    public static void main (String[] args) throws java.lang.Exception
    {
        char[] input;
input = new char[7];

input[0] = 'c';
input[1] = 'a';
input[2] = 'x';
input[3] = 'b';
input[4] = 'd';
input[5] = 'y';
input[6] = 'g';

int length = input.length;

char letter;
int i = 0;
int j = 1;
int printJ = 0;

while (i < length) {
    while (j  < length) {
        if (input[j] < input[j - 1]) {
            letter = input[j];    
                       input[j] = input[j-1];  
                       input[j-1] = letter;  
            }
        j++;
        }
    i++;
    j = i;
    }
    
    while (printJ < length) {
        System.out.println(input[printJ++]);
    }

    }
}

 

[Cinnayum]

Bei geschachtelten Schleifen mit while musst du dich selbst um den "Zustand" deiner Schleifenvariablen kümmern.
Bei geschachtelten for-Schleifen macht die Sprache das für dich, auch wenn die "exit"-Bedingung manchmal Knoten ins Gehirn machen kann, bis man die auf die Reihe kriegt .

Von daher mit Debugging-Tool die Variablen überwachen lassen und schrittweise durch den Code hüpfen (bzw. an den Schleifenenden Checkpoints setzen). Dann findest du solche Dinger recht schnell.

 

[Cookiebowser]

Wie oben schon erwähnt hast du dein J nie zurückgesetzt.
Hier mal der ausgebeserte funktionierende Code:

Ideone.com - eH51r4 - Online Java Compiler & Debugging Tool

Du musst j aber auch auf 1 zurücksetzen .

 

[xActionx]

Wow vielen Dank für die ganzen Antworte. Werde das ganze nacher einmal testen.

 

[GTA 3]

Mit MergeSort geht das ziemlich einfach finde ich, wenn du eine endliche Länge (mit gefüllten Arrays) hast. Musst du nen eigenen Sortalgorithmus machen ?

 

[xActionx]

Musst du nen eigenen Sortalgorithmus machen ?

Jo hab das ganze nämlich in ne neue und ziemlich unbekannte Sprache übersetzt.

 

[sven-a]

Geht bei ArrayLists nicht auch ein automatischer Sortieralgorithmus? Also ich meine einer der in Java.lang bereits implementiert ist? Meine mich da an irgendwas erinnern zu können.
Ansonsten haben wir das immer per Comperator gemacht und rekursiv die Funktion comparTo aufgerufen.

Ist aber schon etwas her