Métodos de Ordenação

Ordenar é uns das atividades mais importantes para  a computação.  Muitos problemas ficam  fáceis quando os dados encontram-se ordenados. Logo, o conhecimento de vários métodos de ordenação e suas particularidades é extremamente importante para o desenvolvimento de algoritmos eficientes.

O algoritmo de ordenação bolha foi analisado 1956 e  librarysort foi publicado em 2004, mostrando que a área ainda está em evolução. Para comparar os diversos algoritmos, vamos gerar entradas para os algoritmos com o seguinte programa em Python:

import random
def entrada( n ):
    x = range(1,n+1)
    random.shuffle(x)
    filename = str(n) + ".in"
    f = open(filename, "w")
    f.write( str(n) + "\n")
    while len(x) > 0 :
        f.write( str( x.pop() ) + "\n") 

Para gerar um arquivo com os números no intervalo de 1..1000 embaralhados.

>>> entrada(1000)

Código para testar o algoritmo de ordenação:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string>
using namespace std;
char filename[100];
int n,i,j;
int main(){
 
 FILE * fp;
 scanf("%d",&n);
 
 fp = fopen(filename, "rt");
 if(fp==NULL) printf("Erro ao abrir o arquivo!\n");
 int v[n];
 for(i=0;i<n;i++)
  fscanf(fp,"%d",&v[i]);
 clock_t begin = clock();  

 Algoritmo de Ordena��o
 
 double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
 printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);

} 

Ordenação Bolha

for(i=n-1;i>0;i--)

      for(j=0;j

            if( v[j] > v[j+1])

                  swap(v[j], v[j+1]);    

Propriedades:

• Estável (mantém o ordem relativa dos elementos iguais)
• In-Place (requer uma quantidade constante de memória adicional.)

Otimizações:

• Se não acontece nenhuma troca então o vetor já se encontra ordenado.

Ordenação por inserção

for(j=1; j

      chave = v[j];

      i = j-1;

      while(i >= 0 && v[i] > chave){

            v[i+1] = v[i];

            i--;

      }          

      v[i+1] = chave;

}

Propriedades:

• Estável
• In-Place 
• On-line (novos elementos podem ser adicionados durante a ordenação)

Otimizações:  

• Busca binária para encontrar a posição da chave no vetor ordenado 

QuickSort

#include

using namespace std;

int partition(int vec[], int left, int right) {

  int i, j;

  i = left;

  for (j = left + 1; j <= right; ++j) {

    if (vec[j] < vec[left]) {

      ++i;

      swap(vec[i], vec[j]);

    }

  }

  swap(vec[left], vec[i]);

  return i;

}

void quickSort(int vec[], int left, int right) {

  int r;

  if (right > left) {

    r = partition(vec, left, right);

    quickSort(vec, left, r - 1);

    quickSort(vec, r + 1, right);

  }

}

QuickSort da stdlib.h

#include

int compara(const void *pa , const void *pb){

                               int a = *(int *)pa;

                               int b = *(int *)pb;

                               return a-b;

}

qsort(v,n,sizeof(n) , compara);

Propriedades:

• Não estável
• Não in-place

Otimizações:

• Usar a ordenação por inserção em pequenos vetores ~ 10.
• Escolha aleatória do pivô
• Média de três elementos aleatórios

MergeSort

void merge(int A[] , int B[], int p, int q, int r){

     

      int i,j,k;

     

      for(i=p;i<=r;i++)

       B[i] = A[i];

     

      i = p;

      j = q+1;

     

      for(k=p;k<=r;k++){

            if(B[i] <= B[j]){

                  A[k] = B[i];

                  i = i+1;

            }else{

                  A[k] = B[j];

                  j = j+1;

            }

      }

     

}

void mergesort(int vec[] , int vec2[] , int inicio , int fim){

      int meio;

      if( inicio >= fim ) return ;

      else {

            meio = (inicio+fim)/2;

            mergesort(vec, vec2, inicio, meio);

            mergesort(vec, vec2, meio+1, fim );

            merge(vec, vec2 , inicio, meio, fim);

      }

}

Chamada:
int v2[n];
mergesort(v, v2, 0 , n-1);

HeapSort

#include

using namespace std;

priority_queue pq (v,v+n);

i = n-1;

while( !pq.empty() ){

      v[i] = pq.top();

      pq.pop();

      i--;

}

TreeSort

Set são um tipo de container associativo que são implementados como um árvore binária de busca. 

#include

using namespace std;

set myset (v,v+n);

set::iterator it;

for ( i = 0, it=myset.begin() ; it != myset.end(); it++ , i++ )

 v[i] = *it;

Todos os métodos de ordenação estudados acima são baseados em comparação, os algoritmos de ordenação baseados em comparação tem um limite inferior de O(n log n). Veremos um algoritmo que não dependem de comparação.

 

Ordenação por Contagem

int min,max;

int k;

min = 0;

for(i=1;iif( v[i] < v[min]) min = i;

           

max = 0;

for(i=1;iif( v[i] > v[max]) max = i;

           

k = v[max] - v[min] + 1;

           

int c[k];

           

for(i=0;i < k; i++) c[i] = 0;

           

for(i=0; i < n; i++) {

c[v[i]-v[min]]++;

}

           

for(i=1; i< k ; i++) {

c[i] = c[i] + c[i-1];

                 

}

//C[i] contém o número de elementos menores que ou iguais a i

                 

int b[n];

           

for(j=n-1;j>=0;j--){

      c[ v[j]-v[min] ]--;

b[ c[ v[j]-v[min] ] ] = v[j];

}    

 N= 100000

BUBBLE SORT
EXECUTION TIME(seconds):   51.954 second(s).
INSERTION SORT
EXECUTION TIME(seconds):   17.546 second(s).
QUICK SORT
EXECUTION TIME(seconds):    0.028 second(s).
QSORT SORT
EXECUTION TIME(seconds):    0.026 second(s).
MERGE SORT
EXECUTION TIME(seconds):    0.028 second(s).
HEAP SORT
EXECUTION TIME(seconds):    0.127 second(s).
TREE SORT
EXECUTION TIME(seconds):     0.15 second(s).
COUNT SORT
EXECUTION TIME(seconds):    0.008 second(s).