Quicksort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
K (Akaibel verschob Seite Quicksort ab Abi 2017 nach Quicksort)
 
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 9: Zeile 9:


<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
=Fachbegriffe=
rekursiv, Divide-Conquer-Prinzip, Pivot-Element, Abbruchbedingung, Laufzeit


=Prinzip=
=Prinzip=
Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':
Quicksort arbeitet nach dem '''Divide-and-Conquer-Prinzip''':


Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt (='''Divide'''). Dazu wählt Quicksort ein sogenanntes '''Pivotelement''' aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt (='''Divide'''). Dazu wählt Quicksort ein sogenanntes '''Pivotelement''' aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.


Anschließend wird jede Teilliste in sich sortiert. Dazu wird der Quicksort-Algorithmus '''rekursiv''' auf der linken und auf der rechten Teilliste ausgeführt. Wenn eine Teilliste leer ist, erfolgt der Abbruch der Rekursion, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.
Anschließend wird jede Teilliste in sich sortiert, indem der Quicksort-Algorithmus '''rekursiv''' auf die linke und die rechte Teilliste angewendet werden. Wenn eine Teilliste nur ein oder kein Element enthält, bricht die Rekursion ab, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.


Am Ende werden die beiden Teillisten und das Pivot-Element zusammengeführt (='''Conquer''').
Am Ende werden die beiden Teillisten und das Pivot-Element zusammengeführt (='''Conquer''').
Zeile 34: Zeile 39:




<code>
<code>
  public List<Person> quicksort(List<Person> pList){
    public List<Person> quicksort(List<Person> pList){
    if(pList.isEmpty()){
          '''// leere Ergebnis-Liste erzeugen'''
      return pList;
          List<Person> ergebnis = new ListWithViewer<Person>();
    }
          '''// Abbruchbedingung für die leere Liste'''
    pList.toFirst();
          if(pList.isEmpty()){
    Person pivot = pList.getContent();
            return ergebnis;
    pList.next();
          }
    if(!pList.hasAccess()){
          '''// das erste Element der Liste als Pivot-Element festlegen'''
      return pList;
          pList.toFirst();
    }
          Person pivot = pList.getContent();
    List<Person> kleiner = new List<>();
          '''// zum nächsten Element gehen'''
    List<Person> groesser = new List<>();
          pList.next();
    while(pList.hasAccess()){
          '''// die Listen links und rechts als leere Listen erzeugen
      Person aktuell = pList.getContent();
          List<Person> links = new List<Person>();
      if(aktuell.getEinkommen() < pivot.getEinkommen()){
          List<Person> rechts = new List<Person>();
        kleiner.append(aktuell);
          '''// pList durchlaufen und die Elemente mit pivot vergleichen:'''
      }
          '''// kleinere kommen nach links, die anderen nach rechts.'''
      else{
          while(pList.hasAccess()){
        groesser.append(aktuell);
            Person p = pList.getContent();
      }
            if(p.getEinkommen() < pivot.getEinkommen()){
      pList.next();
              links.append(p);
    }
            }
    List<Person> kleinerSortiert = quicksort(kleiner);
            else{
    List<Person> groesserSortiert = quicksort(groesser);
              rechts.append(p);
            }
    List<Person> ergebnis = new ListWithViewer<>();
            pList.next();
    ergebnis.concat(kleinerSortiert);
          }
    ergebnis.append(pivot);
          '''// rekursive Aufrufe von quicksort für links und rechts'''
    ergebnis.concat(groesserSortiert);
          List<Person> linksSortiert = quicksort(links);
    return ergebnis;
          List<Person> rechtsSortiert = quicksort(rechts);
  }
          '''// die sortierten Teillisten und das Pivot-Element'''
</code>
          '''// in der richtigen Reihenfolge an ergebnis anhängen'''
 
          ergebnis.concat(linksSortiert);
== für Arrays ==
          ergebnis.append(pivot);
Auf Arrays ist Quicksort schneller, weil man "in situ" sortiert, d.h. es werden keine Teilarrays o.ä. erzeugt.
          ergebnis.concat(rechtsSortiert);
 
          '''// die ergebnis-Liste zurückgeben'''
Dafür ist diese Implementierung komplizierter.
          return ergebnis;
 
         }     
<code>
</code>
  //Rahmenmethode
  <b>public void quicksort(Person[] personen){</b>
      quicksort(personen, 0, personen.length-1);
  }
 
  // rekursive Methode
  <b>private void quicksort(Person[] personen, int start, int ende){</b>
      if(start == ende){
        return;
      }
      if(start + 1 == ende){
        if(personen[start].istAlphabetischNach(personen[ende])){
            tausche(personen, start, ende);
            return;
        }
      }
      Person pivot = personen[start];
      int vomStart = start+1;
      int vomEnde = ende;
      while(vomStart < vomEnde){
        while(vomStart < vomEnde && personen[vomStart].istAlphabetischNach(pivot) == false){
            vomStart++;
        }
        while(vomStart < vomEnde && personen[vomEnde].istAlphabetischNach(pivot)){
            vomEnde--;
        }
        tausche(personen, vomStart, vomEnde);
      }
      // pivot-Element in die Mitte bringen
      tausche(personen, start, vomStart-1);
      if(start < vomStart-1){
        quicksort(personen, start, vomStart-1);
      }
      if(vomStart < ende){
         quicksort(personen, vomStart, ende);
      }
      return;
   }
</code>

Aktuelle Version vom 23. Januar 2022, 16:52 Uhr

Quicksort für das Wort "informatik"

im Zentralabitur nur relevant für den LK!


Diese Seite entspricht dem Abi 17 (und folgenden)

Fachbegriffe

rekursiv, Divide-Conquer-Prinzip, Pivot-Element, Abbruchbedingung, Laufzeit

Prinzip

Quicksort arbeitet nach dem Divide-and-Conquer-Prinzip:

Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt (=Divide). Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

Anschließend wird jede Teilliste in sich sortiert, indem der Quicksort-Algorithmus rekursiv auf die linke und die rechte Teilliste angewendet werden. Wenn eine Teilliste nur ein oder kein Element enthält, bricht die Rekursion ab, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.

Am Ende werden die beiden Teillisten und das Pivot-Element zusammengeführt (=Conquer).

Laufzeit

Quicksort hat im Average Case die Laufzeit O(n*log(n)). Im Worst Case steigt die Laufzeit auf O(n2).
Da der Worst Case nur für Listen (bzw. Arrays) eintritt, die schon sortiert sind, kann man den Worst Case ganz einfach vermeiden: Man muss vor dem Aufruf von Quicksort die Elemente mischen!

Quicksort ist das schnellste vergleichsbasierte Sortierverfahren. Das liegt daran, dass es für Arrays in situ sortiert, d.h. es müssen keine neuen Datenstrukturen erzeugt werden. Das ist der entscheidende Vorteil von Quicksort gegenüber Mergesort.

Implementierung

für Listen

Quicksort-Implementierung für eine Liste (vgl. Schnittstellenbeschreibung Zentralabitur), die mit Objekten vom Typ Person gefüllt ist.

Diese Implementierung ist einfacher als die Array-Implementierung, dafür aber nicht so schnell, denn man muss ständig neue Listen erzeugen.



   public List<Person> quicksort(List<Person> pList){
          // leere Ergebnis-Liste erzeugen
          List<Person> ergebnis = new ListWithViewer<Person>();
          // Abbruchbedingung für die leere Liste
          if(pList.isEmpty()){
            return ergebnis;
          }
          // das erste Element der Liste als Pivot-Element festlegen
          pList.toFirst();
          Person pivot = pList.getContent();
          // zum nächsten Element gehen
          pList.next();
          // die Listen links und rechts als leere Listen erzeugen
          List<Person> links = new List<Person>();
          List<Person> rechts = new List<Person>();
          // pList durchlaufen und die Elemente mit pivot vergleichen:
          // kleinere kommen nach links, die anderen nach rechts.
          while(pList.hasAccess()){
            Person p = pList.getContent();
            if(p.getEinkommen() < pivot.getEinkommen()){
              links.append(p);
            }
            else{
              rechts.append(p);
            }
            pList.next();
          }
          // rekursive Aufrufe von quicksort für links und rechts
          List<Person> linksSortiert = quicksort(links);
          List<Person> rechtsSortiert = quicksort(rechts);
          // die sortierten Teillisten und das Pivot-Element
          // in der richtigen Reihenfolge an ergebnis anhängen
          ergebnis.concat(linksSortiert);
          ergebnis.append(pivot);
          ergebnis.concat(rechtsSortiert);
          // die ergebnis-Liste zurückgeben
          return ergebnis;
        }