Conteúdo principal
Curso: Computer science theory > Unidade 1
Lição 4: Selection sortPseudocódigo do selection sort
Existem muitas formas de ordenar as cartas. Aqui está uma forma simples, chamada ordenação por seleção, possivelmente similar a como você ordenou as cartas acima:
- Encontre o menor cartão. Troque-o com o primeiro cartão
- Encontre o segundo menor cartão. Troque-o com o segundo cartão
- Encontre o terceiro menor cartão. Troque-o com o terceiro cartão
- Repita encontrando o próximo menor cartão e coloque-o na posição correta até que o array esteja ordenado.
Este algoritmo é chamado ordenação por seleção, porque ela seleciona repetidamente o próximo elemento menor e troca-o pelo elemento na posição correta.
Você mesmo pode ver o algoritmo abaixo. Comece usando "Etapa" para ver cada etapa do algoritmo, e então tente "Automático" quando entendê-lo para ver as etapas sendo executadas.
Depois de ver por si mesmo, o que você acha deste algoritmo? Que partes dele parecem demorar mais? Como você acha que ele se sairia com arrays grandes? Mantenha essas questões em mente conforme avançar e implementar este algoritmo.
Encontrar o índice do menor elemento de um subarray
Uma das etapas na ordenação por seleção é encontrar e colocar a próxima menor carta em sua posição correta. Por exemplo, se o array inicialmente tiver os valores [13, 19, 18, 4, 10], precisamos primeiro encontrar o índice do menor valor no array. Como 4 é o menor valor, o índice do menor valor é 3.
A ordenação por seleção troca o valor no índice 3 pelo valor no índice 0, obtendo [4, 19, 18, 13, 10]. Agora precisamos encontrar o índice do segundo menor valor para colocá-lo no índice 1.
Pode ser complicado escrever o código que encontra o índice do segundo menor valor do array. Tenho certeza que você pode fazer isso, mas há um modo melhor. Note que já que o menor valor já foi colocado no índice 0, o que queremos realmente é encontrar o menor valor na parte do array que começa no índice 1. Chamamos uma seção de um array de subarray, então nesse caso, queremos o índice do menor valor no subarray que começa no índice 1. Em nosso exemplo, o array completo é [4, 19, 18, 13, 10], então o menor valor no subarray que começa no índice 1 é 10, que tem o índice 4 no array original. Então, o índice 4 é a posição do segundo menor elemento do array completo.
Tente essa estratégia no próximo desafio, e então você terá a maior parte do que precisa para implementar todo o algoritmo de ordenação por seleção.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
meu codigo do proximo desafio:
var indexOfMinimum = function(array, startIndex) {
// Set initial values for minValue and minIndex,
// based on the leftmost entry in the subarray:
var minValue = array[startIndex];
var minIndex = startIndex;
// Loop over items starting with startIndex,
// updating minValue and minIndex as needed:
for(var nextIndex = minIndex + 1; nextIndex<array.length ; nextIndex++ ) {
if( array[nextIndex]<minValue ) {
minIndex = nextIndex;
minValue = array[nextIndex];
}
}
return minIndex;
};
var array = [18, 6, 66, 44, 9, 22, 14];
var index = indexOfMinimum(array, 2);(4 votos)
No módulo javascript e no módulo desenhando com javascript me parecia bem mais fácil, pelo fato de que o caminho a ser percorrido para a conclusão do desafio possuía muitas etapas, neste, da ciência da computação, o curso te joga no meio de um algoritimo despedaçado, obrigando o aluno a tentar entender a cabeça do criador do programa.(3 votos)
alguém conseguiu resolver o desafio do swap?(1 voto)- var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var testArray = [7, 9, 4];
swap(testArray, 0, 1);
println(testArray);
Program.assertEqual(testArray, [9, 7, 4]);
swap(testArray, 1, 2);
println(testArray);
Program.assertEqual(testArray, [9,4,7]);
swap(testArray, 0, 2);
println(testArray);
Program.assertEqual(testArray, [7, 4, 9]);
//Program.assertEqual(testArray, [9, 7, 4]);(1 voto)