Algorithmen - Sortierverfahren - QuickSort

 InsertionSort  BubbleSort SelectionSort QuickSort

Die Liste wird in zwei Teillisten getrennt. Als Trennstelle dient ein Pivot-Element. Elemente welche kleiner als das Pivot-Element sind wandern in die linke Teilliste, alle anderen in die rechte Teilliste. Der Quicksort-Algorithmus wird nun (rekursiv) auf diese beiden Teillisten angewendet


 Aufgabe:
Bei jedem Aufruf der Rekursion haben die Elemente im Array eine neue Reihenfolge, bis schließlich der oberste Prozeduraufruf abgearbeitet und alle Elemente sortiert sind. Bestimme die Elementreihenfolge nach jedem Eintritt in die rekursive Prozedur.
 
Pseudo-Code:

qSort(F, 0, length(F))

function qSort(F,first,last)
  if(last<first)
    return F
  pivot=first
  mid=first
  for(i=first+1 to i <= last)
    if(F[i] < F[pivot])
      mid = mid + 1
      swap(F[i],F[mid])
  swap(F[mid],F[pivot])
  F = qSort(F,first,mid-1)
  F = qSort(F,mid+1,last)
  return F

  

 

Download
Nutzen Sie die Sortieralgorithmen-Übungsgeneratoren offline
oder bauen Sie diese in Ihre Schulungsunterlagen ein: sort.zip (10 KB)

***

©2004 WW-Anwendungsentwicklung