Capítulo 3: Algoritmos de Ordenação
A ordenação é o processo de reorganizar uma sequência de objetos de forma a colocá-los em uma determinada ordem lógica. Por exemplo, sua fatura do cartão de crédito apresenta as transações em ordem cronológica, e você organiza seus livros em sua estante alfabeticamente por autor e título. A ordenação é uma operação fundamental na ciência da computação e desempenha um papel crucial em muitas aplicações. Existem uma variedade de algoritmos clássicos de ordenação que incorporam diferentes abordagens para este problema.
Neste capítulo, consideramos vários métodos clássicos de ordenação e uma importante estrutura de dados conhecida como fila de prioridade. Começamos com uma discussão sobre vários métodos elementares de ordenação, incluindo ordenação por seleção, ordenação por inserção e ordenação de shell. Esses métodos são apropriadamente usados em muitas aplicações, mas para problemas grandes, recorremos à ordenação por mesclagem e à ordenação rápida, dois algoritmos de ordenação recursivos que podem ser usados para ordenar um grande número de itens. Concluímos com uma discussão sobre filas de prioridade e seu uso na ordenação e em outras aplicações.
Ordenações Elementares
Os algoritmos de ordenação mais simples realizam as seguintes operações:
- Ordenação por seleção: Encontre o menor item e troque-o com a primeira entrada, depois encontre o segundo menor item e troque-o com a segunda entrada, etc.
- Ordenação por inserção: Pegue cada item por vez e insira-o na posição apropriada entre aqueles já considerados (mantendo-os ordenados).
Essas operações espelham a forma como os humanos normalmente realizam tarefas de ordenação e são eficazes para pequenos tamanhos de problema. No entanto, eles não escalam bem e se tornam impraticáveis para ordenar grandes arrays.
Ordenação por Seleção
A ordenação por seleção é um algoritmo de ordenação simples que funciona da seguinte maneira: Primeiro, encontre o menor item no array e troque-o com a primeira entrada (ele mesmo se a primeira entrada já for o menor). Em seguida, encontre o próximo menor item e troque-o com a segunda entrada. Continue dessa forma até que todo o array esteja ordenado.
O loop interno da seleçAqui está a tradução em português do arquivo Markdown, com os comentários traduzidos, mas o código mantido em inglês:
O sort é usado para encontrar o elemento mínimo no subarray não ordenado a[i..N-1]. O índice do elemento mínimo é armazenado em min. Em seguida, a[i] é trocado com a[min], o que coloca o elemento mínimo em sua posição final. À medida que o índice i se move da esquerda para a direita, os elementos à sua esquerda estão em ordem crescente no array e não serão tocados novamente.
Aqui está uma implementação do selection sort em Java:
public static void selectionSort(Comparable[] a) {
// O tamanho do array é armazenado em N
int N = a.length;
// O loop externo percorre todos os elementos do array
for (int i = 0; i < N; i++) {
// O índice do elemento mínimo é inicializado como i
int min = i;
// O loop interno procura o elemento mínimo no subarray a[i+1..N-1]
for (int j = i+1; j < N; j++) {
// Se um elemento menor que o atual mínimo for encontrado, o índice min é atualizado
if (less(a[j], a[min])) min = j;
}
// O elemento mínimo é trocado com o elemento na posição i
exch(a, i, min);
}
}O selection sort usa aproximadamente ~N^2/2 comparações e N trocas para ordenar um array de tamanho N. O tempo de execução é insensível à entrada - leva aproximadamente o mesmo tempo para executar o selection sort em um array já ordenado ou em um array com todas as chaves iguais, quanto em um array aleatoriamente ordenado.
Insertion Sort
O insertion sort é outro algoritmo de ordenação simples que funciona construindo o array final ordenado um item por vez. Ele é muito menos eficiente em arrays grandes do que algoritmos mais avançados, como o quicksort, heapsort ou merge sort, mas tem algumas vantagens:
- É eficiente para pequenos conjuntos de dados.
- É mais eficiente na prática do que o selection sort.
- É estável; ou seja, não altera a ordem relativa de elementos com chaves iguais.
- É in-place; ou seja, requer apenas uma quantidade constante
O(1)de memória adicional. - É online; ou seja, pode ordenar uma lista à medida que a recebe.
Aqui está uma implementação do insertion sort em Java:
public static void insertionSort(Comparable[] a) {
// O tamanho do array é armazenado em N
int N = a.length;
// O loop externo percorre todos os elementos do array, a partir do segundo
for (int i = 1; i < N; i++) {
// O loop interno move os elementos maiores uma posição para a direita,
// fazendo espaço para inserir o elemento atual
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
}O loop interno do insertion sort move os elementos maiores uma posição para a direita, criando espaço para inserir o elemento atual.Aqui está a tradução em português do arquivo Markdown, com os comentários do código traduzidos:
O tempo de execução do insertion sort depende da ordem inicial dos itens na entrada. Por exemplo, se o array for grande e suas entradas já estiverem em ordem (ou quase em ordem), então o insertion sort será muito, muito mais rápido do que se as entradas estiverem aleatoriamente ordenadas ou em ordem inversa.
Shellsort
O Shellsort é uma extensão simples do insertion sort que ganha velocidade permitindo trocas de entradas de array que estão distantes, para produzir arrays parcialmente ordenados que podem ser eficientemente ordenados, eventualmente pelo insertion sort.
A ideia é reorganizar o array para dar-lhe a propriedade de que, tomando cada h-ésima entrada (começando em qualquer lugar), obtém-se uma subsequência ordenada. Tal array é dito ser h-ordenado. De outra forma, um array h-ordenado é h subsequências ordenadas independentes, intercaladas. Ao h-ordenar para alguns valores grandes de h, podemos mover itens no array a longas distâncias e, assim, facilitar o h-ordenamento para valores menores de h. Usando tal procedimento para qualquer sequência de valores de h que termine em 1 produzirá um array ordenado: isso é o Shellsort.
Aqui está uma implementação do Shellsort em Java:
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N;
public MaxPQ(int capacity) {
pq = (Key[]) new Comparable[capacity+1];
}
public boolean isEmpty() {
return N == 0;
}
public void insert(Key key) {
pq[++N] = key;
swim(N);
}
public Key delMax() {
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null;
return max;
}
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
private boolea
```Aqui está a tradução em português do arquivo Markdown, com os comentários traduzidos, mas o código não traduzido:
```java
n menos(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
}Este código implementa um heap binário orientado para o máximo usando um array pq para armazenar a árvore binária completa ordenada pelo heap. As operações insert() e delMax() mantêm o invariante do heap usando os métodos auxiliares swim() e sink() para restaurar a ordem do heap trocando as chaves com um pai maior que um filho ou um filho maior que seu pai, respectivamente.
Cronômetro
Um tipo de dados abstrato mais útil é uma abstração simples e eficaz para um cronômetro, mostrada na página oposta. Para usá-lo, crie um objeto Cronômetro quando quiser iniciar o temporizador, então use o método elapsedTime() para obter o tempo decorrido em segundos desde a criação do objeto. A implementação usa System.currentTimeMillis() do Java para obter o tempo atual em milissegundos desde a meia-noite de 1º de janeiro de 1970.
A variável de instância start registra o momento em que o cronômetro foi criado, e elapsedTime() usa start para calcular o tempo decorrido. O cliente mostrado é típico: ele faz algum cálculo e usa um Cronômetro para medir quanto tempo o cálculo leva. O tipo de dados Cronômetro é uma abstração eficaz porque separa o conceito de um cronômetro (a interface) da implementação (usando System.currentTimeMillis() do Java). Essa separação de interface e implementação é uma característica fundamental dos tipos de dados abstratos que veremos em todos os ADTs ao longo do livro.
Resumo
Tipos de dados abstratos são um elemento essencial da programação orientada a objetos, amplamente utilizados na programação moderna. Nesta seção, vimos:
- Definir um tipo de dados abstrato como uma classe Java, com variáveis de instância para definir os valores do tipo de dados e métodos de instância para implementar as operações nesses valores.
- Desenvolver múltiplas implementações do mesmo API, usando diferentes representações do mesmo dado abstrato.Tipo de dados abstrato.
- Distinguir APIs, clientes e implementações de um tipo de dados abstrato.
- Projetar APIs para tipos de dados abstratos.
- Desenvolver clientes e clientes de teste para uso em testes e depuração.
- Raciocinar sobre a correção de uma implementação de tipo de dados abstrato, usando asserções.
- Comparar o desempenho de diferentes implementações do mesmo API.
Essas atividades são uma parte essencial do desenvolvimento de qualquer programa Java. Cada programa Java que escrevemos envolverá o uso de tipos de dados abstratos de bibliotecas; muitos envolverão o desenvolvimento de novos tipos de dados abstratos. Na próxima seção, consideramos três tipos de dados abstratos fundamentais que são componentes essenciais em um grande número de programas, e na Seção 1.4 consideramos o processo de analisar as características de desempenho das implementações em detalhes.