Este artigo explora a implementação de quatro algoritmos de ordenação comuns em PHP: Bubble Sort, Selection Sort, Insertion Sort e Quick Sort.

1. Bubble Sort (Ordenação por Bolha)

O Bubble Sort é um algoritmo simples que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. Essa passagem é repetida até que a lista esteja ordenada.

function ordenarPorBolha(array $dados): array
{
   $tamanho = count($dados);
   for ($i = 0; $i < $tamanho - 1; $i++) {
       for ($j = 0; $j < $tamanho - 1 - $i; $j++) {
           if ($dados[$j] > $dados[$j + 1]) {
               // Troca os elementos
               $temporario = $dados[$j];
               $dados[$j] = $dados[$j + 1];
               $dados[$j + 1] = $temporario;
           }
       }
   }
   return $dados;
}
 

2. Seelction Sort (Ordenação por Seleção)

O Selection Sort divide a lista em duas partes: uma sublista ordenada e uma sublista não ordenada. O algoritmo encontra o menor elemento na sublista não ordenada e o move para o final da sublista ordenada.

function ordenarPorSelecao(array $dados): array
{
   $tamanho = count($dados);
   for ($i = 0; $i < $tamanho - 1; $i++) {
       $indiceMenor = $i;
       for ($j = $i + 1; $j < $tamanho; $j++) {
           if ($dados[$j] < $dados[$indiceMenor]) {
               $indiceMenor = $j;
           }
       }
       // Troca o menor elemento encontrado com o primeiro elemento da sublista não ordenada
       if ($indiceMenor !== $i) {
           $temporario = $dados[$i];
           $dados[$i] = $dados[$indiceMenor];
           $dados[$indiceMenor] = $temporario;
       }
   }
   return $dados;
}
 

3. Insertion Sort (Ordenação por Inserção)

O Insertion Sort constrói a lista final ordenada um item de cada vez. Ele itera pela lista de entrada, removendo um elemento e encnotrando a posição correta dentro da lista já ordenada, inserindo-o lá.

function ordenarPorInsercao(array $dados): array
{
   $tamanho = count($dados);
   for ($i = 1; $i < $tamanho; $i++) {
       $valorAtual = $dados[$i];
       $j = $i - 1;
       // Move os elementos da sublista ordenada que são maiores que o valor atual para uma posição à frente
       while ($j >= 0 && $dados[$j] > $valorAtual) {
           $dados[$j + 1] = $dados[$j];
           $j--;
       }
       // Insere o valor atual na sua posição correta
       $dados[$j + 1] = $valorAtual;
   }
   return $dados;
}
 

4. Quick Sort (Ordenação Rápida)

O Quick Sort é um algoritmo eficiente que escolhe um elemento como pivô e particiona os outros elementos em dois sub-arrays, de acordo com se eles são menores ou maiores que o pivô. Os sub-arrays são então recursivamente ordenados.

function ordenarRapido(array $dados): array
{
   $tamanho = count($dados);
   if ($tamanho <= 1) {
       return $dados;
   }

   // Escolhe o primeiro elemento como pivô
   $pivo = $dados[0];
   $esquerda = [];
   $direita = [];

   // Particiona os elementos em dois sub-arrays
   for ($i = 1; $i < $tamanho; $i++) {
       if ($dados[$i] < $pivo) {
           $esquerda[] = $dados[$i];
       } else {
           $direita[] = $dados[$i];
       }
   }

   // Ordena recursivamente os sub-arrays e os combina com o pivô
   return array_merge(ordenarRapido($esquerda), [$pivo], ordenarRapido($direita));
}