Quick Sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Introduction
As its name implies, quicksort is the fastest known sorting algorithm in practice. Its average running time is O(n log n). It is very fast, mainly due to a very tight and highly optimized inner loop.Quicksort is a divide-et-impera method for sorting. It works by partitioning an array into two parts, then sorting the parts independently.
[edit] Pseudocode
Quicksort(A,p,r) {
if (p < r) {
q <- Partition(A,p,r)
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r) {
x <- A[p]
i <- p-1
j <- r+1
while (True) {
repeat
j <- j-1
until (A[j] <= x)
repeat
i <- i+1
until (A[i] >= x)
if (i<-> A[j])
else
return(j)
}
}
[edit] C Code
#include <stdio.h>
void swap(int l[], int i, int j)
{ int dummy;
dummy=l[j];
l[j]=l[i];
l[i]=dummy;
}
int partions(int l[],int low,int high)
{
int prvotkey=l[low];
while (low<high)
{
while (low<high && l[high]>=prvotkey)
--high;
swap(l,high,low);
while (low<high && l[low]<=prvotkey)
++low;
swap(l,high,low);
}
return low;
}
void qsort(int l[],int low,int high)
{
int prvotloc;
if(low<high)
{
prvotloc=partions(l,low,high);
qsort(l,low,prvotloc);
qsort(l,prvotloc+1,high);
}
}
void quicksort(int l[],int n)
{
qsort(l,0,n);
}
void main()
{
int a[11]={103,2,32,43,23,45,36,57,14,27,39};
int b,c;
for (b=0;b<=10;b++)
printf("%3d ",a[b]);
printf("\n");
quicksort(a,10);
for(c=0;c<=10;c++)
printf("%3d ",a[c]);
}
[edit] PHP Code
function quick_sort($array){
if (count($array) <= 1) return $array;
$key = $array[0];
$left_arr = array();
$right_arr = array();
for ($i=1; $i<count($array); $i++){
if ($array[$i] <= $key)
$left_arr[] = $array[$i];
else
$right_arr[] = $array[$i];
}
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
return array_merge($left_arr, array($key), $right_arr);
}
Fail. That is a mergesort.
[edit] C++ Code
[edit] Recursive
#undef SORT_MAX
#define SORT_MAX 150
template <typename Type> inline
void Quick(Type *pF, Type *pL)
{
if (pL-pF <= SORT_MAX) { // partial insertion sorting
Insertion(pF, pL); // because of stack overflow
} else {
Type *pM = Partition(pF, pL, GetPivot(pF, pL));
Quick(pF, pM);
Quick(pM, pL);
}
}
template <typename Type> inline
Type *Partition(Type *pF, Type *pL, Type pivot)
{
for (pF--; ;) {
while (*(++pF) < pivot);
while (*(--pL) > pivot);
if (pF>=pL) { return pF; }
std::iter_swap(pF, pL); // #include <algorithm>
}
}
template <typename Type> inline
Type GetPivot(Type *pF, Type *pL)
{
return GetMedian(Type(*pF), Type(*(pF+(pL-pF)/2)), Type(*(pL-1))); // using first, mid and last
}
template <typename Type> inline
Type GetMedian(Type x, Type y, Type z)
{
if (x < y) { return (y < z ? y : x < z ? z : x); }
else { return (x < z ? x : y < z ? z : y); }
}
[edit] Loop (using user's stack)
//////////////////////////// 사용자 스택을 이용한 반복문으로 빠른 정렬 구현
#undef SORT_MAX
#define SORT_MAX 150 // (many : 100~200, a few : 5~25)
template <typename Type> inline
void Quick_Loop(Type *pF, Type *pL)
{
std::stack<Type *> pBuf; // #include <stack>
do {
if (pL-pF <= SORT_MAX) {
Insertion(pF, pL);
} else {
Type *pM = Partition(pF, pL, GetPivot(pF, pL));
pBuf.push(pM); pBuf.push(pL); // [pM, pL)
pBuf.push(pF); pBuf.push(pM); // [pF, pM)
}
if (pBuf.empty()) { break; }
pL = pBuf.top(); pBuf.pop();
pF = pBuf.top(); pBuf.pop();
} while (1);
}
#undef SORT_MAX
[edit] C# 3.0 Code
The algorithm applies to every generic index-based list, inclusively arrays.
using System;
using System.Collections.Generic;
public static class Sorter <T> where T : IComparable
{
private static void QuickSort(IList<T> list, int left, int right)
{
if (left < right)
{
T pivotElement = list[right];
int i = left - 1;
int j = right + 1;
//Search for the biggest item left to the pivot element and for
//the smallest item right to the pivot element and exchange both.
while (i <= j)
{
do { i++; } while (i <= j && IsSmaller(list[i], pivotElement));
do { j--; } while (i <= j && IsBigger (list[j], pivotElement));
if (i < j) Exchange(list, i, j);
}
QuickSort(list, left, j);
QuickSort(list, i, right);
}
}
}
Exchange method:
private static void Exchange(IList<T> list, int index1, int index2)
{
T tmp = list[index1];
list[index1] = list[index2];
list[index2] = tmp;
}
The comparing methods:
private static bool IsSmaller(T item1, T item2)
{
return item1.CompareTo(item2) < 0;
}
private static bool IsBigger(T item1, T item2)
{
return item1.CompareTo(item2) > 0;
}
[edit] Another C# Code
void Quicksort(int[] v, int prim, int ult) {
if (prim < ult)
{
/* Selecciona un elemento del vector y coloca los menores
que él a su izquierda y los mayores a su derecha */
int p = Pivote(v, prim, ult, ult);
/* Repite el proceso para cada una de las
particiones generadas en el paso anterior */
Quicksort(v, prim, p - 1);
Quicksort(v, p + 1, ult);
}
}
/* Implementación no clásica de la función Pivote. En lugar de recorrer el vector simultáneamente desde ambos extremos hasta el cruce de índices, se recorre desde el comienzo hasta el final */ int Pivote(int[] v, int prim, int ult, int piv) {
int p = v[piv];
int j = prim;
// Mueve el pivote a la última posición del vector
Intercambia(v, piv, ult);
/* Recorre el vector moviendo los elementos menores
o iguales que el pivote al comienzo del mismo */
for (int i = prim; i < ult; i++)
{
if (v[i] <= p)
{
Intercambia(v, i, j);
j++;
}
}
// Mueve el pivote a la posición que le corresponde
Intercambia(v, j, ult);
return j;
}
void Intercambia(int[] v, int a, int b) {
if (a != b)
{
int tmp = v[a];
v[a] = v[b];
v[b] = tmp;
}
}
[edit] Java 6 Code
public int [] quickSort(int[] array, int anfang, int ende){
if (ende> anfang){
int pivot = anfang;
int mitte = anfang;
for (int i=anfang+1; i<= ende; i++){
if (array[i]< array[pivot]){
mitte++;
swap(array, i, mitte);
}
}
swap(array, pivot, mitte);
array= quickSort(array, mitte+1, ende);
array =quickSort(array, anfang, mitte-1);
}
return array;
}
private void swap(int[] result, int a, int b){
int temp = result[a];
result[a] = result[b];
result[b] = temp;
}
[edit] Java Code
static void sort(int a[], int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
if (lo >= hi) {
return;
}
int mid = a[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && a[lo] < mid) {
lo++;
}
while (lo<hi && a[hi] >= mid) {
hi--;
}
if (lo < hi) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
sort(a, lo0, lo);
sort(a, lo == lo0 ? lo+1 : lo, hi0);
}
static void sort(int a[]) {
sort(a, 0, a.length-1);
}
[edit] Delphi/Pascal Code
unit Unit2;
// INFO QuickSort zum Sortieren eines Array of Records oder Arrays
// INFO bzw. zum Sortieren einer "Tabelle"/"Matrix" nach einer Spalte
// INFO Aufruf erfolg mit quicksort(ARRAYbezeichung,Sortierrichtung)
// INFO Bei TRUE wird aufsteigend a..z und bei FALSE absteigend z..a sortiert
// VORRAUSSETZUNG es muss einen Datentyp vom Typ 'TMyArrayOne' geben !
// VORRAUSSETZUNG dieser kann ein "ARRAY of Records" oder "ARRAY of ARRAYs of 'DatentypXY'" sein
// VORRAUSSETZUNG ES MÜSSEN ZWEI STELLEN IM CODE ANGEPASST WERDEN, DIESE BEREICHE SIND DURCH --> GEKENNZEICHENT
// VORRAUSSETZUNG Das ist zueinem die Angabe der Spalte, nach der sortiert werden soll.
// VORRAUSSETZUNG Und zum anderen die Verknüpfung mit der Unit wo der Datentyp 'TMyArrayOne' deklariert wurde
interface
uses
// --> Wo ist Datentyp 'TMyArrayOne' deklariert ???
Unit1;
var aSortVergleich: array of Variant;
procedure quicksort(var aUn2SortDaten0: TMyArrayOne; bSortierrichtung0:boolean);
procedure quicksort_teil_a(var aUn2SortDaten1: TMyArrayOne; iLinksP1,iRechtsP1:integer);
function quicksort_teil_b(var aUn2SortDaten2: TMyArrayOne; iLinksP2,iRechtsP2:integer):integer;
procedure quicksort_teil_c(var aUn2SortDaten3: TMyArrayOne; iDatensatzzeiger1, iDatensatzzeiger2: integer);
implementation
procedure quicksort(var aUn2SortDaten0: TMyArrayOne; bSortierrichtung0:boolean);
var iLinks0,iRechts0,i,j:integer;
begin
// Der erste Datensatz LINKS im Array ist auf Position X
iLinks0:=low(aUn2SortDaten0);
// Der letze Datensatz RECHTS im Array ist auf Position Y
iRechts0:=high(aUn2SortDaten0);
// Aufbau des Vergleichsarrays
setlength(aSortVergleich,length(aUn2SortDaten0));
for i:=iLinks0 to iRechts0 do
begin
// ********************************************************* //
// ** --> Angabe nach welcher Spalte sortiert werden soll ** //
aSortVergleich[i]:=aUn2SortDaten0[i].sWort;
// ********************************************************* //
end;
// ===========================================================
// * BEGINN DER SORTIERUNG - KEINE ÄNDERUNGEN MEHR NOTWENDIG *
//Durchführen der Sortierung
quicksort_teil_a(aUn2SortDaten0, iLinks0, iRechts0);
// es wurde jetzt von a..z sortiert, falls z..a gewünscht ist, geschieht das jetzt
if not bSortierrichtung0 then
begin
repeat
begin
quicksort_teil_c(aUn2SortDaten0, iLinks0, iRechts0);
iLinks0:=iLinks0+1;
iRechts0:=iRechts0-1;
end;
until not (iLinks0 < iRechts0);
end;
end;
// + Teilprozedure 1 von QuickSort +
procedure quicksort_teil_a(var aUn2SortDaten1: TMyArrayOne; iLinksP1,iRechtsP1:integer);
var iTeiler:integer;
begin
if iLinksP1 < iRechtsP1 then
begin
iTeiler := quicksort_teil_b(aUn2SortDaten1, iLinksP1, iRechtsP1);
quicksort_teil_a(aUn2SortDaten1, iLinksP1, iTeiler-1);
quicksort_teil_a(aUn2SortDaten1, iTeiler+1, iRechtsP1);
end;
end;
// + Teilprozedure 2 von QuickSort +
function quicksort_teil_b(var aUn2SortDaten2: TMyArrayOne; iLinksP2,iRechtsP2:integer):integer;
var iLinksTemp,iRechtsTemp:integer;
begin
iLinksTemp := iLinksP2;
// Starte mit j links vom Pivotelement
iRechtsTemp := iRechtsP2 - 1;
repeat
begin
// Suche von links ein Element, welches größer oder gleich dem Pivotelement ist
while ((aSortVergleich[iLinksTemp] <= aSortVergleich[iRechtsP2]) and (iLinksTemp < iRechtsP2)) do iLinksTemp:= iLinksTemp + 1;
// Suche von rechts ein Element, welches kleiner oder gleich dem Pivotelement ist
while ((aSortVergleich[iRechtsTemp] >= aSortVergleich[iRechtsP2]) and (iRechtsTemp > iLinksP2)) do iRechtsTemp:= iRechtsTemp - 1;
if iLinksTemp < iRechtsTemp then quicksort_teil_c(aUn2SortDaten2, iLinksTemp, iRechtsTemp);
end;
until not(iLinksTemp < iRechtsTemp); // solange iLinks an iRechts nicht vorbeigelaufen ist
// Tausche Pivotelement (daten[rechts]) mit neuer endgültigen Position (daten[i])
quicksort_teil_c(aUn2SortDaten2, iLinksTemp, iRechtsP2);
// gib die Position des Pivotelements zurück
result:=iLinksTemp;
end;
// + Teilprozedure 3 von QuickSort +
procedure quicksort_teil_c(var aUn2SortDaten3: TMyArrayOne; iDatensatzzeiger1, iDatensatzzeiger2: integer);
var vHelp:Variant;
iTempDatensatzanzahl:integer;
begin
// Tauschen der beiden Vergleichswerte
vHelp:=aSortVergleich[iDatensatzzeiger1];
aSortVergleich[iDatensatzzeiger1]:=aSortVergleich[iDatensatzzeiger2];;
aSortVergleich[iDatensatzzeiger2]:=vHelp;
// Tauschen von zwei Datensätzen
iTempDatensatzanzahl:=length(aUn2SortDaten3);
setlength(aUn2SortDaten3,iTempDatensatzanzahl+1);
aUn2SortDaten3[iTempDatensatzanzahl]:=aUn2SortDaten3[iDatensatzzeiger1];
aUn2SortDaten3[iDatensatzzeiger1]:=aUn2SortDaten3[iDatensatzzeiger2];
aUn2SortDaten3[iDatensatzzeiger2]:=aUn2SortDaten3[iTempDatensatzanzahl];
setlength(aUn2SortDaten3,iTempDatensatzanzahl);
end;
// * ENDE VON QUICKSORT * //
//====================================================
end.
Noch ein Beispiel für die Deklaration des Records im anderen Unit
TMyRecordOne = record
iZahl:integer;
sWort:string;
bEigenschaft:boolean;
end;
TMyArrayOne = array of TMyRecordOne;
var
aDatenbank: TMyArrayOne;
Und der Aufruf der Sortierung dann im Code
quicksort(aDatenbank,True);
procedure QuickSort(var A: array of Integer; iLO, iHi : integer);
var
Lo, Hi, Mid, T: Integer;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2]; //mid:=A[10]
repeat
while A[Lo] < Mid do Inc(Lo);
while A[Hi] > Mid do Dec(Hi);
if Lo <= Hi then
begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo); //increment Lo:=Lo+1;
Dec(Hi); //decrement Hi:=Hi-1;
end;
until Lo > Hi;
if Hi > iLo then QuickSort(A, iLo, Hi);
if Lo < iHi then QuickSort(A, Lo, iHi);
end;
[edit] VB.NET Code
Private Sub QSort(ByVal list As Integer(), ByVal low As Integer, ByVal high As Integer)
Dim pivote, left, right, temp As Integer
left = low
right = high - 1
If low >= high Then Return
pivote = list(high)
Do
While list(left) < pivote AndAlso left < right : left += 1 : End While
While list(right) > pivote AndAlso right > left : right -= 1 : End While
If list(left) > list(right) Then
temp = list(left)
list(left) = list(right)
list(right) = temp
Else
Exit Do
End If
Loop
temp = list(left)
list(left) = list(high)
list(high) = temp
QSort(list, low, left - 1)
QSort(list, left + 1, high)
End Sub
[edit] VB Code
Option Explicit
Dim Result, I
Dim TestData(100)
const N = 100
Randomize
For I = 0 To N - 1
TestData(I) = ROUND(RND() * 32768)
Next
Sub Swap(byRef Array, first, second)
Dim t
t = Array(first)
Array(first) = Array(second)
Array(second) = t
End Sub
Sub QSort(byRef Array, low, hi)
Dim i, j, p
While low < hi
p = Array(hi)
i = low - 1
For j = low To hi-1
If Array(j) <= p Then
i = i + 1
Swap Array, i, j
End If
Next
Swap Array, i+1, j
QSort Array, low, i
low = i + 2
Wend
End Sub
QSort TestData, 0, N - 1
For I = 0 To N - 1
Result = Result & TestData(I) & VbTab
Next
MsgBox(Result)
[edit] Perl Code
sub qsort {
return () unless @_;
return (qsort(grep { $_ < $_[0] } @_[1..$#_]), $_[0],
qsort(grep { $_ >= $_[0] } @_[1..$#_]));
}
[edit] Prolog Code
append([], L, L).
append([H | L1], L2, [H | Result]) :- append(L1, L2, Result).
partition([], _, [], []).
partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right).
partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right).
qsort([],[]).
qsort([H | Tail], Sorted) :-
partition(Tail, H, Left, Right),
qsort(Left, SortedLeft),
qsort(Right, SortedRight),
append(SortedLeft, [H | SortedRight], Sorted).
[edit] Python Code
import random qsort = lambda l:[] if not l else qsort([n for n in l if n<l[0]])+[n for n in l if n==l[0]]+qsort([n for n in l if n>l[0]]) aList = [random.randrange(1000) for i in xrange(10000)] sortedList = qsort(aList)
[edit] Ruby Code
class Array
def quicksort(list=self.dup)
return list if list.size <= 1
pivot = list.delete_at(rand(list.size))
left, right = list.partition { |e| e < pivot }
quicksort(left) + [pivot] + quicksort(right)
end
end
[edit] Haskell Code
qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
[edit] Ada Code
procedure sort is
type IArr is array (integer range <>) of integer;
procedure swap(X,Y : in out integer) is
t:integer;
begin
t:=x;
x:=y;
y:=t;
end swap;
procedure partition(arr: in out iarr; links, rechts:integer; pivot: out integer) is
x: integer:= arr(links);
i,j: integer;
begin
loop
i:=links+1;
while i <= arr'last and then arr(i) <= x loop
i:=i+1;
end loop;
j:=rechts;
while j>=arr'first and then arr(j) >x loop
j:=j-1;
end loop;
if i< j and j>= arr'first and i <= arr'last then
swap(arr(i),arr(j));
end if;
exit when i>j;
end loop;
arr(links):=arr(j);
arr(j):=x;
pivot:=j;
end partition;
procedure quicksortpart (arr: in out iarr; links , rechts :integer) is
piv: integer;
begin
if links<rechts then
partition(arr,links,rechts,piv);
quicksortpart(arr,links,piv-1);
quicksortpart(arr,piv+1,rechts);
end if;
end quicksortpart;
procedure quicksort (arr:in out IArr) is
begin
quicksortpart(arr,arr'first,arr'last);
end quicksort;
begin
null;
--- aufruf mit quicksort(Array);
end sort;
