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;
   }
}


Algoritmos de Ordenação #1 – Bubble Sort

Padrão

Olá pessoal! Começamos aqui uma série de posts sobre algoritmos de ordenação. A Ordenação ou Classificação de Dados consiste em uma das tarefas mais frequentes e importantes do processamento de dados. Através dela, é determinada a ordem em que serão apresentadas as entradas de uma tabela de modo que obedeçam à sequência ditada po um ou mais campos (conhecidos como chaves de classificação). Tais ambientes podem na memória principal (RAM), denominado ordenação interna ou em memórias secundárias (como os discos), sendo então uma ordenação externa.

Os algoritmos de ordenação, são “receitas” para ordenar conjuntos de dados. Existem diversos algoritmos, cada qual com uma característica de como ocorre a ordenação, e consequentes melhores aplicações.

Para iniciar a série, vou apresentar uma implementação simples que fiz em C, do algoritmo conhecido como Bubble Sort ou Ordenação por Aprofundamento. Este é um algoritmo simples, que consiste em percorrer a lista de dados comparando os dados adjacentes, trocando-os de ordem caso estejam em ordem invertida. Ao realizar-se uma troca, o algoritmo volta para o início, começando a varredura novamente. É o algoritmo de ordenação que possui o pior desempenho. Mas serve pra uso simples, quando o desempenho não é um fator crítico.

A implementação, como eu disse, está na linguagem C, passando-se um vetor no primeiro parâmetro (que é ordenado, já que em C os vetores são passados como referência), seguido do tamanho do vetor. Fique à vontade para adaptar para outras linguagens ou alterar o tipo de dado e fazer uso em seus aplicativos 🙂

// Algoritmo de Ordenação Bubble Sort
// Implementação por Rafael Toledo (rafaeldtoledo@gmail.com)
// http://striker07.wordpress.com

void bubbleSort(int *vetor, const int tamanho)
{
   int chave, i, aux;

   contador = 0;
   do
   {
      chave = 1;
      for(i = 0; i &lt; tamanho - 1; i++)
      {
         if(vetor[i] &gt; vetor[i + 1])
         {
            aux = vetor[i];
            vetor[i] = vetor[i + 1];
            vetor[i + 1] = aux;
            chave = 0;
         }
      }
   }while(chave == 0);
}