Métodos De Ordenação

[bonoddr]

Bom, resolvi abrir este tópico para comentarmos sobre os principais métodos de ordenação, incluindo seus códigos, logicamente. Vamos começar pelo mais simples e menos eficiente? BUBBLESORT

Mais tarde vou pesquisar como funciona o procedimento e podemos construir o algoritmo passo a passo. Se quiserem se adiantar, melhor ainda!

No momento estou bem ocupado e não posso dar atenção especial, mas resolvi criar o tópico antes que me esquecesse...

[Turbo]

o procedimento conciste em alterar os valores de uma variavel ou d um vetor com o auxilo de uma varivel criada especialmente para armazenar um valor temporario e depois troca-lo de posicao com um outro, é bem simples funciona como os valores sendo bolhas (por isso o nome Bubble) e organizando da maneira q foi pedido, crescente ou descrente....

pelo q me lembro o codigo(basico) é + - assim :

for (i=0;i> tamanho do vetor ou nos d campos -1; i ++)

{

for (j=i+1; j > tamanho do vetor ou nos d campos; j++)

{

if ( a condicao desejada)

{

//troca de valores

aux = a;

a = b;

b = aux;

}

}

}

espero ter ajudado, senao foi mal.....

[bonoddr]

Parece que é praticamente isso, mas vamos organizar as idéias com vetores... Mas valeu ae Turbo, já saímos do zero

[Turbo]

o uso d 2 for's é pra poder utilizar dois vetores, caaso contrario um for dava conta.....

o a é um vetor e o b é outro, é so indicar a variavel como indice..

Valeu

[]´s , e caso alguém saiba como fazer um programa em C, utilizando IP, me dá uma luz q eu não tenho a menor ideia.....

[bonoddr]

O princípio do Bubblesort é a troca de valores entre posições consecutivas, fazendo com que os valores mais altos ( ou mais baixos ) "borbulhem" para o final do arranjo. Vamos imaginar um exemplo de posições de um vetor. Exibirei o código primeiro e, aos poucos, vamos comentando cada linha do mesmo:

long int aux;  // Variável auxiliar para fazer a troca, caso necessário
 for ( long int i=0; i < tam; i++ )
 {
   for ( long int j=0; j<= tam-i; j++ )
   {
     if ( Array[j] > Array[j+1] )  // Caso o elemento de uma posição menor
     {                             // for maior que um elemento de uma posição
       aux        = Array[j];      // maior, faz a troca.
       Array[j]   = Array[j+1];
       Array[j+1] = aux;
     }
   }
 }

[5] [3] [1] [4] [2]

tam é o "tamanho" do vetor, ou seja, o número de elementos que o mesmo possui.

tam=5

no primeiro for, vamos percorrer os elementos do vetor. Então, o primeiro elemento é o Array[0], ou seja, o elemento 5. Vamos então para o segundo for:

i=0 e j=0

se Array[0]>Array[1], então realiza a troca.

5 > 3 (Verdadeiro)

então:

aux = 5 //guarda o valor corrente

Array[0] = Array[1] // Array[j] armazena o menor elemento

Array[1] = aux

então fica: [3] [5] [1] [4] [2]

Agora, o elemento a ser analisado é o próprio 5, pois no último for o j foi incrementado, então:

i=0 e j=1

se Array[1]>Array[2], então realiza a troca.

5 > 1 (Verdadeiro)

então:

aux=5

Array[1]=Array[2]

Array[2]=aux

então fica: [3] [1] [5] [4] [2]

e assim vai, até que fica: [3] [1] [4] [2] [5]

O processo não precisará comparar o penúltimo com o último elemento, pois o último número, o 5, está em sua posição correta no arranjo.

neste último, i=0 e j=5 e ainda j=tam. Quando por último j for igual a 6, então o último for é descartado. Então voltemos para o 1º:

i=1 e j=0

se Array[0]>Array[1], então realiza a troca.

3 > 1 (Verdadeiro)

então:

aux = 3 //guarda o valor corrente

Array[0] = Array[1] // Array[j] armazena o menor elemento

Array[1] = aux

então fica: [1] [3] [4] [2] [5]

Agora notem na posição j=1.

se Array[1]>Array[2], então realiza a troca.

3 > 4 (Falso)

então incrementamos j (j=2) e vamos lá de novo.

Comparamos 4 com 2, é verdadeiro, então trocamos. Fica: [1] [3] [2] [4] [5]

...

...

...

[1] [3] [2] [4] [5]

Depois da troca de 3 com 2, fica:

[1] [2] [3] [4] [5]

OBS: Neste caso o arranjo já está ordenado devido as disposições iniciais de nosso arranjo, mas não é possível nosso algoritmo saber se todo o arranjo está ordenado ou não, e é exatamente por isso que precisaremos realizar mais um processo ).

Para i=5, teremos: [1] [2] [3] [4] [5]. Quando i for 6, o programa sai do loop principal (o primeiro for) e todos os elementos estarão ordenados.

Ufa! Que post enorme!

Mas espero que tenha sido útil. Uma ótima dica para ver a implementação passo-a-passo é debugar o código. Aí vai verificando as atribuições das variáveis.

*editado* pra quem quer checar visualmente os processos de troca, tá aqui um link mais do que interessante:

Métodos de Ordenação

[Wicker Man]

Olha só, bonoddr: no laço de repetição for mais externo você fez:

for ( long int i=0; i <= tam; i++ )

Mas, dessa forma, não se fariam "tam + 1" passagens? Isso porque começaríamos a contar do 0. Não seria melhor fazer:

for ( long int i=0; i < tam; i++ )

O mesmo valeria para o for mais interno.

Por favor me corrijam se estiver errado.

[bonoddr]

Tem razão Wicker Man, muito bem observado

Vou corrigir meu post anterior

[Eddie_666]

vou sair um pouco do assuto para dizer que gostei muito deste tópico, participação do pessoal construindo a solução ajuda muito a aprender

[bonoddr]

Valeu Eddie666...

Agora, alguém se candidata a explicar outro método de ordenação???

[Turbo]

existe um método chamado de divisão e conquista, não sei c já ouviram falar dele, ele consisitem em através de uma variável pivo ( tamanho do vetor /2 ) ir "quebrando" o vetor principal em vetor menores e mais simples, chegando até o vetor elementar com 1 elemento, e apartir dai ele organiza o vetor .... (vou procurar o codigo em casa, pra postar aki .... to meio esquecido. ...)

existe tmb o MergeSort ....

[Wicker Man]

Acho que já ouvi falar sim nesse método de ordenação, mas com outro nome: "SelectionSort". Num sei se é esse que você citou, mas o SelectionSort consiste em, fazer uma busca pelo menor elemento do array (no caso que você citou, uma busca binária) e permutá-lo com o primeiro elemento do array; na segunda passagem, procuraremos o segundo menor elemento do array a partir da segunda posição e o permuteremos com o segundo elemento do array, e assim sucessivamente...

Já tenho o algoritmo pronto, mas resolvi colocar só uma explicação do mesmo caso queiram tentar sozinhos.

Se algo não ficou claro ou falei besteira, postem aí.

[bonoddr]

Posta o código também Wicker... Vai explicando passo a passo, tem muita gente que não sabe como partir no código que pode estar curiosa para entender... Abraços,

bonoddr

[fbafelipe]

é algo +- assim?

 int array[5] = {5, 1, 3, 2, 4}; // array a ser organizado
 int tam = 5; // numero de elementos
 int i, t, i2;
 for (i = 1; i < tam; i++){
  if (array[i] < array[i - 1]){
   t = array[i];
   for (i2 = i - 1; i2 >= 0; i2--){
    if (t < array[i2]){
     array[i2 + 1] = array[i2];
     array[i2] = t;
    }
    else break;
   }
  }
 }

[bonoddr]

hummm... Que tal falarmos agora sobre o QuickSort?

[Eddie_666]

Pessoal, to meio sem tempo aqui, mas assim que eu conseguir, coloco algum método aqui...

[Wicker Man]

Aí, galera, desculpem a demora, mas surgiram imprevistos por aqui!

O código que eu fiz pro SelectionSort é o seguinte:

void SelectionSort( int array[], const int arraySize )

{

    int i, menor,

        var, aux = 0;

 

    for ( i = 0; i < arraySize; i++ ) {  // Loop externo

 

        menor = array[ i ];

   

        for ( int j = i; j < arraySize - 1; j++ ) {  // Loop aninhado

     

            if ( array[ j + 1 ] <= menor ) {  // Definição do menor elemento

     

                menor = array[ j + 1 ];

                aux = j + 1;  // Captura do subscrito do menor elemento

       

            }  // Fim da definição

           

        }  // Fim do Loop aninhado

   

    // Permuta:   

    var = array[ i ];

    array[ i ] = array[ aux ];

    array[ aux ] = var;

   

    }  // Fim do Loop externo

 

}

Qualquer dúvida, crítica ou se fiz besteira, por favor, postem.

[Guest Demetrius Rodrigues Bizin]

Valeu pela ajuda sobre algoritmo de QuickSort. Mas na teoria eu já sei um monte de coisa, inclusive achei a esse algoritmo e C/C++, Java, Delphi ...

Mas não me ajudou muito. Não tenho muito conhecimento em Visual Basic mas estou aprendendo muito.

De qualquer forma obrigaduuuuu.

Demetrius Rodrigues Bizin

[Guest - Andre -]

No começo dos posts foi dito que o BubbleSort é o método menos eficiente. Por que? Gostaria de saber (se alguém puder me explicar ou indicar alguma pagina para eu entender) em que cada método de ordenação é melhor que o outro.

[fbafelipe]

o bublesort é o menos eficiente porque é o q mais fais comaracoes (e consequentemente mais trocas), ele é o mais simples, porem o ecesso de comparacoes compromete o desempenho...

alguém ai sabe o algoritimo do quicksort???

vlw

[Newdelay]

tinha postado besteira, por isso editer, desculpem

[iSoron]

No começo dos posts foi dito que o BubbleSort é o método menos eficiente. Por que? [...]

Bem, não se pode afirmar a princípio que um algoritmo é mais ou menos eficiente que o outro. No pior caso, o QuickSort pode levar um tempo O(n²). O Bublesort, por sua vez, leva vantagem quando se tem um conhecimento dos dados que serão introduzidos. Por exemplo: Se você tem uma lista ordenada e deseja incluir um numero nela, você pode colocar o numero adicional no fim da lista e usar um Bublesort no sentido inverso e sem o loop principal. Nesse caso, o Quicksort perde de lavada

É bem verdade que o quicksort é, quase sempre, mais rápido que os demais. Mesmo assim, é bom analisar a situação direitinho antes de se decidir!

falou,

[iSoron]

Quicksort

O quicksort é um dos algoritmos mais complexos de se implementar, porém é mais eficiente que os demais na maioria das vezes. Basicamente, o que ele faz é o seguinte:

1. Escolhe o ultimo elemento do intervalo [p,q] para comparar com os demais.

2. Cria dois grupos de numeros: os não maiores que k, e os maiores que k. (onde k é o elemento escolhido em (1)).

3. Insere k no meio dos dois grupos. Assim, quem está do lado esquerdo de k é menor ou igual a k; e quem está a direta, é maior que k.

* A operação Partition diz em que indice "k" se encontra. A seguir, é chamado novamente o quicksort para os segmentos dos lados de k. Dessa forma, o vetor fica completamente ordenado.

ex de funcionamento:

 
                            k
2   8   7   1   3   5   6   4
2   8   7   1   3   5   6   4  -  2 é trocado consigo mesmo
2 ( 8 ) 7   1   3   5   6   4  -  8 é adicionado ao grupo dos maiores
2 ( 8   7 ) 1   3   5   6   4  - 7 é adicionado ao grupo dos maiores
2   1 ( 7   8 ) 3   5   6   4  - 1 é trocado com 8, já que ele é menor.
2   1   3 ( 8   7 ) 5   6   4  - 3 é trocado com 7
2   1   3 ( 8   7   5 ) 6   4  - 5 é adicionado ao grupo dos maiores
2   1   3 ( 8   7   5   6 ) 4  - 6 é adicionado ao grupo dos maiores
2   1   3  [4] (7   5   6   8) - Para finalizar, 8 troca com 4

Eis aqui o algoritmo implementado. Essa versão foi um pouco alterada por mim, para ordenar um vetor bidimensional de altura "depth".

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#ifndef _QUICKSORT_HEADER_
    #define _QUICKSORT_HEADER_
    void quicksort(int p, int r);
    int partition(int p, int r);
    void trocar(int a, int b);
#endif

int vetor[200][200];
int index = 0, depth = 2;

void main() {
    srand((unsigned)time(NULL));
    
    for(int i=0; i<100; i++) {
        vetor[0][i] = rand()%200+10;
        vetor[1][i] = i+1;
    }
    quicksort(0, 99);
    for(int i=0; i<100; i++) printf("%d %d\n", vetor[0][i], vetor[1][i]);
    
    scanf("%d", vetor[0][0]);
}

void quicksort(int p, int r) {
    if(p<r) {
        int q = partition(p, r);
        quicksort(p, q-1);
        quicksort(q+1, r);
    }
}
int partition(int p, int r) {
    int x = vetor[index][r];
    int i = p-1;
    
    for(int j=p; j<=r; j++) {
        if(vetor[index][j] <= x) {
            i++;
            trocar(j, i);
        }
    }
    return i;
}
void trocar(int a, int b) {
    for(int i=0; i<depth; i++) {
        int tmp = vetor[i][a];
        vetor[i][a] = vetor[i][b];
        vetor[i][b] = tmp;
    }
}

Ufa, é isso. Acho que deu pra entender.

falou gente!

[Guest - Andre -]

Hum.... agora ficou bem explicado. Mas eu gostaria que alguém me indicasse uma url (to fazendo um trabalho sobre isso... =/ ) em que explicasse bem a diferença entre o QuickSort, BubbleSort, SelectionSort, ShellSort... etc.