Algoritmos de Ordenação #5 – Quick Sort

Padrão


Temos aqui, um dos mais rápidos algoritmos de ordenação, o Quick Sort (rápido até no nome!). Grande parte da sua eficiência, dá-se pelo fato de utilizar técnicas de recursão (uma função que faz uma chamada a ela mesma). Com isso, este é considerado um algoritmo complexo. Nesta minha implementação, é necessário passar-se o conjunto de dados e o início e fim (no caso, início 0 e fim tamanho – 1).

Segue a implementação do algoritmo em C:

void quickSort(int *vetor, int inicio, int fim)
{
   int i, j, meio, aux;

   i = inicio;
   j = fim;
   meio = vetor[(inicio + fim) / 2];

   do
   {
      while(vetor[i] < meio)
         i++;
      while(vetor[j] > meio)
         j--;
      if(i <= j)
      {
         aux = vetor[i];
         vetor[i] = vetor[j];
         vetor[j] = aux;
         i++;
         j--;
      }
   }while(i <= j);

   if(inicio < j)
      quickSort(vetor, inicio, j);
   if(i < fim)
      quickSort(vetor, i, fim);
}


Algoritmos de Ordenação #4 – Shell Sort

Padrão


Temos aqui a implementação do algoritmo Shell Sort. Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, o Shell Sort é o mais eficiente algoritmo de ordenação dentre os de complexidade quadrática (não utiliza recursividade). É um refinamento do método de inserção direta.O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o vetor a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção (algoritmo já mostrado no blog).

Segue a implementação em C do algoritmo:

void shellSort(int *vetor, int tamanho)
{
   int i = (tamanho - 1) / 2;
   int chave, k, aux;

   while(i != 0)
   {
      do
      {
         chave = 1;
         for(k = 0; k < MAX - i; ++k)
         {
            if(Vetor[k] > Vetor[k + i])
            {
               aux = Vetor[k];
               Vetor[k] = Vetor[k + i];
               Vetor[k + i] = aux;
               chave = 0;
            }
         }
      }while(chave == 0);
      i = i / 2;
   }
}


Algoritmos de Ordenação #3 – Inserção Direta

Padrão


Mais um algoritmo de ordenação, dessa vez o algoritmo de Inserção Direta ou Insertion Sort. Este algoritmo é bastante eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.

Segue, então, a minha implementação em C deste algoritmo:

void insercaoDireta(int *vetor, int tamanho)
{
   int i, x, k, j;

   for(i = 1; i < tamanho; ++i)
   {
      x = vetor[i];
      k = 0;
      j = i - 1;
      while(j >= 0 && k == 0)
      {
         if(x < vetor[j])
         {
            vetor[j + 1] = vetor[j];
            --j;
         }
         else
            k = j + 1;
      }
      vetor[k] = x;
   }
}


Algoritmos de Ordenação #2 – Seleção Direta

Padrão


Continuando com os algoritmos de ordenação, temos uma implementação em C do algoritmo de ordenação chamado Seleção Direta (ou Selection Sort). Esse algoritmo baseia-se em passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Segue, então, a minha implementação deste algoritmo em C:

void selecaoDireta(int *vetor, int tamanho)
{
   int i, j, menor, aux;

   for(i = 0; i < tamanho - 1; ++i)
   {
      menor = i;
      for(j = i + 1; j < tamanho; ++j)
      {
         if(vetor[j] < vetor[menor])
            menor = j;
      }
      aux = vetor[i];
      vetor[i] = vetor[menor];
      vetor[menor] = aux;
   }
}