Partition

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Partition ordnet das Teilarray so, dass links Elemente <= Pivot und rechts Elemente >= Pivot liegen (Varianten differieren in Details). Der Pivot landet an seiner finalen Position.

Lomuto und Hoare sind gängige Schemata.

Wo gebraucht

Kern von Quicksort und von Selection (Quickselect). Dieselbe Idee steckt in Dutch-National-Flag-Partitionen und in In-Place-Umordnungen.

Vertiefung

Eine Partition ordnet einen Bereich so um, dass Werte auf verschiedenen Seiten eine Relation zum Pivot erfüllen. Lomuto führt typischerweise eine Grenze für den kleineren Bereich und einen Scanindex. Hoare bewegt zwei Zeiger von aussen nach innen und tauscht falsch liegende Paare.

Die Rückgabe hat je nach Schema eine andere Bedeutung. Bei Lomuto ist sie häufig eine Pivotposition, bei Hoare meist eine Trennstelle für zwei weitere Intervalle. Korrekte Rekursionsgrenzen müssen daher aus dem verwendeten Schema folgen und dürfen nicht zwischen Varianten gemischt werden.

Schwierigkeitsstufen

Die Bereichsinvarianten eines Partitionsschemas verfolgen.
Rückgabewert und rekursive Intervalle passend kombinieren.
Verhalten bei vielen Werten gleich dem Pivot analysieren.

Fallstricke

Viele Quicksortfehler entstehen nicht im Vergleich, sondern durch inkonsistente Intervallkonventionen. Inklusive und exklusive Grenzen dürfen innerhalb einer Implementierung nicht unbemerkt wechseln.

University approvals: 0

Tasks

Question 1

Wo steht das Pivot nach einer korrekten Partition?

Immer am Index 0

An seiner endgültigen Sortierposition im Teilarray

Nur auf dem Heap

Ausserhalb des Arrays

Question 2

Warum dürfen Hoare- und Lomuto-Rekursionsgrenzen nicht beliebig ausgetauscht werden?

Beide Verfahren verwenden grundsätzlich verschiedene Datentypen.

Ihre Rückgabewerte beschreiben unterschiedliche Grenzen des partitionierten Bereichs.

Hoare darf nur gerade Arraylängen verarbeiten.

Lomuto benötigt immer ein bereits sortiertes Array.

Question 3

Implementiere die Lomuto-Partition mit a[hi] als Pivot und gib dessen endgültigen Index zurück.

Hint

Das Pivot kann in einer lokalen int-Variable gespeichert werden. Zum Tauschen zweier Arrayelemente genügt eine temporäre Variable.

class Lomuto {
  static int partition(int[] a, int lo, int hi) {
    // TODO
    return lo;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy