Quicksort Algorithmus

[gamma21]

Ich würde gerne den Quicksort Algorithmus schreiben und habe dazu auch schon viel Code im Netz gefunden, jedoch klappt es bei mir noch nicht.

    static int quickSort(ArrayList<Integer> numbers, int low, int high) {
        int i = low;
        int j = high;
        int pivot = (numbers.get(i)+numbers.get(j))/2;
        if (i < j) {

            while (i < j) {
                while (numbers.get(i) <= pivot) {
                    i++;
                }
                while (numbers.get(j) > pivot) {
                    j--;
                }
            }
            int temp = numbers.get(i);
            numbers.add(i, numbers.get(j));
            numbers.add(j, temp);
            i++;
            j--;

       }
        if(low<j){
            quickSort(numbers, low, j);}

        if(i<high){
                quickSort(numbers,i, high);
        }
    return 0;
    }

Fehlermeldung bekomme ich keine, jedoch stimmt das Ergebnis nicht.
Fällt jemanden ein Fehler auf?

 

[kneitzel]

Also ArrayList.add fügt ein weiteres Element hinzu. Also wenn Du vorher n Elemente hattest, dann hast Du danach n+1 Elemente.

Was Du wohl aufrufen wolltest war ArrayList.set, welches ein Element überschreibt.

ArrayList (Java Platform SE 7 )

 

[gamma21]

Stimmt das wollte ich. Wenn ich aber

int temp = numbers.get(i);
numbers.set(i, numbers.get(j));
numbers.set(j, temp);

schreibe, komme ich dennoch nicht auf die gewünschte Lösung.
Habe ich irgendwo einen logik Fehler?

 

[gamma21]

Habe nun die

if (i < j)

Schleife entfernt. Leider sortiert der Algorithmus immer noch nicht richtig.
Die Eingabewerte low und high sind zu beginn 0 und numbers.size()-1.
Kann keiner weiterhelfen?

 

[kneitzel]

Also mein Problem ist gerade, dass ich bei Deinem Code den QuickSort Algorithmus nicht erkenne. Zumindest finde ich unter https://de.wikipedia.org/wiki/Quicksort
eine andere Beschreibung.

Und bei Deinem Code kommt es direkt zu einer Endlosschleife in meinen Tests.
Als Eingabe habe ich 9, 5, 1, 3 gegeben. Aufruf ist dann mit 0, 3 als Grenze.
pivot ist dann 6 bei mir
i (0) ist kleiner j (3):
9 ist nicht kleiner gleich 6, also kein i++
3 ist nicht größer 6 also kein j++
==> While wird nicht verlassen.

Also so kann es aus meiner Sicht nicht funktionieren und das ist kein QuickSort Algorithmus.

 

[gamma21]

Den Alggorithmus habe ich mithilfe dieser Beschreibung versucht umzusetzen.
Ich gehe den Code einmal durch:
Zuerst suche ich mir ein Pivotelement (in meinem Fall nehme ich die Mitte).
Danach vergleiche ich, ob die Elemente kleiner oder größer als das Pivot Element sind. Wenn das Element an der Stelle i kleiner ist als das Pivot Element erhöhe ich i und schaue mir das nächste Element an.
Habe ich einen Wert gefunden der kleiner ist als das Pivot Element vertausche ich dieses mit jenem welches größer ist.
Mein momentaner Code:

   static int quickSort(ArrayList<Integer> numbers, int low, int high) {
        int i = low;
        int j = high;
      
        int pivot = numbers.get((low +high)/2);

        while(i <= j) {


                while (numbers.get(i) < pivot) {
                    i++;
                }
                while (numbers.get(j) > pivot) {
                    j--;
                }

            if(i<=j) {
                int temp = numbers.get(i);
                numbers.set(i, numbers.get(j));
                numbers.set(j, temp);
                i++;
                j--;
            }

       }
       if(low<j){
            quickSort(numbers, j, low);}

       if(i<high){
                
                quickSort(numbers,i, high);
        }
    return 0;
    }

durchläuft zumindest bei mir keiner Endlosschleife.
Kannst du mir denn nicht zumindest einen Tipp geben, woran es bei mir scheitert?

pivot ist dann 6 bei mir

Wie kommst du darauf? Muss nicht das Pivot Element Teil des Arrays sein?

 

[Meniskusschaden]

durchläuft zumindest bei mir keiner Endlosschleife.

Stimmt. Ursprünglich war es aber so.

Kannst du mir denn nicht zumindest einen Tipp geben, woran es bei mir scheitert?

Wenn du die Teilarrays sortieren lässt, solltest du auf korrekte Übergabe der Unter- und Obergrenze achten.

pivot ist dann 6 bei mir

Wie kommst du darauf?

(9+3)/2 = 6

Muss nicht das Pivot Element Teil des Arrays sein?

Ja (Ist es inzwischen auch, war es zum Zeitpunkt des Postings von @kneitzel aber noch nicht).

 

[Xyz1]

Nabend. Wieso habt ihr nur eine Methode? Ich brauchte, ohne Akrobatik, mindestens drei Methoden...

import java.util.*;
public class QS {
	public native void swap(ArrayList<Comparable> list, int i, int j);
	void qs1(ArrayList<Comparable> list) {
		qs1(list,0,list.size()-1);
	}
	void qs1(ArrayList<Comparable> list, int l, int r) {
		if (l<r) {
			int t=t(list,l,r);
			qs1(list,l,t-1);
			qs1(list,t+1,r);
		}
	}
	int t(ArrayList<Comparable> list, int l, int r) {
		int i=l, j=r-1, p=r;
		do {
			while (i < r && list.get(i).compareTo(list.get(p))<0)
				i++;
			while (j > l && list.get(j).compareTo(list.get(p))>=0)
				j--;
			if (i<j) {
				Comparable c = list.get(i);
				list.set(i, list.get(j));
				list.set(j, c);
			}
		} while (i<j);
		Comparable c = list.get(i);
		list.set(i, list.get(p));
		list.set(p, c);
		return i;
	}
	public static void main(String[] args) {
		QS q = new QS();
		ArrayList<Comparable> list = new ArrayList<>();
		list.add(4);
		list.add(4);
		list.add(2);
		list.add(2);
		list.add(5);
		list.add(1);
		list.add(6);
		list.add(0);
		q.qs1(list);
		System.out.println(list);
	}
}

public native void swap(ArrayList<Comparable> list, int i, int j); wollte ich eigentlich noch in C schreiben, um zwei Elem ohne Variable zu tauschen, indem die Adressen geswappt werden, um Zeit zu sparen.... aber das war mir wieder zu kompliziert.

Wie es auch sei, so wie es oben steht steht es fast 1:1 bei Wikipedia - und ich denke nicht, das diese sich irren...

(Achtung: Type Safety!!!)

 

[mihe7]

Wieso habt ihr nur eine Methode?

Weil er den Algorithmus von https://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html implementiert hat.

 

[Xyz1]

aso, warum denn auch einfach, wenn's auch ...

 

[gamma21]

Wenn du die Teilarrays sortieren lässt, solltest du auf korrekte Übergabe der Unter- und Obergrenze achten.

Danke für den Tipp. Habe nun in

 if(low<j){
            quickSort(numbers, j, low);}

j und low vertauscht und nun sortiert er wie gewünscht. Danke!

 

[Susi123]

Wenn ich folgende Liste nach Quicksort sortieren solle, habe ich das dann richtig verstanden?
Ausgangsliste: 3, 1, 7, 2, 8, 9, 6, 5, 4

3​	1​	7​	2​	8​	9​	6​	5​	4​
1​	2​	3​	7​	8​	9​	6​	5​	4​
1​	2​	3​	7​	8​	9​	6​	5​	4​
1​	2​	3​	7​	8​	9​	6​	5​	4​
1​	2​	3​	7​	8​	9​	6​	5​	4​
1​	2​	3​	6​	5​	4​	7​	8​	9​
1​	2​	3​	6​	5​	4​	7​	8​	9​
1​	2​	3​	5​	4​	6​	7​	8​	9​
1​	2​	3​	5​	4​	6​	7​	8​	9​
1​	2​	3​	4​	5​	6​	7​	8​	9​
1​	2​	3​	4​	5​	6​	7​	8​	9​
1​	2​	3​	4​	5​	6​	7​	8​	9​

 

[mihe7]

@Susi123 kannst Du leicht selbst überprüfen, z. B. mit https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/visualize/