Algoritmos de Ordenação

Ir em baixo

Algoritmos de Ordenação

Mensagem por Evandro Abu Kamel em Qui 08 Out 2009, 21:03

Olá pessoal, vamos dar início aos nossos estudos de algoritmos de ordenação.
Como o nome já diz, esses algoritmos servem para ordenar conjuntos de dados.

Quem quiser saber mais sobre o assunto, a WikiPédia cita e explica vários (senão todos) métodos de ordenação, alguns deles nem veremos em sala. Mas vela a pena conhecer.

WikiPédia - Algoritmos de Ordenação

Mas antes, devemos ver um pouco sobre Complexidade de Algoritmos. Para isso, segue abaixo o link para o download da matéria, scaneada, passada pela professora.

Complexidade de Algoritmos

Segue abaixo os códigos dos algoritmos que veremos em sala e serão cobrados.
Testem os programas, tentem colocar o programa para imprimir o vetor após ocorrer qualquer troca para ver como funcionam no passo-a-passo; vale usar o Debug também.

E nosso colega Gustavo postou a resolução da lista de exercícios que a professora havia passado:
Resolução da Lista de Exercícios sobre Algoritmos de Ordenação

Bons estudos e até mais.


Última edição por Evandro Abu Kamel em Qua 21 Out 2009, 18:40, editado 9 vez(es)

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Pequena introdução do Quick Sort

Mensagem por gufonseca em Ter 13 Out 2009, 09:40

Galera,

Desculpa a demora no envio, mas trabalhei muito este feriado... ufá... hoje é que estou descansando...

QuickSort


Att.
Gustavo Fonseca
avatar
gufonseca
Moderador
Moderador

Número de Mensagens : 10
Idade : 34
Data de inscrição : 19/08/2009

Ver perfil do usuário http://www.aindanaotenho.com.br

Voltar ao Topo Ir em baixo

Bubble Sort (Bolha)

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 19:11

A seguir o método da bolha, corrigido, pois o do WikiPédia não está funcionando direito.

Código:
class Program
{
   public static void BubbleSort(int[] vetor)
   {
      int swap;
      for (int i = 0; i < vetor.Length - 1; i++)
      {
         for (int j = vetor.Length - 1; j > i; j--)
         {
            if (vetor[i] > vetor[j])
            {
               swap = vetor[i];
               vetor[i] = vetor[j];
               vetor[j] = swap;
            }
         }
      }
   }
         
   static void Main(string[] args)
   {
      Console.WriteLine("\nBubble Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }
               
      long time = Environment.TickCount;                  
      BubbleSort(a);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}


Última edição por Evandro Abu Kamel em Qua 14 Out 2009, 19:31, editado 1 vez(es)

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Insertion Sort (Inserção)

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 19:18

Segue abaixo o método da inserção.

Código:
class Program
{
   public static int[] InsertionSort(int[] A)
   {
      int i, j, index;
      for (i = 1; i < A.Length; i++)
      {
         index = A[i];
         j = i;
         while ((j > 0) && (A[j - 1] > index))
         {
            A[j] = A[j - 1];
            j = j - 1;
         }
         A[j] = index;
      }
      return A;
   }
   
   static void Main(string[] args)
   {
      Console.WriteLine("\nInsertion Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }

      long time = Environment.TickCount;
      a = InsertionSort(a);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Selection Sort (Seleção)

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 19:35

Este é o método da seleção.

Código:
class Program
{
   public static int[] SelectionSort(int[] vetor)
   {
      int aux = 0;
      for (int i = 0; i < vetor.Length - 1; i++)
      {
         for (int j = i + 1; j < vetor.Length; j++)
         {
            if (vetor[j] < vetor[i])
            {
               aux = vetor[j];
               vetor[j] = vetor[i];
               vetor[i] = aux;
            }
         }
      }
      return vetor;
   }
   
   static void Main(string[] args)
   {
      Console.WriteLine("\nSelection Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }

      long time = Environment.TickCount;
      a = SelectionSort(a);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Shell Sort

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 19:40

Abaixo está o método Shell Sort.

Código:
class Program
{
   private static void ShellSort(int[] v)
   {
      int i, j, h = 1, value;

      do
      {
         h = 3 * h + 1;
      } while (h < v.Length);

      do
      {
         h /= 3;
         for (i = h; i < v.Length; i++)
         {
            value = v[i];
            j = i - h;
            
            while (j >= 0 && value < v[j])
            {
               v[j + h] = v[j];
               j -= h;
            }
            v[j + h] = value;
         }
      } while (h > 1);
   }
   
   static void Main(string[] args)
   {
      Console.WriteLine("\nShell Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }

      long time = Environment.TickCount;
      ShellSort(a);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Heap Sort

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 20:03

Segue abaixo o código do heap sort.

Código:
class Program
{
   public static void HeapSort(int[] v)
   { 
      buildMaxHeap(v);
      int n = v.Length;

      for (int i = v.Length - 1; i > 0; i--)
      {
         swap(v, i , 0);
         maxHeapify(v, 0, --n);
      }
   }

   private static void buildMaxHeap(int[] v)
   {
      for (int i = v.Length / 2 - 1; i >= 0; i--)
         maxHeapify(v, i, v.Length);
   }

   private static void maxHeapify(int[] v, int pos, int n)
   {
      int max = 2 * pos + 1;
      int right = max + 1;
      if (max < n)
      {
         if ((right < n) && (v[max] < v[right]))
            max = right;
         if (v[max] > v[pos])
         {
            swap(v, max, pos);
            maxHeapify(v, max, n);
         }
      }
   }

   public static void swap(int[] v, int j, int aposJ)
   {
      int aux = 0;
      aux = v[j];
      v[j] = v[aposJ];
      v[aposJ] = aux;
   }

   static void Main(string[] args)
   {
      Console.WriteLine("\nHeap Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }

      long time = Environment.TickCount;
      HeapSort(a);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Merge Sort

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 20:06

Este é o merge sort, ele não está na ementa da disciplina, mas a professora até gostaria de passá-lo.
Então, não faz mal conhecer.

Código:
class Program
{
   public static void MergeSort(int[] vetor, int inicio, int fim)
   {
      if (inicio < fim)
      {
         int meio = (inicio + fim) / 2;
         MergeSort(vetor, inicio, meio);
         MergeSort(vetor, meio + 1, fim);
         mesclar(vetor, inicio, meio, fim);
      }
   }

   public static void mesclar(int[] vetor, int inicio, int meio, int fim)
   {
      int tamanho = fim - inicio + 1;

      /*
       * Inicialização de um vetor temporario para auxiliar na ordenação O
       * vetor temporário é uma cópia do trecho que será ordenado
       */

      int[] temp = new int[tamanho];

      for (int posicao = 0; posicao < tamanho; posicao++)
      {
         temp[posicao] = vetor[inicio + posicao];
      }

      /*
       * Laço para ordenação do vetor, utilizando o vetor temporário, usando
       * índices i e j para cada trecho de vetor da mesclagem
       */

      int i = 0;
      int j = meio - inicio + 1;

      //A depender das condições, recebe um elemento de um trecho ou outro
      for (int posicao = 0; posicao < tamanho; posicao++)
      {
         vetor[inicio + posicao] =
            (j <= tamanho - 1) ?
               ((i <= meio - inicio) ?
                     (temp[i] < temp[j]) ?
                           temp[i++]
                     : temp[j++]
               : temp[j++])
            : temp[i++];
      }
   }

   static void Main(string[] args)
   {
      Console.WriteLine("\nMerge Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }

      long time = Environment.TickCount;
      MergeSort(a, 0, a.Length-1);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Quick Sort

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 20:11

Este é considerado o método de ordenação mais rápido e eficiente.

Código:
class Program
{
   private static void QuickSort(int[] vetor, int inicio, int fim)
   {
      if (inicio < fim)
      {
         int posicaoPivo = Separar(vetor, inicio, fim);
         QuickSort(vetor, inicio, posicaoPivo - 1);
         QuickSort(vetor, posicaoPivo + 1, fim);
      }
   }

   private static int Separar(int[] vetor, int inicio, int fim)
   {
      int pivo = vetor[inicio];
      int i = inicio + 1, f = fim;
      while (i <= f)
      {
         if (vetor[i] <= pivo)
            i++;
         else if (pivo < vetor[f])
            f--;
         else
         {
            int troca = vetor[i];
            vetor[i] = vetor[f];
            vetor[f] = troca;
            i++;
            f--;
         }
      }
      vetor[inicio] = vetor[f];
      vetor[f] = pivo;
      return f;
   }
   
   static void Main(string[] args)
   {
      Console.WriteLine("\nQuick Sort\n");

      Random r = new Random();
      int dim = 16;
      int max = 30;
      int[] a = new int[dim];

      Console.WriteLine("Vetor Original: \n");
      for (int i = 0; i < a.Length; i++)
      {
         a[i] = r.Next(1, max);
         Console.Write(" {0} ", a[i]);
      }

      long time = Environment.TickCount;
      QuickSort(a, 0, a.Length - 1);
      time = Environment.TickCount - time;

      Console.WriteLine("\n\nVetor Ordenado: \n");
      for (int i = 0; i < a.Length; i++)
      {
         Console.Write(" {0} ", a[i]);
      }

      Console.WriteLine("\nTime Elapsed (n=" + dim + "): " + time + " msecs.");
      Console.ReadLine();
   }
}

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Faster than Quick Sort

Mensagem por Evandro Abu Kamel em Qua 14 Out 2009, 20:15

Esses dias. achei na internet um código de um QuickSort mais rápido que o convencional, inclusive o do C#, que já possui uma função que ordena vetor usando quick sort.
O autor até expõe argumentos a favor do seu código, basta testar.

Faster than quicksort? Use quicksort!

Código:
class Program
{
   private static int[] QuickSort(int[] a, int i, int j)
   {
      if (i < j)
      {
         int q = Partition(a, i, j);
         a = QuickSort(a, i, q);
         a = QuickSort(a, q  1, j);
      }
      return a;
   }

   private static int Partition(int[] a, int p, int r)
   {
      int x = a[p];
      int i = p - 1;
      int j = r  1;
      int tmp = 0;
      
      while (true)
      {
         do
         {
            j--;
         } while (a[j] > x);

         do
         {
            i  ;
         } while (a[i] < x);

         if (i < j)
         {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
         }
         else
            return j;
      }
   }

   
   static void Main(string[] args)
   {
      Console.WriteLine("\nFast QuickSort\n");

      Random r = new Random();
      int dim = 100000;
      int max = 4 * dim;
      int[] a = new int[dim];
      // populate the array randomly
      for (int i = 0; i < a.Length; i  )
      {
         a[i] = r.Next(max);            
      }

      // take starting time (msecs)
      long time = Environment.TickCount;

      // choose between my QuickSort or C# QuickSort

      a = QuickSort(a, 0, a.Length-1);
      // Array.Sort(a);

      // take finish time
      time = Environment.TickCount - time;

      for (int i = 0; i < a.Length; i  )
      {
         Console.WriteLine("{0}", a[i]);
      }

      // print results
      Console.WriteLine("\nTime Elapsed (n="  dim  "): "  time  " msecs.");
      Console.ReadLine();
   }
}


Última edição por Evandro Abu Kamel em Sex 16 Out 2009, 13:31, editado 1 vez(es)

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Solução da lista sobre ordenação

Mensagem por gufonseca em Qui 15 Out 2009, 10:13

Galera,

Segue o link das soluções passadas pela Prof. Michelle para Lista de ordenação.

Att.
Gustavo Fonseca
avatar
gufonseca
Moderador
Moderador

Número de Mensagens : 10
Idade : 34
Data de inscrição : 19/08/2009

Ver perfil do usuário http://www.aindanaotenho.com.br

Voltar ao Topo Ir em baixo

Visualizar a ordenação

Mensagem por gufonseca em Qui 15 Out 2009, 21:23

Galera,

Vejam como os metodos de ordenação funcionam... visualmente falando...mesmo... só assim é fácil de entender...rsrsrsr

ORDENAÇÃO

Bom estudo a todos ...

Att.
Gustavo Fonseca
avatar
gufonseca
Moderador
Moderador

Número de Mensagens : 10
Idade : 34
Data de inscrição : 19/08/2009

Ver perfil do usuário http://www.aindanaotenho.com.br

Voltar ao Topo Ir em baixo

Re: Algoritmos de Ordenação

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Voltar ao Topo Ir em baixo

Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum