Kody źródłowe/Sortowanie szybkie

Sortowanie szybkie • Kod źródłowy
Sortowanie szybkie
Kod źródłowy
Kody źródłowe programów stosujących sortowanie szybkie
Wikipedia
Zobacz w Wikipedii hasło 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;
		}		
		}
}

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);     
}
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
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);

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)

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
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)))
  }
}

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.

Informacje o pochodzeniu tekstu możesz znaleźć w dyskusji tego tekstu.