# einfache Sortierverfahren

:::spoiler Inhaltsverzeichnis
[toc]
:::

## Bubblesort

Schrittweiser Aufbau hin zum Algorithmus

**Erklärung**

1. Schritt: {3，1，0，2} Ausgangssituation
2. Schritt: {1，3，0，2} Position zwischen 1 und 3 wechseln
3. Schritt: {1，0，3，2} Position zwischen 0 und 3 wechseln
4. Schritt: {1，0，2，3} Position zwischen 2 und 3 wechseln
5. Schritt: {0，1，2，3} Position zwischen 0 und 1 wechseln
6. Schritt: {0，1，2，3} Position zwischen 1 und 2 so bleiben
7. Schritt: {0，1，2，3} Position zwischen 0 und 1 so bleiben :+1:

Beim Bubblesort Algorithmus wird ein Array – also eine Eingabe-Liste – immer paarweise von links nach rechts in einer sogenannten Bubble-Phase durchlaufen. Man startet mit der ersten Zahl und vergleicht diese mit ihrem direkten Nachbarn nach dem Sortierkriterium.

**Sortieralgorithmus**

public class BubbleSort {
  
    public void sort(int[]array) {
        
        int length = array.length;
        
        if (length > 0) {
            
            for (int i = 1; i < length; i++) {

                for (int j = 0; j < length - i; j++) {
// siehe (1)                    
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
       }
// siehe (2)                    
                }
            }
        }
    }
  }

:::spoiler Erläuterung von ZL
/* (1)
* Lassen Sie uns zuerst zwei for-Schleifen definieren: Die zweite for-Schleife wird verwendet, um zu definieren, wo die Zahlen, die wir vergleichen, abgeschnitten werden.
* Beispielsweise ist die Cut-off-Position der ersten Schleife j<array.length-1 (obwohl J<array.length-1, die letzten beiden zu vergleichenden Zahlen j und j+1 sind), und der Cut-off Position der zweiten Schleife ist j<array.length-2 (nachdem die erste for-Schleife mit Variable j endet, geht die for-Schleife mit Variable i weiter in Schleife i++, die zweite Schleife i=2, also die Position, an der die zweite Schleifenenden ist Array .length-2-1) und so weiter für die dritte und vierte Iteration.

*/

/* (2)

* Wenn die vorherige Zahl Array[j] größer ist als die letzte Zahl Array[j+1], dann vertausche die Positionen der beiden Zahlen. Wir definieren zuerst eine Variable temp, um den Wert von array[j] zu speichern, und weisen dann den Wert von array[j+1] an array[j] zu. Weisen Sie dann temp an array[j+1] zu, damit wir erfolgreich Zahlen an den Positionen j+1 und j austauschen können
*/

:::

[Video zu Bubble Sort](https://www.youtube.com/watch?v=xli_FI7CuzA)

## InsertSort

**Erklärung**

1. Schritt: {3, 1, 0} Ausgangssituation
2. Schritt: {1, 3, 0} Position zwischen 1 und 3 wechseln
3. Schritt: {1, 0, 3} Position zwischen 0 und 3 wechseln
4. Schritt: {0, 1, 3} Position zwischen 0 und 1 wechseln :+1:

Bei Insert-Sort soll man zuerst die 2. Zahl mit erste Zahl vergleichen. Wenn die 2. Zahl größer als die 1. Zahl ist, dann müssen diese vertauscht werden.

Nachdem die 2. Zahl mit der 1. Zahl verglichen und sortiert wurde, soll die nächste, 3. Zahl, mit der 2. genauso vergleichen werden. Nachdem die 3. Zahl mit der 2. ausgetauscht wurde, muss man die neue 2. Zahl mit der 1. Zahl vergleichen. Sollte die 1. Zahl grosser als die 2. Zahl sein, müssen diese vertauscht werden.

{%youtube JMRU2nh6bfs %}

**Übung**

:::spoiler Buchstabenfolge mit InsertSort sortieren
<iframe src="https://einstiegh5p.de/h5p/embed/28865" width="800" height="500" frameborder="0"></iframe><script src="https://einstiegh5p.de/sites/all/modules/h5p/library/js/h5p-resizer.js" charset="UTF-8"></script>
:::

**Sortieralgorithmus**

public class InSort {
    
    public static void main(String[] args) {   
        
        int[] a = {3, 1, 0};                     // siehe (1)
        
        for ( int i = 1; i < a.length; ++i ){         
            int item = a[i];                     // siehe (2)
            int j = i - 1;                       // siehe (3)
        
            while ( j >= 0 && item < a[j] ){     // siehe (4)
                a[j + 1] = a[j];                 // siehe (5)
                j--;                             // siehe (6)
            }
            a[j + 1] = item;                     // siehe (7)
            System.out.println( Arrays.toString(a) );
        }
    }
}

:::spoiler Erläuterung Vorschlag
* Zeile 7: For-Schleife mit Parameter i startet mit 1
* Zeile 9: in For-Schleife definieren wir j und j ist immer um 1 kleiner als i damit wir die 2. Zahl (a[i]) mit 1. Zahl (a[j]) vergleichen koennen.
:::

:::spoiler Erläuterung von ZL

/* (1)
* Wir schreiben hier eine for-Schleife mit Parameter i, i soll mit
* 1 anfangen, in der for-Schleife definieren wir noch int j, die immer um
* 1 kleiner als i sein muss, damit wir zum Beispiel am Anfang die 2te
* Zahl(a[i]) mit der erste Zahl (a[j])vergleichen können.
*/

/* (2)
* Wichtig:
* Während jedem i-ten for-Schleifen Durchlauf, verändert sich der Wert item nicht!!!
* Während des ersten Durchlaufes ist a[i]=1, deswegen item=1
* Während des zweiten Durchlaufes ist item=a[i+1]=a[2], nach dem ersten for-Schleifen Durchlauf sieht Array so aus {1,3,0}, deswegen ist a[2]=0 und item=0;
*/

/* (3)
* z.B wenn i==1,j==0,j ist immer um 1 kleiner als i. erst mal
* forSchleifeLaufen ist j=1-1=0
* 2te mal forSchleifeLaufen ist j=2-1=1
*/

/* (4)
* Wenn man whileSchleife reinkommen moechte, soll man zuerst die
* 2 Bedingungen in Klammer gleichzeitig erfuellen, wenn eine Bedingung
* nicht erfuellt wird, dann soll j raus von whileSchleife.
*/

/* (5)
* z.B waehrend erst mal forSchleife ist j==0,a[j+1]==a[1],und a[j]=a[0];
* das heisst jetzt ist der wert von a[1] genauso wie der wert von a[0],
* jetzt sieht die Array so aus{3 3 0};
*
* 2te mal ist a[j+1]=a[2],a[j]=a[1], so hier bedeutet a[2]=a[1]
* jetzt sieht die Array so aus{1 3 3}
*/

/* (6)
* waehrend erste mal laufen ist j=0-1=-1; deswegen j nachdem j--
* raus von whileSchleife
*
* waehrend 2te mal laufen ist j=1-1=0; deswegen j nachdem j--=0,
* und a[0]ist > item(item=0,a[0]=1) noch nicht raus von whileSchleife,
* dann a[0+1]=a[0], dann sieht Arrays so aus{1,1,3}
*/

/* (7)
* jetzt a[j+1]=a[-1+1]=a[0], a[0]=item,deswegen a[0]=1;jetzt sieht Array so aus{1,3,0}
* jetzt a[j+1]=a[-1+1]=a[0], a[0]=item,deswegen a[0]=0;jetzt sieht Array so aus{0 1 3}
*/

:::

## Selection-Sort

**Erklärung**

1. Schritt: {3, 1, 0, 2} Ausgangssituation
2. Schritt: {0, 1, 3, 2} Position zwischen 3 und 0 wechseln
3. Schritt: {0, 1, 3, 2} Position von 1 schon in der richtigen Position, braucht man nicht zu wechseln.
4. Schritt: {0, 1, 2, 3} Position zwischen 3 und 2 wechseln
5. Schritt: {0, 1, 2, 3} Position von 3 schon in der richtigen Position, braucht man nicht zu wechseln.:+1:

Die Selectionssortierung muss die Nummer an der aktuellen Position mit der Nummer nach der aktuellen Position vergleichen. Wenn die nachfolgenden Nummern größer als die aktuelle Nummer sind, muss die Nummer an der aktuellen Position nicht vertauscht werden. Andernfalls müssen Sie die finden kleinste Zahl unter allen Zahlen nach der aktuellen Zahl Positionen tauschen mit der Zahl an der aktuellen Position.

[LernVedio von Selection-Sort](https://www.youtube.com/watch?v=g-PGLbMth_g)

**Sortieralgorithmus**

public class SelectionSort {
    
	public void sort(int[]a) {
        
		for(int i=0;i<a.length-1;i++) {
         
            int min=i;
  // siehe (1)          
			for(int j=i+1;j<a.length;j++) {
  // siehe (2)              
				if(a[min]>a[j]) {
  // siehe (3)                  
					min=j;
				}
			}
            
  			if(min!=i) {
              
				int aux=a[i];
				a[i]=a[min];
				a[min]=aux;
  // siehe (4)              
			}
		}
	}
}

:::spoiler Erläuterung von ZL

/* (1)
* Lassen Sie uns zuerst eine for-Schleife schreiben und den Bereich der Variablen i auf 0 bis a.length-1 definieren (warum a.length-1 ist, erkläre ich im zweiten Schritt).

* Danach definieren wir in dieser Schicht der For-Schleife eine Variable min（Die Bedeutung von min ist die Position des Minimalwertes）. Wir lassen zunächst min=i standardmäßig, was bedeutet, dass die aktuell kleinste Zahl bei Position i ist.
*/

/* (2)
* Definieren Sie eine weitere for-Schleife innerhalb dieser Schicht der for-Schleife. Dieses Mal beginnt die Variable j der for-Schleife bei i+1, und der Bereich reicht von i+1 bis a.length, damit wir sicherstellen können, dass die Position von j muss nach Position i stehen, damit wir die Zahl an Position i mit allen Zahlen nach Position i vergleichen können.
*/

/* (3)
* Zum Beispiel, jetzt i=0, dann j=0+1=1, was wir jetzt tun müssen, ist zu vergleichen, ob a[i] kleiner als alle a[j] ist, wenn ja, dann ist i immer noch die Position von die kleinste Zahl, also ist min immer noch gleich i. Wenn die Nummer der Position von j kleiner ist als die Nummer der Position von i, dann ist der aktuelle Minimalwert nicht mehr i, sondern j. Wenn j weiter zu +1 wird und die Nummer der neuen j-Position immer noch kleiner als die Nummer der ursprünglichen j-Position ist, müssen Sie die minimale Position weiter aktualisieren.

*/

/* (4)
* Nun müssen wir beurteilen, ob die Position von min an der Position von i liegt oder transformiert wurde. Zu beachten ist, dass sich die if-Bedingung zu diesem Zeitpunkt noch in der ersten for-Schleife befindet.

* Wenn sich die Position von min nicht an der Position von i befindet, die wir ursprünglich definiert haben, müssen wir die Positionsnummer von i und die Positionsnummer von min vertauschen.

* Zuerst weisen wir der Variablen aux einen Wert als a[i] zu, der der Wert der Anfangszahl ist, die aux an der Position von i darstellt. Als nächstes müssen wir die Zahl an der Position von i transformieren, sodass a [i]=a[min], das heißt, a[i] sei gleich der kleinsten Zahl, die wir gefunden haben. a[min]=aux, was bedeutet, dass die Zahl an der min-Position gleich der Zahl an der ursprünglichen i-Position ist.

*/

/* wichtig:
* Nachdem die erste i=0-Schleifenposition vorbei ist, ist die Position von i=0 bereits die kleinste Zahl. Zu diesem Zeitpunkt erfordert die Position von i=1, dass wir die kleinste Zahl außer der ersten Zahl finden. Je größer die Position von i ist, desto kleiner ist der Bereich der zu vergleichenden Zahlen
*/

:::

## Mergesort

**Erklärung**
Der Mergesort sortiert gegebene Folgen durch das vorherige zerlegen aller Folgenglieder (devide and conquer). Hierbei wird in jedem Schritt eine Teilung in Array.length/2 für jedes bestehende Array durchgeführt. Die Teilung endet, sobald alle Teilarrays eine Länge von 1 haben und entsprechend nicht weiter teilbar sind.
Nach der erfolgreichen Zerlegung werden die Teilarrays aufsteigend gegeneinander von links beginnend verglichen und in ein neues gemeinsames Array verbracht. Der Vergleich ist beendet, wenn alle Elemente in einem Array von der Länge Array.length des ursprünglichen Arrays sortiert sind. (vgl. [Merge sort in 3 minutes](https://www.youtube.com/watch?v=4VqmGXwpLqc))

Gegeben sei die Folge [78, 14, 66, 2, 67, 5, 3, 35]

1. Schritt: [78, 14, 66, 2] [67, 5, 3, 35] Teilung des Arrays in Array.length/2
2. Schritt: [78, 14] [66, 2] [67, 5] [3, 35] Teilung in Array.length/2
3. Schritt: [78] [14] [66] [2] [67] [5] [3] [35] Teilung in Array.length/2, nicht weiter teilbar
4. Schritt: [14, 78] [2, 66] [5, 67] [3, 35] Beginn Sortierung, Vergleich beginnend von Array[0]
5. Schritt: [2, 14, 66, 78] [3, 5, 35, 67] Vergleich des jeweils nächsten Arrays
6. Schritt: [2, 3, 5, 14, 35, 66, 67, 78] Array sortiert, Vergleich abgeschlossen

**Darstellung in Java** (vgl. [Merge Sort in Java](https://stackabuse.com/merge-sort-in-java/))

public static void merge(int[] array, int low, int mid, int high)
{
    // Definition der Unterarrays
    int leftArray[] = new int[mid - low + 1];
    int rightArray[] = new int[high - mid];
    // Einfügen der Werte aus array
    for (int i = 0; i < leftArray.length; i++)
        leftArray[i] = array[low + i];
    for (int i = 0; i < rightArray.length; i++)
        rightArray[i] = array[mid + i + 1];
    // Definition der Indexzähler
    int leftIndex = 0;
    int rightIndex = 0;

    // Schreiben aus leftArray und rightArray in array
    for (int i = low; i < high + 1; i++) 
    {
        // Wenn noch unsortierte Elemente in beiden Subarrays vorhanden sind
        if (leftIndex < leftArray.length && rightIndex < rightArray.length)
        {
            if (leftArray[leftIndex] < rightArray[rightIndex]) 
            {
               array[i] = leftArray[leftIndex];
               leftIndex++;
            } else {
                array[i] = rightArray[rightIndex];
                rightIndex++;
            }
        } else if (leftIndex < leftArray.length) 
        {
            // Wenn kein Element mehr in rightArray, 
            // schreibe verbleibende Elemente aus leftArray
            array[i] = leftArray[leftIndex];
            leftIndex++;
        } else if (rightIndex < rightArray.length) 
        {
            // Wenn kein Element mehr in leftArray, 
            // schreibe verbleibende Elemente aus rightArray
            array[i] = rightArray[rightIndex];
            rightIndex++;
        }
    }
}

public static void mergeSort(int[] array, int low, int high) 
{
    // Abbruch, falls nicht weiter sortierbar
    if (high <= low) return;
    // Ermittlung der Mitte des Arrays
    int mid = (low+high)/2;
    // Rekursiver Aufruf des linken Teils inkl. mid
    mergeSort(array, low, mid);
    // Rekursiver Aufruf des rechten Teils ohne mid
    mergeSort(array, mid+1, high);
    // Mergen von array
    merge(array, low, mid, high);
}

## Heap-Sort

**Erklärung**
Der Heapsort sortiert Folgen anhand der Erstellung von sogenannten heap- und maxheap-trees. Hierzu wird die gegebene Folge als Binär-Baum dargestellt (heap-tree) und anschließend das maximale Element an die Spitze in diesem Baum sortiert (maxheap). Jenes maximales Element wird darauf folgend in der Folge an die letzte Stelle gesetzt und als sortiert betrachtet. Entsprechend ändert sich der heap-tree, aus welchem nun das zuvor sortierte Element entfernt wird. Folglich muss der tree erneut nach dem maximalen Element sortiert werden. Diese Abfolge wird bis zur vollständigen Sortierung der Folge wiederholt. (vgl. [Heap Sort - Erklärung](https://www.youtube.com/watch?v=oJY1FFvLCJA))

Gegeben sei die Folge [78, 14, 66, 2, 67, 5, 3, 35]

1. Schritt: Erstellung heap-tree

digraph HeapsortSchritt1 {
    78 -> 14
    78 -> 66
    14 -> 2
    14 -> 67
    66 -> 5
    66 -> 3
    2 -> 35
}

2. Schritt: Erstellen maxheap ("heapify")
Sortieren der parent- und child-elemente nach ihrer Größe von links beginnend

digraph HeapsortSchritt2 {
    78 -> 67
    78 -> 66
    67 -> 35
    67 -> 14
    66 -> 5
    66 -> 3
    35 -> 2 
}

35>2, tausche 35 mit 2 | [78, 14, 66, 35, 67, 5, 3, 2]
67>35>14, tausche 67 mit 14 | [78, 67, 66, 35, 14, 5, 3, 2]
5<66 && 3<66, kein Tausch notwendig | [78, 67, 66, 35, 14, 5, 3, 2]
maxheap hergestellt.

3. Schritt: Tausche maximales Element mit dem letzten Element der Folge.

digraph HeapsortSchritt3 {
    2 -> 67
    2 -> 66
    67 -> 35
    67 -> 14
    66 -> 5
    66 -> 3 
}

[2, 67, 66, 35, 14, 5, 3, 78]
Erstes Element sortiert. Lösche sortiertes Element aus dem Baum.

4. Schritt: heapify

digraph HeapsortSchritt4 {
    67 -> 35
    67 -> 66
    35 -> 2
    35 -> 14
    66 -> 5
    66 -> 3
}

67>66>2, tausche 67 mit 2 | [67, 2, 66, 35, 14, 5, 3, 78]
35>14>2, tausche 35 mit 2 | [67, 35, 66, 2, 14, 5, 3, 78]
5<66 && 3<66, kein Tausch notwendig | [67, 35, 66, 2, 14, 5, 3, 78]

5. Schritt: maximales Element sortieren und löschen

digraph HeapsortSchritt5 {
    3 -> 35
    3 -> 66
    35 -> 2
    35 -> 14
    66 -> 5
}

Tausche 67 mit 3 [3, 35, 66, 2, 14, 5, 67, 78]

6. Schritt: heapify

digraph HeapsortSchritt6 {
    66 -> 35
    66 -> 5
    35 -> 2
    35 -> 14
    5 -> 3
}

66>35>3, tausche 66 mit 3 | [66, 35, 3, 2, 14, 5, 67, 78]
2<35 && 14<35, kein Tausch notwendig | [66, 35, 3, 2, 14, 5, 67, 78]
5>3, tausche 5 mit 3 [66, 35, 5, 2, 14, 3, 67, 78]

7. Schritt: maximales Element sortieren und löschen

digraph HeapsortSchritt7 {
    3 -> 35
    3 -> 5
    35 -> 2
    35 -> 14
}

Tausche 66 mit 3 | [3, 35, 5, 2, 14, 66, 67, 78]

8. Schritt: heapify

digraph HeapsortSchritt8 {
    35 -> 14
    35 -> 5
    14 -> 2
    14 -> 3
}

35>5>3, tausche 35 mit 3 | [35, 3, 5, 2, 14, 66, 67, 78]
14>3>2, tausche 14 mit 3 | [35, 14, 5, 2, 3, 66, 67, 78]
5<35, kein Tausch notwendig |[35, 14, 5, 2, 3, 66, 67, 78]

9. Schritt: maximales Element sortieren und löschen

digraph HeapsortSchritt9 {
    3 -> 14
    3 -> 5
    14 -> 2
}

Tausche 35 mit 3 | [3, 14, 5, 2, 35, 66, 67, 78]

10. Schritt: heapify

digraph HeapsortSchritt10 {
    14 -> 3
    14 -> 5
    3 -> 2
}

14>5>3, tausche 14 mit 3 | [14, 3, 5, 2, 35, 66, 67, 78]
2<3, kein Tausch notwendig | [14, 3, 5, 2, 35, 66, 67, 78]

11. Schritt: maximales Element sortieren und löschen

digraph HeapsortSchritt11 {
    2 -> 3
    2 -> 5
}

Tausche 14 mit 2 | [2, 3, 5, 14, 35, 66, 67, 78]

12. Schritt: heapify

digraph HeapsortSchritt12 {
    5 -> 3
    5 -> 2
}

5>3>2, tausche 5 mit 2 | [5, 3, 2, 14, 35, 66, 67, 78]

13. Schritt: maximales Element sortieren und löschen

digraph HeapsortSchritt14 {
    2 -> 3
}

Tausche 5 mit 2 | [2, 3, 5, 14, 35, 66, 67, 78]

14. Schritt: heapify

digraph HeapsortSchritt14 {
    3 -> 2
}

3>2, tausche 3 mit 2 | [3, 2, 5, 14, 35, 66, 67, 78]

15. Schritt: maximales Element sortieren und löschen

digraph HeapsortSchritt15 {
    2
}

Tausche 3 mit 2 | [2, 3, 5, 14, 35, 66, 67, 78]
2 verbleibt als letztes Element.
Folge sortiert.

**Darstellung in Java** (vgl. [HeapSort](https://www.geeksforgeeks.org/heap-sort/))

public class HeapSort 
{
    public void sort(int arr[])
    {
        int n = arr.length;
        // Heap tree erstellen 
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        // Analysiere jedes Element einzeln
        for (int i = n - 1; i > 0; i--) 
        {
            // Verschieben der Wurzel (größtes Element)
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // Heapify ohne die alte Wurzel
            heapify(arr, i, 0);
        }
    }
    // Heapify eines trees mit Größe n und dem Wurzelknoten i, 
    // welcher einen Index in arr[] ist
    void heapify(int arr[], int n, int i)
    {
        int largest = i; // Wurzel ist initial das größte Element
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2
 
        // Wenn der linke Kindknoten größer als die Wurzel ist
        if (l < n && arr[l] > arr[largest])
            largest = l;
        // Wenn der rechte Kindknoten größer als der bisher größte Wert ist
        if (r < n && arr[r] > arr[largest])
            largest = r;
        // Wenn größtes Element != Wurzel, dann tausche deren Position
        if (largest != i) 
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            // Rekursiver Aufruf für den vom Tausch betroffenen Subtree
            heapify(arr, n, largest);
        }
    }
}

## Quicksort

**Erklärung**

Die Grundidee des Quick Sortierens besteht darin, die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile zu teilen, und alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil, und dann die beiden Teile schnell zu sortieren Daten nach diesem Verfahren. , kann der gesamte Sortierprozess rekursiv durchgeführt werden, so dass die gesamten Daten zu einer geordneten Folge werden.

[Ich bin Video von Quicksort](https://www.youtube.com/watch?v=Hoixgm4-P4M)

------------------------------------------------
1. Schritt: {1, 9, 0, 2, 4, 3} Ausgangssituation, definieren wir eine Anfangposition=-1;

2. Schritt: {1, 9, 0, 2, 4, 3} Zahlen zwischen 3(letzte Position) und 1(Position 0) vergleichen, 1<3,deswegen lasse Anfangposition++ mit die Position von Zahl 1(Position 0) wechseln, also wechseln wir Position 0 mit Position 0, deswegen Zahl 1 ist immer noch in Position 0;

3. Schritt: {1, 9, 0, 2, 4, 3} Zahlen zwischen 3(letzte Position) und 9(Position 1) vergleichen, 9>3,deswegen bleibt Zahl 9 so, soll seine Position nicht gewechselt werden.

4. Schritt: {1, 0, 9, 2, 4, 3} Zahlen zwischen 3(letzte Position) und 0(Position 2) vergleichen, 0<3,deswegen lasse Anfangposition++(Anfangposition=0+1=1) mit die Position von Zahl 0(Position 2) wechseln, also wechseln wir Position 1 mit Position 2, deswegen Zahl 0 ist jetzt in Position 1;

5. Schritt: {1, 0, 2, 9, 4, 3} Zahlen zwischen 3(letzte Position) und 2(Position 3) vergleichen, 2<3,deswegen lasse Anfangposition++(Anfangposition=1+1=2) mit die Position von Zahl 2(Position 3) wechseln, also wechseln wir Position 2 mit Position 3, deswegen Zahl 2 ist jetzt in Position 2;

6. Schritt: {1, 0, 2, 9, 4, 3} Zahlen zwischen 3(letzte Position) und 4(Position 4) vergleichen, 4>3,deswegen bleibt Zahl 4 so, soll seine Position nicht gewechselt werden.

7. Schritt: {1, 0, 2, 3, 9, 4} Zahlen 3 von letzten Position haben schon mit alle Zahlen verglichen,nun ist Anfangposition in der Position 2, d.h die Zahlen vor Anfangposition+1(Position 3)immer kleiner als 3, deswegen jetzt wechseln wir die Positionen zwischen letzte Position und Anfangosition+1;Dann ist Zahl 3 in Position 3, alle Zahlen vor 3 sind immer kleiner als 3, und alle Zahlen nachdem 3 sind immer groesserer als 3.

8. Schritt: {1, 0, 2, 3, 4, 9} Nehmen Sie die Position der Zahl 3 als Grenze, und die Zahlen vor 3 und nach 3 werden gleichzeitig sortiert.Also muss man gleichzeitig {1, 0, 2}und{4,9} wie oben genannte Methode sortieren.

9. Schritt: {0, 1, 2, 3, 4, 9} :+1:

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

	int[] a = {1, 9, 0, 2, 4, 3};
	System.out.println(Arrays.toString(a));
	quicksort(a, 0, a.length - 1);
	System.out.println(Arrays.toString(a));
	}
    
	public static void quicksort( int[] a, int p, int r ){
        
	if (p<r){
    // siehe (6)  
	int q = partition( a, p, r ); 
	quicksort(a, p, q-1);
	quicksort(a, q+1, r);
    // siehe (7)   
	}
	}
    
	public static int partition(int []a, int p, int r){
        
	int x = a[r];
	int i = p - 1;
 // siehe (2)       
	for (int j = p; j < r; ++j){
// siehe (3)
	if (a[j] <= x){
        
	i++;
	swap(a, i, j);
// siehe (4)

        
	}
	}
        
	swap (a, i+1, r);
        
	return i+1;
// siehe (5)
        
	}
    
	public static void swap( int[] a, int i, int j ){
        
	int aux = 0;
	aux = a[i];
	a[i] = a[j];
	a[j] = aux;
        
// siehe (1)
        
}
}

:::spoiler Erläuterung von ZL

/* (1)
* Lassen Sie uns zuerst eine Swap-Methode schreiben, um zwei Zielzahlen in Position i und Position j spaeter zu tauschen.

*/

/* (2)
* Der Zweck der Partitionsmethode besteht darin, die letzte Zahl im Array zu unterteilen : ein ganz Array in 2 Arrays zu unterteilen, einer mit die Zahlen größer als die letzte Zahl und anderer mit der Zahlen kleiner als die letzte Zahl sind.
* Parameter p ist erste Zahl von Zielarray, r ist letzt Zahl von Zielarray.wie oben gesagt, muessen wir immer eine Anfangposition difinieren, hier ist Anfangposition i,die ist immer eine Position vor erste Zahl eines Arrays.
* i<r,weil a[r] darf nicht mit sich selbst vergleichen.
*/

/* (3)
* hier definieren wir ein Forschleife mit Parameter j, j beginnt immer mit erste Zahl von Array,hier hat man j=p definiert aber nicht j=0,weil jist nicht immer =0.z.B wenn man moechte spaeter Teil-Array von Position 3 bis letzte dieses Arrays sortiren, dann ist j=3.

*/

/* (4)
* if (a[j] <= x) hier bedeutet, wenn Zahl in Position j nun groesserer gleich als letzt Zahl,dann muss Anfangposition i plus 1. z.B a[0]=1,k=5,x=a[k]=3,1<3, deswegen i=i+1, jetzt ist i=-1+1=0,und wechseln wir jetzt Position von 0 mit i(i=0) mit swap(a,0,0), dann bleibt Position 0 noch wie vorher. a[1]>3, deswegen bleibt a[1] in seiner Position. aber wenn z.B a[2]=0,a[2]<3, deswegen i++, jetzt ist i=1, dann muessen wir mit swap(a,1,2) die Position von i und Position 2 wechseln.Bis jetzt sieht Array so aus:{1, 0, 9, 2, 4, 3}.

*/

/* (5)
* wenn a[k] hat mit allen Zahlen von Array a verglichen, dann ist i in der Position letzt Zahl, die kleiner als a[k] ist.Alle Zahl nachdem Position i sind groesserer als a[k],deswegen wechseln wir jetzt Position k mit Position i+1 mit swap(a,k,i+1), und jetzt ist Position i+1 die Grenze von Array. Alle Zahlen vor Position i+1 sind kleiner als a[k],und alle Zahlen nachdem i+1 sind groesserer als a[k].
*/

/* (6)
* wenn p<r werde die Rekursiv beenden.(weil z.B es geht nicht wenn die erste Position 2 aber die letzte Position 0 ist.
*/

/* (7)
* wenn p<r werde die Rekursiv beenden.(weil z.B es geht nicht wenn die erste Position 2 aber die letzte Position 0 ist.
* q ist um eine Grenze von Array zu herrausfinden. z.B {1, 9, 0, 2, 4, 3} nachdem in Methode partition laufen ist Grenze 3 in Position 3: {1, 0, 2, 3, 9, 4}.Weil alle Zahlen vor 3 sind kleiner als 3,und alle nach 3 sind groesserer als 3, deswegen jetzt rufen wir gleichzeitig rekursiv "quicksort", um {1,0,2}und {9,4} zu sortieren.
*/

:::

## Rekursiv

**Erklärung**

* Gucken Sie bitte diese Vedio, bevor Sie die Aufgabe loesen :
[ich bin Vedio](https://www.youtube.com/watch?v=weTpjhDnLnc)

public class Rekursiv {
  
	public static int rekursiv(int a,int b) {

		int sum =0;

		if(a==b) {
	 		sum= a;
 // siehe (1)
		}

		else if(a>b) {
			sum=rekursiv(a-b,b);
 // siehe (2)            
		}

		else {
			sum=rekursiv(a,b-a);
 // siehe (3)
		}

		return sum;
	}
   
  }

:::spoiler Erläuterung von ZL

Wichtig: Eine rekursive Kopie besteht darin, dieselbe Methode so lange zu wiederholen, bis wir das gewünschte Ergebnis gefunden haben.

/* (1)
* Wir definieren zuerst ein Attribut:sum vom Typ int. Wenn Variable a = Variable b, dann setzen wir sum gleich a oder b und geben den Wert von sum zurück.

*/

/* (2)
* Wenn a>b, dann führe die rekursiv-Methode mit neue Variable(a-b,b) erneut aus.
*/

/* (3)

* Wenn a>b, dann führe die rekursiv-Methode mit neue Variable(a,b-a) erneut aus.

*/

:::

:::spoiler Idee/Vorschläge
Idee RM (für alle Verfahren):
* Spielkarten für Visualisierung nutzen
* [Vorlagen hier unter CC0](https://commons.wikimedia.org/wiki/File:English_pattern_playing_cards_deck.svg)
:::

:::info
**Autoren**
* Z. Li (InsertSort, Bubblesort, Erläuterungen "von ZL")
* N. Greb (Korrekturen)
* R. Meiner (Organisation, Korrekturen, )

Dieser Text steht unter CC-0 (TODO: Link zur Lizenz)
:::