DSA - Datové struktury a algoritmy

QuickSort ::: popis

Jan Kubec(kubecj1) - cvičení (St-14:30)


Seznámení s quicksortem(trochu teorie)
Grafická ukázka jak pracuje quicksort
Základní algoritmus v C a Javě

Seznámení s Quicksortem(trochu teorie)

Quicksort je třídící algoritmus, byl vynalezen v roce 1960 a autorem je C.A.R. Hoare.Quicksort je velmi oblíbený, protože je snadné jej implementovat a pracuje dobře pro mnoho různých druhů dat. A hlavně, v mnoha situacích spotřebovává méně zdrojů než kterákoliv jiná třídící metoda.

Algoritmus quicksortu má požadované rysy - tčídí na místě (potřebuje jen malý pomocný zásobník), využívá v průměru N log N operací k setřídění N položek a má extrémě krátkou vnitřní smyčku.Jeho stinnou stánkou je, že není příliš stabilní pro nejhorší případ potřebuje N^2 operací a je velmi "křehký" ve smyslu, že hloupá chyba v implementaci může zůstat nepovšimnuta a může způsobit, že pro některé souborz bude třídění fungovat špatně.


Grafická ukázka - jak pracuje quicksort

Flash animace
Na tomto příkladu se Vám pokusím přiblížit, jak quicksort třídění funguje. (pozn. ukázka je zpracována v programu Flash, proto je nutné mít nainstalován Flashplayer).


Základní algoritmus

V programovacím jazyku C

void sort(int array[], int begin, int end) {
if (end > begin) {
int pivot = array[begin];
int l = begin + 1;
int r = end;
while(l < r) {
if (array[l] <= pivot) {
l++;
} else {
swap(array[l], array[r]);
r--;
}
}
l--;
r++;
swap(array[begin], array[l]);
sort(array, begin, l);
sort(array, r, end);
}
}

V programovacím jazyku Java

import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
Object pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private void qsort(Object[] array, int begin, int end, Comparator cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public void sort(Object[] array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}


Zdroje, ze kterých jsem čerpal:

Skripta ČVUT - Programovací techniky
Wikipedia.org
Algoritmy v C (Robert Sedgewick) - http://www.awl.com/cseng