 |
|
||||
 Planilha Web - Planilhas e Calculadoras online para estudantes e profissionais de Engenharia Civil, Engenharia Elétrica e Engenharia Mecânica. |
|||||
Você está aqui: PHP ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
Ordenação e pesquisa em PHP - Como ordenar um vetor de inteiros usando a ordenação Insertion Sort (Ordenação por Inserção)Quantidade de visualizações: 1595 vezes |
|
A ordenação Insertion Sort, ou Ordenação por Inserção, possui uma complexidade de tempo de execução igual à ordenação Bubble Sort (Ordenação da Bolha), ou seja, O(n2). Embora mais rápido que o Bubble Sort, e ser um algorítmo de ordenação quadrática, a ordenação Insertion Sort é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação, porém, nunca recomendada para um grande conjunto de dados. A forma mais comum para o entendimento da ordenação Insertion Sort é compará-la com forma pela qual algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando as cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam à ordenação. A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, a sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim em diante, até não receber mais cartas. Esta é a ideia por trás da ordenação por inserção. Percorra as posições do vetor (array), começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no sub-vetor ordenado à esquerda daquela posição. Vamos ver a implementação na linguagem PHP agora? Observe o seguinte código, no qual temos um vetor de inteiros com os elementos {4, 6, 2, 8, 1, 9, 3, 0, 11}:
<html>
<head>
<title>Estudando PHP</title>
</head>
<body>
<?php
// função que permite ordenar um vetor de inteiros
// usando a ordenação Insertion Sort
// Note a passagem do vetor como referência
function insertionSort(&$vetor){
// este laço varre os elementos a partir do segundo
// elemento, ou seja, o índice 1
for($i = 1; $i < count($vetor); $i++){
// guardamos o elemento atual em temp
$temp = $vetor[$i];
for($j = $i; (($j > 0) && ($vetor[$j - 1] > $temp)); $j--){
$vetor[$j] = $vetor[$j - 1]; // houve uma troca
}
$vetor[$j] = $temp; // colocamos temp em seu devido lugar
}
}
// vamos testar a ordenação agora
$valores = array(4, 6, 2, 8, 1, 9, 3, 0, 11);
// imprime a matriz sem a ordenação
echo "Sem ordenação:<br>";
for($i = 0; $i < count($valores); $i++){
echo $valores[$i] . " ";
}
// vamos ordenar a matriz
insertionSort($valores);
// imprime a matriz ordenada
echo "<br><br>Ordenada usando Insertion Sort:<br>";
for($i = 0; $i < count($valores); $i++){
echo $valores[$i] . " ";
}
?>
</body>
</html>
Ao executar este código PHP nós teremos o seguinte resultado: Sem ordenação: 4 6 2 8 1 9 3 0 11 Ordenada usando Insertion Sort: 0 1 2 3 4 6 8 9 11 |
 Link para compartilhar na Internet ou com seus amigos: |
Desafios, Exercícios e Algoritmos Resolvidos de PHP |
Veja mais Dicas e truques de PHP |
Dicas e truques de outras linguagens |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |
