Sortierverfahren - allgemeine Lösung?

[clemensum]

Hallo allerseits!

Es geht darum, dass ich eine Liste an Elementen der Größe nach sortiert werden muss. Dabei DARF KEINE fertige Routine der Java-Bibliothek entnommen werden und muss eigenständig implementiert werden.

Dabei habe ich mir überlegt, dass ich ja zwei benachbarte Elemente jeweils vertauschen kann und zwar solange bis das (k+1)-te Element größer als k-tes Element FÜR ALLE k<=liste.length.

Mein Java-Code lautet:

import java.util.Arrays;

public class Sortieralgorithmus {

	// static double sortieren(int[] array ) {

	public static void main(String[] args) {
		int i = 0;
		int[] array = { 5, 7, 3, 2, 4, 6, 9, 8, 1 };
		int[] hilfsarray = new int[array.length];

		while (i < array.length) {
			hilfsarray[i] = array[i];
			i++;
		}

		while (array[i + 1] < array[i] ||??????????) {
			while (i < array.length - 1) {
				if (array[i] > array[i + 1]) {
					vertausche(array[i], array[i + 1]);
				}

				i++;
			}
			i = 0;
		}

		System.out.println(Arrays.toString(array));

	}

}

Das Problem:
Ich rätsle schon seit geraumer Zeit welche Bedingung ich der der äußersten Schleife füttern soll.
Ich weiß nicht, wie ich beibringen kann, dass er erkennen kann, wenn die Liste fertig sortiert ist. Ich nehme an, dass er ungünstigerweise so viele Fälle durchlaufen muss, wie es das Worst-Case Szenario offenbart. Gibt es eine Optimierung? Wie lautet hier überhaupt der Worst-Case? Ich nehme an, dieser liegt (genau) dann vor, wenn die Elemente in umgekehrter Reihenfolge darliegen. Also müsste ich die Anzahl der Schritte dafür überlegen und dies als Bedingung formulieren.

Meine Frage aber: Wie kann ich mir dies allgemein überlegen, etwa, wenn das Array mit Zufallszahlen gefüllt ist, Wie viele Schritte sind dann nötig, bis die Liste in eine geordneten Reihenfolge gebracht wird? :rtfm:

 

[Marco13]

So lange bis keine Vertauschungen mehr nötig waren (wie bei BubbleSort). Zum Sortieren sollte man aber doch die eine oder andere Webseite finden...

 

[bone2]

such dir eins aus:
Sortierverfahren ? Wikipedia
da sind alle samt pseudocode beschrieben

 

[Andi_CH]

Mal abgesehen davon, dass deine "vertausche" Mothode wohl nicht funktionieren wird (call by reference vs call by value) habe ich gar nicht zu verstehen versucht was dein Code soll (dazu ist es zu heiss)

Effizient kannst du selbst noch einbauen und die Exception die es gibt ist willentlich drin ... na ja irgend etwas sollst du ja auch noch zu tun haben

import java.util.Arrays;

public class PrimitvSort {

	public static void main(String[] args) {
		int[] array = { 5, 7, 3, 2, 4, 6, 9, 8, 1 };
		boolean etwasVertauscht;
		System.out.println(Arrays.toString(array));
		do {
			etwasVertauscht = false;
			for(int i=0; i<array.length; i++) {
				if(array[i]>array[i+1]) {
					etwasVertauscht = true;
					int tmp = array[i+1];
					array[i+1] = array[i];
					array[i] = tmp;
					System.out.println(Arrays.toString(array));
				}
			}
		} while (etwasVertauscht);
		System.out.println("============== fertig ==============");
		System.out.println(Arrays.toString(array));
	}
}

 

[clemensum]

UUps, ich sehe, da hat mir Jemand einen Code angeboten - jetzt bin ich Gott sei Dank auch selbst auf die Lösung des Grundkonzeptes gekommen

import java.util.Arrays;

public class Sortieralgorithmus {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = { 5,4,3,2,1};
		int[] hilfsarray = new int[100];
		int i = 0, j = 0;

		while (j < array.length) {
			if (array[j + 1] < array[j]) {
				hilfsarray[j] = array[j];
				hilfsarray[j + 1] = array[j + 1];
				array[j] = hilfsarray[j + 1];
				array[j + 1] = hilfsarray[j];
				
			}
		i++;
			if ((i == ((array.length)* (array.length -1 )) / 2 +10))
				break;	
			
			
			j++;

			if (j == array.length -1 )
				j = 0;
		

		}

		System.out.println(Arrays.toString(array));
	}

}

So, jetzt muss ich Wörter "ihrer Größe" nach sortieren. Da ich aber keine Methoden der API verwenden darf, bin ich ratlos wie ich das angehen soll.

Man darf ja nicht so etwas schreiben wie:
if(Hansi>Affe)

Gibt es eine Möglichkeit, strings nach ihrer (d.h. alphabetisch)Größe zu vergleichen ??
Gibt es da einen speziellen Befehl. (Ich meine aber ohne implements comparable) :rtfm:

 

[SlaterB]

Strings haben eine compareTo()-Methode,
das hast schon was mit Comparable zu tun, wieso das nicht? neu implementieren musst du zum Glück eher nicht

 

[bLaSt]

Strings haben eine compareTo()-Methode,
das hast schon was mit Comparable zu tun, wieso das nicht? neu implementieren musst du zum Glück eher nicht

Hinzu zu fügen ist vielleicht noch was die compareTo()-Methode zurückgibt.
Sie gibt dir -1, 0, 1 zurück.
Das heißt für deine if-Anweisung nicht anderes wie, dass wenn du -1 zurück bekommst ist der Wert kleiner als der mit dem du in verglichen hast und bei 1 ist er größer und bei 0 ist es der gleiche Wert
Ansonsten gibt es da noch die Collator Klasse. Da kann man sogar Landestypische Rechtschreibungen mit importieren

 

[clemensum]

Das Problem ist eben, dass man nicht "implements Comparable" verwenden soll.

Aso, wenn ich das jetzt nicht mehr neu implementieren muss, dann reicht es doch aus, einfach ein String-Array anstatt eines int-Arrays zu verwenden??

Aber wie kann ich dann vergleichen? Da muss sich wohl mein Lehrer geirrt haben. oder?? ???:L

 

[SlaterB]

- du schreibst nirgendwo in dein Programm 'implements Comparable',
- du verwendest String[] statt int[]
- du verwendest compareTo() statt <

diese Kombination haut mehr oder weniger hin, ok für dich?
wenn es dich glücklicher macht kannst du die Methode auch selber implementieren, vielleicht unter anderen Namen,
um Strings zu vergleichen muss man die chars paarweise anschauen, bei chars gibts dann auch wieder <,
der Originalcode lautet

   public int compareTo(String anotherString) {
	int len1 = count;
	int len2 = anotherString.count;
	int n = Math.min(len1, len2);
	char v1[] = value; // toCharArray()
	char v2[] = anotherString.value; // toCharArray()
	int i = offset;
	int j = anotherString.offset;

	if (i == j) {
	    int k = i;
	    int lim = n + i;
	    while (k < lim) {
		char c1 = v1[k];
		char c2 = v2[k];
		if (c1 != c2) {
		    return c1 - c2;
		}
		k++;
	    }
	} else {
	    while (n-- != 0) {
		char c1 = v1[i++];
		char c2 = v2[j++];
		if (c1 != c2) {
		    return c1 - c2;
		}
	    }
	}
	return len1 - len2;
    }

ohne Strings auf irgendeine Weise zu vergleichen gibts jedenfalls keine String-Sortierung

 

[bLaSt]

Das Problem ist eben, dass man nicht "implements Comparable" verwenden soll.

Aso, wenn ich das jetzt nicht mehr neu implementieren muss, dann reicht es doch aus, einfach ein String-Array anstatt eines int-Arrays zu verwenden??

Aber wie kann ich dann vergleichen? Da muss sich wohl mein Lehrer geirrt haben. oder?? ???:L

Um compareTo() zu verwenden brauchst du kein implements Comparable. Das kannst du ganz normal benutzen. Wir haben erst kürzlich sowas gemacht wo man ein Studentobjekt hatte und dieses nach Namen sortieren sollte mit Hilfe des Insertion Sort. Ich stell dir mal den Code Ausschnitt ein, damit du siehst was ich mein.

public class StudentArray {
	public void binarySort(Student[] arrayp, String namep){		// binärer Suchalgorihtmus. Vorher muss jedoch nach Namen sortiert worden sein
		sortStudentArray(arrayp);
		int l,r,m;																	
		l=0;																		// linke Seite, bei Arrays Standardmässig auf 0 gesetzt
		r = arrayp.length-1;														// rechte Seite, immer die Größe des Arrays-1, da die Zählung bei 0 beginnt
		m = 0;
		while(l <= r){
			m = (l+r)/2;
			if (namep.compareTo(arrayp[m].getName()) < 0){							// der Name wird lexikografisch nach unicode verglichen. verglichen wird der
				r = m-1;															// übergebene Name mit dem Namen aus dem Array, beginnend bei 0
			}																		// sollte dieser Wert kleiner 0 sein, so wird der äusserste Wert um eines verringert,
			else{																	// da das Feld leer ist
				l = m+1;															// Im anderen Fall wird die linke Seite um eins erhöht, um durch die einzelnen Felder
			}																		// zu schreiten
		}
		if (arrayp[r].getName().equals(namep)) {									// ist der aktuelle Name gleich dem übergebenen Namen, so wird es ausgegeben
			//System.out.println("l  :"+l+"   r   :"+r);
			System.out.println("\n" + arrayp[r].getName()+"\t"+arrayp[r].getAlter());
		}
		else {
			System.out.println("\nName nicht vorhanden\n");    								
		}
}