Quicksort
Origem: Wikipédia, a enciclopédia livre.
O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscou como estudante. Foi publicado em 1962 após uma série de refinamentos.
Sua premissa básica é dividir o problema de ordenar n itens em dois problemas menores. Em seguida, os problemas menores são ordenados de forma independente e os resultados são combinados para produzir a solução do problema todo.
Índice |
[editar] Complexidade
- Complexidade de tempo: θ(n lg2 n) no melhor caso e no caso médio e θ(n2) no pior caso;
- Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e θ(n) no pior caso.
[editar] Implementações
[editar] Algoritmo em português estruturado
proc quicksort (x:vet[n] int; ini:int; fim:int; n:int)
var
int: i,j,x,aux;
início
i <- ini;
j <- fim;
x <- x[(ini + fim) div 2];
repete
enquanto (x[i] < x) faça
i <- i + 1;
fim-enquanto;
enquanto (x[j] > x) faça
j <- j - 1;
fim-enquanto;
se (i <= j) então
aux <- x[i];
x[i] <- x[j];
x[j] <- aux;
i <- i + 1;
j <- j - 1;
fim-se;
até_que (i >= j);
se (j > ini) então
exec quicksort (x, ini, j, n);
fim-se;
se (i < fim) então
exec quicksort (x, i, fim, n);
fim-se;
fim.
[editar] Haskell
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = (sort [y | y <- rest, y < pivot])
++ [pivot] ++
(sort [y | y <- rest, y >=pivot])
[editar] Lisp
(defunt partition (fun array)
(list (remove-if-not fun array) (remove-if fun array)))
(defun sort (array)
(if (null array) nil
(let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
(append (sort (car part)) (cons (car array) (sort (cadr part)))))))
[editar] Ruby
def sort( array )
return array if array.size <= 1
pivot = array[0]
return sort( array.select { |y| y < pivot } )
+ array.select { |y| y == pivot } +
sort( array.select { |y| y > pivot } )
end
[editar] C++
#include <algorithm>
#include <iterator>
#include <functional>
template <typename T>
void sort(T begin, T end) {
if (begin != end) {
T middle = partition (begin, end, bind2nd(less<iterator_traits<T>::value_type>(), *begin));
sort (begin, middle);
sort (max(begin + 1, middle), end);
}
}
[editar] C
void sort(int array[], int begin, int end) {
if (end - begin > 1) {
int pivot = array[begin];
int l = begin + 1;
int r = end;
while(l < r) {
if (array[l] <= pivot) {
l++;
} else {
r--;
swap(array[l], array[r]);
}
}
l--;
swap(array[begin], array[l]);
sort(array, begin, l);
sort(array, r, end);
}
}
Implementaçao usando 'fat pivot':
void sort(int array[], int begin, int end) {
int pivot = array[begin];
int i = begin + 1, j = end, k = end;
int t;
while (i < j) {
if (array[i] < pivot) i++;
else if (array[i] > pivot) {
j--; k--;
t = array[i];
array[i] = array[j];
array[j] = array[k];
array[k] = t; }
else {
j--;
swap(array[i], array[j]);
} }
i--;
swap(array[begin], array[i]);
if (i - begin > 1)
sort(array, begin, i);
if (end - k > 1)
sort(array, k, end);
}
[editar] 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, right);
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);
}
}
[editar] C#
class Quicksort {
private void swap(int[] Array, int Left, int Right) {
int temp = Array[Left];
Array[Left] = Array[Right];
Array[Right] = temp;
}
public void sort(int[] Array, int Left, int Right) {
int LHold = Left;
int RHold = Right;
Random ObjRan = new Random();
int Pivot = ObjRan.Next(Left,Right);
swap(Array,Pivot,Left);
Pivot = Left;
Left++;
while (Right >= Left) {
if (Array[Left] >= Array[Pivot] && Array[Right] < Array[Pivot])
swap(Array, Left, Right);
else if (Array[Left] >= Array[Pivot])
Right--;
else if (Array[Right] < Array[Pivot])
Left++;
else {
Right--;
Left++;
} }
swap(Array, Pivot, Right);
Pivot = Right;
if (Pivot > LHold)
sort(Array, LHold, Pivot);
if (RHold > Pivot+1)
sort(Array, Pivot+1, RHold);
} }
[editar] Assembly
qsort: @ Takes three parameters:
@ a: Pointer to base of array a to be sorted (arrives in r0)
@ left: First of the range of indexes to sort (arrives in r1)
@ right: One past last of range of indexes to sort (arrives in r2)
@ This function destroys: r1, r2, r3, r4, r5, r7
stmfd sp!, {r4, r6, lr} @ Save r4 and r6 for caller
mov r6, r2 @ r6 <- right
qsort_tailcall_entry:
sub r7, r6, r1 @ If right - left <= 1 (already sorted),
cmp r7, #1
ldmlefd sp!, {r1, r6, pc} @ Return, moving r4->r1, restoring r6
ldr r7, [r0, r1, asl #2] @ r7 <- a[left], gets pivot element
add r2, r1, #1 @ l <- left + 1
mov r4, r6 @ r <- right
partition_loop:
ldr r3, [r0, r2, asl #2] @ r3 <- a[l]
cmp r3, r7 @ If a[l] <= pivot_element,
addle r2, r2, #1 @ ... increment l, and
ble partition_test @ ... continue to next iteration.
sub r4, r4, #1 @ Otherwise, decrement r,
ldr r5, [r0, r4, asl #2] @ ... and swap a[l] and a[r].
str r5, [r0, r2, asl #2]
str r3, [r0, r4, asl #2]
partition_test:
cmp r2, r4 @ If l < r,
blt partition_loop @ ... continue iterating.
partition_finish:
sub r2, r2, #1 @ Decrement l
ldr r3, [r0, r2, asl #2] @ Swap a[l] and pivot
str r3, [r0, r1, asl #2]
str r7, [r0, r2, asl #2]
bl qsort @ Call self recursively on left part,
@ with args a (r0), left (r1), r (r2),
@ also preserves r6 and
@ moves r4 (l) to 2nd arg register (r1)
b qsort_tailcall_entry @ Tail-call self on right part,
@ with args a (r0), l (r1), right (r6)
