ALGORITMOS DE ORDENAÇÃO – SORTING ALGORITHM
Oi pessoal! I’m back!
Aqui estou novamente com mais um post para o blog. Sei que faz muito tempo que não escrevo nada aqui, mas o tempo ta curto, muito curto!
Ontem na aula de Estrutura de dados II, tivemos uma aula sobre ordenação de vetores, ai me veio à idéia de colocar algo no blog sobre isso.
Irei apresentar pra vocês os métodos: Bubble Sort (bolha), Selection Sort (seleção), Insertion Sort (inserção), Merge Sort e Quick Sort.
Espero que gostem e ajudem vocês.
Abraços.
AGENDA
1. Introdução – Algoritmos de ordenação.
2. Características
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
3. Tempo de ordenação
4. Implementações (Java)
5. Referências
1. INTRODUÇÃO – ALGORITMOS DE ORDENAÇÃO. [English]
Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem, em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica.
Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.
Métodos simples
Métodos sofisticados
- Quick sort
- Merge sort
- Heapsort
- Shell sort
- Radix sort
- Gnome sort
- Count sort
- Bogosort
- Bucket sort
- Cocktail sort
2. CARACTERÍSTICAS
Method Bubble – [English]
O bubble sort, ou ordenação por flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A idéia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
No melhor caso, o algoritmo executa n2 / 2 operações relevantes, onde n representa o número de elementos do vetor. No pior caso é feitas 2n2 operações. No caso médio, são feitas 5n2 / 2 operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
Method Selection – [English]
O selection sort ou ordenação por seleção, é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.
O algoritmo possui complexidade O(n2) enquanto que, por exemplo, os algoritmos Heapsort e Mergesort possuem complexidades O(nlogn).
Method Insert. – [English]
Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.
- Menor número de trocas e comparações entre os algoritmos de ordenação Ω(n) quando o vetor está ordenado.
- Pior caso O(n²)
Method Merge Sort – [English]
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.
Sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.
Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:
- Dividir: Dividir os dados em subsequências pequenas;
- Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
- Combinar: Juntar as duas metades em um único conjunto já classificado.
- Complexidade de tempo: O(n log2 n)
Complexidade de espaço: O(n)
Method Quick Sort – [English]
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 Moscovo como estudante. Ele criou o ‘Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.
O Quicksort adota a estratégia de divisão e conquista. Os passos são:
- Escolha um elemento da lista, denominado pivô;
- Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;
- Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;
A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
- Complexidade de tempo: O(n lg2 n) no melhor caso e no caso médio e O(n2) no pior caso;
- Complexidade de espaço: O(lg2 n) no melhor caso e no caso médio e O(lg2 n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade O(lg2 n) no pior caso.
3.TEMPO DE ORDENAÇÃO
Bubble Sort
- Applied to 1 array containing 100000 items:
- Elapsed Time: 106.034 seconds
- Approximate Compute Time: 86.128 seconds
- Number of comparisons: 4999950000
- Number of copies: 7508838831
Selection Sort
- Applied to 1 array containing 100000 items:
- Elapsed Time: 63.782 seconds
- Approximate Compute Time: 51.856 seconds
- Number of comparisons: 4999950000
- Number of copies: 299997
Insertion Sort
- Applied to 1 array containing 100000 items:
- Elapsed Time: 40.360 seconds
- Approximate Compute Time: 32.878 seconds
- Number of comparisons: 2491283628
- Number of copies: 2491383637
Merge Sort
- Applied to 1 array containing 100000 items:
- Elapsed Time: 0.047 seconds
- Approximate Compute Time: 0.047 seconds
- Number of comparisons: 1566709
- Number of copies: 3400000
QuickSort
- Applied to 1 array containing 100000 items:
- Elapsed Time: 0.031 seconds
- Approximate Compute Time: 0.031 seconds
- Number of comparisons: 2099482
- Number of copies: 812876
4. IMPLEMENTAÇÕES (JAVA)
Method Bubble
public class Bubble {
public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length – 1; i++) {
for (int j = 0; j < a.length – 1; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Method Selection Sort
public class Selection {
public static void SelectionSort(int[] v) {
int index_min, aux;
for (int i = 0; i < v.length; i++) {
index_min = i;
for (int j = i + 1; j < v.length; j++) {
if (v[j] < v[index_min]) {
index_min = j;
}
}
if (index_min != i) {
aux = v[index_min];
v[index_min] = v[i];
v[i] = aux;
}
}
}
}
Method Inserction Sort
public class Insertion {
public static void insertionSort(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
int copyNumber = numbers[i];
int j = i;
while (j > 0 && copyNumber < numbers[j - 1]) {
numbers[j] = numbers[j - 1];
j–;
}
numbers[j] = copyNumber;
}
}
}
Method Merge Sort
public class Merge {
/**
* Algoritmo Merge Sort.
*/
public static void mergeSort(Comparable[] a) {
Comparable[] tmpArray = new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length – 1);
}
/**
* Método interno que faz chamadas recursivas
*/
private static void mergeSort(Comparable[] a, Comparable[] tmpArray,
int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
/**
* Metódo interno que ordena duas partes de um subarray.
*/
private static void merge(Comparable[] a, Comparable[] tmpArray,
int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos – 1;
int tmpPos = leftPos;
int numElements = rightEnd – leftPos + 1;
// loop principal
while (leftPos <= leftEnd && rightPos <= rightEnd)
if (a[leftPos].compareTo(a[rightPos]) <= 0)
tmpArray[tmpPos++] = a[leftPos++];
else
tmpArray[tmpPos++] = a[rightPos++];
while (leftPos <= leftEnd)
tmpArray[tmpPos++] = a[leftPos++];
while (rightPos <= rightEnd)
tmpArray[tmpPos++] = a[rightPos++];
// Copiando o array temporário de volta
for (int i = 0; i < numElements; i++, rightEnd–)
a[rightEnd] = tmpArray[rightEnd];
}
}
Method Quick Sort
import java.util.Arrays;
import java.util.Random;
public class QuickSort<E extends Comparable<? super E>> {
public static final Random RND = new Random();
private void swap(E[] array, int i, int j) {
E tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(E[] array, int begin, int end) {
int index = begin + RND.nextInt(end – begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++i) {
if (array[i].compareTo(pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private void qsort(E[] array, int begin, int end) {
if (end > begin) {
int index = partition(array, begin, end);
qsort(array, begin, index – 1);
qsort(array, index + 1, end);
}
}
public void sort(E[] array) {
qsort(array, 0, array.length – 1);
}
// Exemplo de uso
public static void main(String[] args) {
// Ordenando Inteiros
Integer[] l1 = { 5, 1024, 1, 88, 0, 1024 };
System.out.println(“l1 start:” + Arrays.toString(l1));
QuickSort<Integer> qs = new QuickSort<Integer>();
qs.sort(l1);
System.out.println(“l1 sorted:” + Arrays.toString(l1));
// Ordenando Strings
String[] l2 = { “gamma”, “beta”, “alpha”, “zoolander” };
System.out.println(“l2 start:” + Arrays.toString(l2));
QuickSort<String> qs2 = new QuickSort<String>();
qs2.sort(l2);
System.out.println(“l2 sorted:” + Arrays.toString(l2));
}
}
5. REFERÊNCIAS
[Br]
- http://pt.wikipedia.org/wiki/Algoritmo_de_ordenação
- http://pt.wikipedia.org/wiki/Bubble_sort
- http://pt.wikipedia.org/wiki/Selection_sort
- http://pt.wikipedia.org/wiki/Insertion_sort
- http://pt.wikipedia.org/wiki/Merge_sort
- http://pt.wikipedia.org/wiki/Quick_sort
[En]
- http://en.wikipedia.org/wiki/Sorting_algorithm
- http://en.wikipedia.org/wiki/Bubble_sort
- http://en.wikipedia.org/wiki/Selection_sort
- http://en.wikipedia.org/wiki/Insert_sort
- http://en.wikipedia.org/wiki/Merge_Sort
- http://en.wikipedia.org/wiki/Quick_Sort
Nestes dois sites vocês poderão ver animações em (Java Applet) dos métodos de ordenação apresentados aqui.
These two sites you may see an animation of the sorting algorithms presented here.
[nico]
[Kawano]
Tuor