C / C++ Ajuda para analise do Bubble sort

[Pattack]

alguem pode me ajudar a analisar um algoritimo de ordenação bubble sort em C++ ?

tenho que avaliar a eficiencia, custo, velocidade, entre outras coisas que se achar interessante ressaltar, no caso seria uma analise completa do programa.incluindo o método de estudo e como chegou ąs conclusões. Como colocar algum contator no código pra poder se ter ideia do numero de interações que ocorreram sabe?
se alguem puder dar essa força ai, envio as linhas de codigo por email ou conforme for melhor ... !!

[Lizard]

Eu dou uma ajuda (: eu conheço o bubble sort, mas é pra vc dizer a vantagem de usar esse método em relação a algum outro método ou falar somente deste método?

[Pattack]

Eu dou uma ajuda (: eu conheço o bubble sort, mas é pra vc dizer a vantagem de usar esse método em relação a algum outro método ou falar somente deste método?

sim ,no caso eu teria que ter os resultados do bubble sort para comparar com os outros algoritimos de ordenaçao (select,insertion,quick...) entre o que tem que ser analisado é o tempo, a perfomance, o que é melhor em que ... seja mudando o tamanho (10,100,1000) , em ordem crescente e decrescente tbm. Podendo ser incluido linhas de codigo para fazer a mediçao do que é pedido por exemplo : #include <time.h>, etc.
o programa ta em anexo. se incluir ou modificar alguma linha vc pode me mandar o programa modificado? o programa ta em c++ (sou novo por aqui to meio perdidao rs)

[Lizard]

O Bubblesort é o tipo de análise mais simples que tem, ele percorre número por número em ordem e vai vendo o real lugar de cada um e fazendo as trocas. Parando pra analisar, ele faz algumas trocas desnecessárias. Levando em consideração os números nessa respectiva ordem: 10, 1, 3. Deveria ficar 1, 3 ,10. Porém no método bubblesort ele primeiro vai deixar 1, 10, 3.
E só depois 1, 3, 10. O interessante do método select é que ele analisa todos os números, e vai armazenando o menor em uma variável e só quando é terminado que ele coloca aquela variável menor na sua posição. Já a bubblesort vai fazendo trocas sempre que necessário, mesmo que um dos números não esteja no local certo.

Eu olhei seu código e a única alteração que pensei foi a de tirar o do-while e colocar um for no local. Mas nada além disso. Pensei nisso, porque como eu sei a quantidade de vezes que vou repetir o laço o ideal seria for ao invés do do-while (que faz com que eu crie uma variável bool que é a "trocou").

Bom, é isso que eu pude notar com uma pequena pesquisa e olhando o código que você me mostrou (: Se não fui claro ou se você tiver como completar ou até corrigir algo que eu disse, por favor poste para que possamos aprender juntos!

[Pattack]

O Bubblesort é o tipo de análise mais simples que tem, ele percorre número por número em ordem e vai vendo o real lugar de cada um e fazendo as trocas. Parando pra analisar, ele faz algumas trocas desnecessárias. Levando em consideração os números nessa respectiva ordem: 10, 1, 3. Deveria ficar 1, 3 ,10. Porém no método bubblesort ele primeiro vai deixar 1, 10, 3.
E só depois 1, 3, 10. O interessante do método select é que ele analisa todos os números, e vai armazenando o menor em uma variável e só quando é terminado que ele coloca aquela variável menor na sua posição. Já a bubblesort vai fazendo trocas sempre que necessário, mesmo que um dos números não esteja no local certo.

Eu olhei seu código e a única alteração que pensei foi a de tirar o do-while e colocar um for no local. Mas nada além disso. Pensei nisso, porque como eu sei a quantidade de vezes que vou repetir o laço o ideal seria for ao invés do do-while (que faz com que eu crie uma variável bool que é a "trocou").

Bom, é isso que eu pude notar com uma pequena pesquisa e olhando o código que você me mostrou (: Se não fui claro ou se você tiver como completar ou até corrigir algo que eu disse, por favor poste para que possamos aprender juntos!

suas conclusoes foram otimas ! mas eu precisava de algumas linhas a mais que imprimisse por exemplo, o tempo que ele demora pra ser executado, quantos passos ele da ate ordenar, etc. eu to precisando analisar essas coisas pra depois comparar com o resultados dos outros e dizer qual é mais rapido , qual é o melhor essas coisas.

[Pattack]

O Bubblesort é o tipo de análise mais simples que tem, ele percorre número por número em ordem e vai vendo o real lugar de cada um e fazendo as trocas. Parando pra analisar, ele faz algumas trocas desnecessárias. Levando em consideração os números nessa respectiva ordem: 10, 1, 3. Deveria ficar 1, 3 ,10. Porém no método bubblesort ele primeiro vai deixar 1, 10, 3.
E só depois 1, 3, 10. O interessante do método select é que ele analisa todos os números, e vai armazenando o menor em uma variável e só quando é terminado que ele coloca aquela variável menor na sua posição. Já a bubblesort vai fazendo trocas sempre que necessário, mesmo que um dos números não esteja no local certo.

Eu olhei seu código e a única alteração que pensei foi a de tirar o do-while e colocar um for no local. Mas nada além disso. Pensei nisso, porque como eu sei a quantidade de vezes que vou repetir o laço o ideal seria for ao invés do do-while (que faz com que eu crie uma variável bool que é a "trocou").

Bom, é isso que eu pude notar com uma pequena pesquisa e olhando o código que você me mostrou (: Se não fui claro ou se você tiver como completar ou até corrigir algo que eu disse, por favor poste para que possamos aprender juntos!

preciso da analise só do bubble sort mesmo, de quanto tempo ele demora , quantos passos ele da pra ordenar, seja em ordem crescente e decrescente, nos tamanhos 10, 100, 1000 . dai com esses resultados eu comparo com os results dos outros entende

[Lizard]

Certo, vou ver se entendi bem.
Em relação ao tempo, peço que você mesmo veja, pois ainda não aprendi sobre o header time.h do C++.
O primeiro passo do Bubblesort é pegar o primeiro número e ir comparando com TODOS os outros, e vai trocando sempre que encontra um número menor.
Ao final da comparação com todos os números, conclui-se que aquele primeiro número que
usávamos para comparar já está no lugar correto, e agora o processo se repete com o segundo número, e assim sucessivamente diminuindo a quantidade de comparações.
Na primeira vez, faz-se 9 comparações, depois 8, depois 7, etc...
Sempre que um número é comparado com todos os outros, ele já está na posição correta, enquanto os outros ainda não se sabe...
Após fazer essas comparações decrescentes os números estão organizados.

kkkk Acho que é a melhor análise que posso fazer sobre o BubbleSort pra você, se eu não tiver sido claro em algo, pode perguntar ou falar

[Pattack]

....

kkkk Acho que é a melhor análise que posso fazer sobre o BubbleSort pra você, se eu não tiver sido claro em algo, pode perguntar ou falar

entao coloquei o header time.h porem nao sei se o certo é colocar no main ou no bubble. mandei em anexo pra vc dar uma olhada. agora to precisando saber como declaro uma variavel global que va incrementando a cada passo da ordenaçao pra eu saber a quantidade de passos dados ou se tem outra forma de se saber isso ,

[Lizard]

Eu copiei seu código e coloquei no meu Dev e deu um erro... O main não está retornado int e sim void. Eu já pesquisei muito a respeito disso e vi que somente há um bom tempo atrás era permitido o main ser do tipo void. O código funciona 100% no seu compilador? Outra coisa que ocorreu foi que o código está em looping infinito, então só vou dizer como criar a variável global já que não sei se você ia querer que eu alterasse o código...

Declaração:

int passos =0; // Criação da variável global valendo 0

void BubbleSort(int* v, int tam)
{

Agora se você quiser saber quantos números são percorridos, você faz isso:

for(i = 0; i < tam; i++){
passos++; //Incrementa um a cada número que é percorrido

Se só quiser saber as trocas que ele faz:

if(v[i] > v[i + 1])
{
passos++; //Incrementa um a cada número trocado

Mais uma vez quero te lembrar que aconselho fortemente você trocar aquele do-while por um outro for...

[Pattack]

Eu copiei seu código e coloquei no meu Dev e deu um erro... O main não está retornado int e sim void. Eu já pesquisei muito a respeito disso e vi que somente há um bom tempo atrás era permitido o main ser do tipo void. O código funciona 100% no seu compilador? Outra coisa que ocorreu foi que o código está em looping infinito, então só vou dizer como criar a variável global já que não sei se você ia querer que eu alterasse o código...
..

Uso o visual studio e nao da erro algum . coloquei as variaveis globais e deu certo porem quando mudo o tamanho do vetor pra 100 e 1000 nao aparece as linhas "Ordenacao com BubbleSort:" e o "Vetor original:". como paro o looping ? vou te mandar o codigo com as alteraçoes pra vc ver...

[Lizard]

Posso alterar o código como eu quiser? Se sim, peço que espero que de noite eu te respondo com o código pronto...

[Pattack]

Posso alterar o código como eu quiser? Se sim, peço que espero que de noite eu te respondo com o código pronto...

ta bom , pode alterar que eu espero

[Lizard]

Feito

Alterei o código a meu gosto como lhe disse e também citei em comentário as razões da alterações, caso eu tenha esquecido alguma ou não tenha entendido algo, pode perguntar...

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

//Removido o define, o ideal seria const
//Mas como vc pretende alterar o valor ao passar do programa
//Inviavel ambas as formas

int passos =0; // Criação da variável global valendo 0
int trocas =0; // Criação da variável global valendo 0

//Algoritmo de ordenacao BubbleSort
void BubbleSort(int* v, int tam)
{
//Removido variáveis desnecessárias que acumulam
//Mais espaço na memória
int controle = 100;
for(int i = 0; i < tam; i++) //Removido do-while que fazia comparações desnecessárias a mais!!
{
//Comparo sempre i com i2, i2 é sempre um acima de i, pois o i sempre vai estar
//no lugar certo, ou seja, de acordo vai passando o tempo, é desnecessário
//comparar com vetores anteriores.
for(int i2 = (i+1); i2 < tam; i2++)
{
passos++; //Incrementa um a cada número que é percorrido
if(v[i] > v[i2])
{
trocas++; //Incrementa um a cada número trocado
int aux = v[i];
v[i] = v[i2];
v[i2] = aux;

for(int k = 0; k < tam; k++) //O ideal é que a variável seja declarado dentro do laço
printf("%d ", v[k]); //Pois assim que o laço encerra, ela é liberada da memória.
printf("\n\n");//Adicionei isso pra não confundir
}
}
}
}

int main(){
system("title BubbleSort"); //Titulo pra ficar bonitinho
time_t tinicio;
time_t tfim;
double segundos; /* variaveis do "tipo" tempo */
int i;

int tamanho = 10;
for (int C=1;C<=3;C++)
{
{ //Aberto colchete aqui pra poder dizer quando o uso da variável VBS começa e termina
int vbs[tamanho]; //Criado aqui dentro pra ser liberado da memória após uso


//Cria numeros aleatorios para os vetores
for(i = 0; i < tamanho; i++)
vbs[i] = rand()%10+1;

// Ordenacao com BubbleSort
printf("========================================== ===\n");
printf("Ordenacao com BubbleSort: \n");
printf("========================================== ===\n");
printf("Vetor original: \n");
printf("---------------------------------------------\n");
for(i = 0; i < tamanho; i++){
printf("%d ", vbs[i]);
}
printf("\n---------------------------------------------\n");
printf("Passos da ordenacao: \n");
printf("---------------------------------------------\n");
time (&tinicio); /* marca o tempo inicial */
BubbleSort(vbs, tamanho);
time (&tfim); /* marca o tempo final */
printf("\n O bubble sort ordenou em %.f segundo(s).\n",segundos = difftime(tfim, tinicio)/* marca a diferença tfim-tinicio */);
printf("\n Numero de passos %d\n",passos/* marca o numero de passos*/);
printf("\n Numero de trocas %d\n",trocas/* marca o numero de trocas */);
tamanho *= 10;
printf("\n\nPressione qualquer tecla para ver o vetor de %d",tamanho);
trocas =0; passos =0;
getch();
}
system("cls");
}
getch();getch();
}

Com 10 são 0 segundos.
Com 100 são de 3 a 5 segundos.
E com 1000 temos um problema... Demora muito, mas muito, mas muito.
Dá a impressão que tá em looping infinito, mas acredite, não está!
Aqui deu:
Tempo: 559 segundos.
Passos: 499500.
Trocas: 4465.

Caso você esteja impaciente e queira ver como está a troca no de 1000, pode pressionar
ctrl+s que irá pausar, e clicando novamente ele volta...

Bom está aí (: Se gostou, não esquece de dar um obrigado