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)