Quicksort Algorithmus

gamma21 · 30. Apr 2019

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.

Code:

    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 · 30. Apr 2019

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 · 30. Apr 2019

Stimmt das wollte ich. Wenn ich aber

Code:

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 · 30. Apr 2019

Habe nun die

Code:

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 · 30. Apr 2019

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 · 1. Mai 2019

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:

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 · 1. Mai 2019

gamma21 hat gesagt.:
durchläuft zumindest bei mir keiner Endlosschleife.

Stimmt. Ursprünglich war es aber so.

gamma21 hat gesagt.:
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.

gamma21 hat gesagt.:
kneitzel hat gesagt.:

pivot ist dann 6 bei mir

Zum Vergrößern anklicken....

Wie kommst du darauf?

(9+3)/2 = 6

gamma21 hat gesagt.:
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 · 1. Mai 2019

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

Java:

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 · 1. Mai 2019

Tobias-nrw hat gesagt.:
Wieso habt ihr nur eine Methode?

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

Xyz1 · 1. Mai 2019

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

gamma21 · 1. Mai 2019

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

Code:

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

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

Susi123 · 25. Dez 2019

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 · 25. Dez 2019

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

Quicksort Algorithmus

gamma21

Mitglied

kneitzel

Gast

gamma21

Mitglied

gamma21

Mitglied

kneitzel

Gast

gamma21

Mitglied

Meniskusschaden

Top Contributor

Xyz1

Gast

mihe7

Top Contributor

Xyz1

Gast

gamma21

Mitglied

Susi123

Aktives Mitglied

mihe7

Top Contributor

Aktuelle Jobs

Neue Themen

Ähnliche Themen

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

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

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