Kody źródłowe/Sortowanie szybkie
ANSI C edytuj
Funkcja w języku ANSI C (dla tablicy o elementach typu float i długości typu int). Wersja klasyczna:
typedef float TYP;
void QuickSort(TYP *T, int Lo, int Hi)
{
int i,j;
TYP x;
x = T[(Lo+Hi)>>1]; //można wylosować element dzielący, np: x=T[rand%(Hi-Lo)+Lo+1], dzięki temu zabezpieczymy się dość skutecznie przed ukwadratowieniem.
i = Lo;
j = Hi;
do
{
while (T[i] < x) ++i;
while (T[j] > x) --j;
if (i<=j)
{
TYP tmp = T[i];
T[i] = T[j];
T[j] = tmp;
++i; --j;
}
} while(i < j);
if (Lo < j) QuickSort(T, Lo, j);
if (Hi > i) QuickSort(T, i, Hi);
}
Wersja Lomuto:
void quicksortlomuto(int table[], int first, int last)
{
int i = first-1;
int temp, j;
int pivot = table[last];
for(j=first; j<last; ++j)
{
if(table[j]<pivot)
{
++i;
temp = table[i];
table[i] = table[j];
table[j] = temp;
}
}
if(i<first)
{
temp = table[first];
table[first]=table[last];
table[last]=temp;
++i;
}
if (first<i) quicksortlomuto(table, first, i);
if (last>i+1) quicksortlomuto(table, i+1, last);
}
Wersja hybrydowa(rekurencyjnie dzieli do 10 elementów, jeżeli jest mniej pozostałe sortuje przy pomocy sortowania przez wybieranie):
void quicksorthybrid(int table[], int first, int last)
{
if (last-first>9)
{
int i = first;
int j = last;
int pivot = table[(first+last)>>1];
while (i<j)
{
while ( table[i] < pivot ) ++i;
while ( table[j] > pivot ) --j;
if (i<=j)
{
int temp = table[i];
table[i] = table[j];
table[j] = temp;
++i;
--j;
}
}
if (first < j) quicksorthybrid(table, first, j);
if (i < last) quicksorthybrid(table, i, last);
} else {
int i;
for ( i=first; i<=last; i++ )
{
int j, klucz;
j = i;
klucz = table[j];
while ( j>first && klucz<table[j-1] )
{
table[j] = table[j-1];
j--;
}
table[j] = klucz;
}
}
}
C++ edytuj
Implementacja w języku C++ przy założeniu, że elementem osiowym jest środkowy element tablicy.
void quicksort(int tab[], int left, int right){
int i=left;
int j=right;
int x=tab[(left+right)>>1];
do{
while(tab[i]<x) i++;
while(tab[j]>x) j--;
if(i<=j){
int temp=tab[i];
tab[i]=tab[j];
tab[j]=temp;
i++;
j--;
}
}while(i<=j);
if(left<j) quicksort(tab,left,j);
if(right>i) quicksort(tab,i,right);
}
C# edytuj
void QuickSort<T>(IList<T> items, int left, int right)
where T : IComparable<T>
{
int i = left;
int j = right;
T x;
x = items[(left + right) >> 1];
do
{
while (items[i].CompareTo(x) < 0) i++; //items[i] < x
while (items[j].CompareTo(x) > 0) j--; //items[j] > x
if (i <= j)
{
Swap<T>(items, i, j);
i++; j--;
}
}
while (i < j);
if (left < j) QuickSort(items, left, j);
if (right > i) QuickSort(items, i, right);
}
void Swap<T>(IList<T> list, int left, int right)
{
T temp = list[left];
list[left] = list[right];
list[right] = temp;
}
Haskell edytuj
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
Java edytuj
public static void quicksort(int[] a, int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
// partition
do
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
Pascal edytuj
Kod szybkiego sortowania tablicy w Pascalu (z losowym wyborem elementu dzielącego, lecz bez pozostałych usprawnień).
Procedure Quicksort (Var t:tab; l,r:Integer);
Var
pivot,b,i,j:Integer;
Begin
If l < r Then
Begin
pivot := t[random(r-l) + l+1]; { losowanie elementu dzielącego }
//pivot:=t[(l+r) lsl 1];
i := l-1;
j := r+1;
Repeat
Repeat i := i+1 Until pivot <= t[i];
Repeat j := j-1 Until pivot >= t[j];
b:=t[i]; t[i]:=t[j]; t[j]:=b
Until i >= j;
t[j]:=t[i]; t[i]:=b;
Quicksort(t,l,i-1);
Quicksort(t,i,r)
End
End;
Wywoływanie dla tablicy o długości n: quicksort(tablica,1,n);.
W Delphi algorytm quicksort jest domyślnie wbudowany w klasę TList i wszystkie klasy pochodne. Jako parametr wywołania metody Sort należy podać wskaźnik do funkcji porównującej dwa elementy listy.
JavaScript edytuj
Na podstawie powyższej implementacji w JavaScript.
function quicksort(a, lo, hi)
{
var i=lo;
var j=hi;
var x=a[(lo+hi)/2];
// partition
do
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
return a;
}
var mess = new Array(12,54,23,87,15,43,89,65,34,23,76);
quicksort(mess, 0, 10);
PHP edytuj
Na podstawie implementacji w Javie:
<?PHP
function quicksort(&$tab, $lo, $hi){
$i = $lo;
$j = $hi;
$x = $tab[($lo + $hi) / 2];
do{
while($tab[$i] < $x) $i++;
while($tab[$j] > $x) $j--;
if($i <= $j){
$h = $tab[$i];
$tab[$i] = $tab[$j];
$tab[$j] = $h;
$i++;
$j--;
}
}while($i <= $j);
if($lo < $j) quicksort($tab, $lo, $j);
if($i < $hi) quicksort($tab, $i, $hi);
}
$sort = array(34, 12, 78, 543, 0);
quicksort($sort, 0, 4);
var_dump($sort);
/***************
Wyswietli:
array(5) { [0]=> int(0) [1]=> int(12) [2]=> int(34) [3]=> int(78) [4]=> int(543) }
*/
?>
Python edytuj
Dwie implementacje w języku Python. Pierwsza jest szybsza (mniej kopiowania i tworzenia tymczasowych tablic), druga bardziej czytelna.
def qsort(arr, l=0, r=None):
if r is None: r = len(arr) - 1
i, j = l, r
pivot = arr[(l + r) / 2]
while i <= j:
while arr[i] < pivot: i += 1
while arr[j] > pivot: j -= 1
if i <= j:
arr[i], arr[j] = arr[j], arr[i]
i += 1; j -= 1
if l < j: qsort(arr, l, j)
if r > i: qsort(arr, i, r)
def qsort(arr):
if len(arr) <= 1: return arr
p = arr.pop()
left = [a for a in arr if a < p]
right = [a for a in arr if a >= p]
return qsort(left) + [p] + qsort(right)
Ruby edytuj
Dwie implementacje w języku Ruby. Pierwsza jest szybsza (mniej kopiowania i tworzenia tymczasowych tablic), druga bardziej czytelna.
def qsort(arr, l=0, r=arr.size-1)
i, j = l, r
pivot = arr[(l + r) / 2]
while i <= j
i += 1 while arr[i] < pivot
j -= 1 while arr[j] > pivot
if i <= j
arr[i], arr[j] = arr[j], arr[i]
i += 1; j -= 1
end
end
qsort(arr, l, j) if l < j
qsort(arr, i, r) if r > i
end
def qsort(arr)
return arr if arr.size <= 1
pivot = arr.pop
left, right = arr.partition {|e| e < pivot }
return qsort(left) + [pivot] + qsort(right)
end
Scala edytuj
def qsort(arr: Array[Int]): Array[Int] = {
if (arr.length <= 1) arr
else {
val pivot = arr(arr.length / 2)
Array.concat(
qsort(arr filter (el => pivot > el)),
arr filter (el => pivot == el),
qsort(arr filter (el => pivot < el)))
}
}
SML edytuj
Kod szybkiego sortowania w SML
infix 5 <<;
infix 5 >>;
fun x << (y::ys) = if (y < x) then y::(x << ys) else x << ys
| x << nil = nil;
fun x >> (y::ys) = if (y >= x) then y::(x >> ys) else x >> ys
| x >> nil = nil;
fun quicksort nil = nil
| quicksort [x] = [x]
| quicksort (x::xs) = quicksort(x << xs) @ (x::quicksort(x >> xs))
(* np. sortuj int list *)
quicksort [108,14,13,15];
(* albo krócej *)
fun qs [] = []
| qs (x::xs) = (qs (filter (fn p => p < x) xs)) @ (x::(qs (filter (fn p => p>= x) xs)))
Udziela się zgody na kopiowanie, dystrybucję i/lub modyfikację tego tekstu na warunkach licencji GNU Free Documentation License w wersji 1.2 lub nowszej, opublikowanej przez Free Software Foundation.
Kopia tekstu licencji umieszczona została pod hasłem GFDL. Dostepne jest również jej polskie tłumaczenie.