Sorting: selection and insertion sort
Colocando um array em ordem
- Ordenação significa colocar os valores de um array em ordem, geralmente do menor para o maior.
- Na prova AP CSA você deve saber escrever e rastrear duas ordenações: selection sort e insertion sort.
- Você também precisa rastrear (mas não escrever) uma terceira ordenação: merge sort. Vamos ver as três aqui.
Selection sort: a ideia
- Percorra o array da esquerda para a direita.
- Em cada posição
i, encontre o menor valor na parte ainda não ordenada (deiaté o fim). - Troque esse menor valor para a posição
i. Agora0..iestá ordenado. - Repita até que todo o array esteja em ordem.
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
Selection sort: um rastreamento
- Vamos ordenar
{5, 2, 4, 1, 3}. A parte à esquerda de|já está ordenada. - Cada passada escolhe o menor valor do resto e o troca para a frente.
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
Insertion sort: a ideia
- Pense em segurar cartas de baralho e adicionar uma carta de cada vez no lugar certo.
- Comece no índice
1. Chame esse valor de chave. - Deslize os valores maiores à esquerda uma posição para a direita, até a chave caber.
- Coloque a chave no espaço vazio. Agora tudo à esquerda está ordenado.
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
Insertion sort: um rastreamento
- Ordenar
{5, 2, 4, 1, 3}novamente. A parte à esquerda de|permanece ordenada enquanto avançamos. - O
keyé o valor que estamos inserindo em cada passagem.
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
Merge sort: apenas rastreamento
- Merge sort usa recursão (lição 15). Você não o escreve na prova, mas deve rastrear ele.
- Divida o array pela metade repetidamente, até que cada peça tenha um valor.
- Mescle pares de peças de volta juntas, mantendo-as sempre em ordem.
Merge sort: um rastreamento
- Um valor já está "ordenado". Mesclar duas peças ordenadas dá uma peça maior ordenada.
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- Selection sort e insertion sort são lentos em arrays grandes (fazem cerca de n² passos).
- Merge sort é mais rápido em arrays grandes (cerca de n·log n passos). É por isso que importa.
Erros comuns
- Selection sort e insertion sort são ambos O(n²).
- Rastreie um array pequeno à mão para verificar sua ordenação.
Agora você tenta
- Cada tarefa lhe dá um esqueleto de método com um TODO. Ordene o array in place (altere
amesmo). - Um Harness oculto ordena vários arrays e verifica o resultado.
- Use Check answer para compilar seu código com os testes fornecidos e visualizar os resultados. Mantenha as interfaces da classe e do método mostradas no modelo.
Selection / insertion sort
Sorting compares and swaps until the list is ordered.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted.
Clique em Executar para ver a saída aqui.