package dataStructures;
import java.util.Random;
/**
*
Titulo: A classe utilitária de alg. de ordenação
* Descrição: Possui vários algoritmos de ordenação sobre vectores de
* Objectos comparáveis.
* @version 1.0
*/
public class Sort {
// Esconder o construtor. Não se pode construir objectos desta classe!
private Sort() {
}
private static void swap(Object[] v, int i, int j) {
Object tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
/**
* Ordena através do algoritmo insertSort, complexidade O(|v|^2)
* @param v O vector de elementos a ordenar
*/
public static void insert(Comparable[] v) {
int i,j;
for (i=1;i0 && v[j-1].compareTo(tmp) > 0;j--)
v[j] = v[j-1];
v[j] = tmp;
}
}
/**
* Ordena através do algoritmo selectionSort, complexidade O(|v|^2)
* @param v O vector de elementos a ordenar
*/
public static void selection(Comparable[] v) {
for (int i=0;i0;i--)
for(int j=1;jbegin) {
int lower = begin, higher = end;
// Escolher o pivot arbitrariamente como o elemento do meio
Comparable pivot = v[(begin+end)/2];
while(lower<=higher) {
while((lowerbegin) && (v[higher].compareTo(pivot)>0))
--higher;
if(lower<=higher) // se os indices ainda nao se cruzaram...
swap(v,lower++,higher--); // ... trocar os elementos
}
if(begin=0;i--) {
result[count[v[i]]-1] = v[i];
count[v[i]]--;
}
for(int i=0;i