Ordenar Valores

1. Ordenar Valores

João Paulo
princknoby

(usa Arch Linux)

Enviado em 01/08/2019 - 22:25h

Olá a todos, estou iniciando os estudos sobre ponteiros por conta própria mesmo (QUE LOUCURA!!! HAHAH), não tenho achado nada fácil, e não sei se estou implementando os ponteiros de forma correta, mas, estou na caminhada rsrs'

Me deparei com um exercício a primeira vista, bem simples rsrs, mas quando fui fazer... Deu bastante trabalho.
O exercício é o seguinte: Preciso receber 3 valores do usuário, e devo criar uma função, que recebe esses valores e ordene esses valores de forma DECRESCENTE. E isso deu muito trabalho... Então, gostaria de saber, se existe alguma forma mais simples de fazer essa ordenação. Sinto que transformei algo simples em uma dor de cabeça desnecessária kkkk
Fiz da seguinte forma: (OBS: Caso eu esteja fazendo uso errado dos ponteiros, ou de funções, por favor me corrijam, ainda estou iniciado em ponteiros, iniciei hoje)


#include <stdio.h>

void buffer_clean () {
int ch=fgetc(stdin);
while (ch != '\n' && ch != EOF);
}

void system_pause () {
printf ("\n\nPress any key to continue . . .");
scanf ("%*c");
}

int func_order(int *pa, int *pb, int *pc) {
int aux;

//CASO *PA SEJA O MAIOR DE TODOS
if (*pa > *pb && *pa > *pc) {
//não precisamos fazer nada, precisamos ordenar apenas o *pb e o *pc
if (*pc > *pb) { //Não precisamos fazer: if (*pb > *pc) -> Pois dessa forma já está ordenado
aux = *pb;
*pb = *pc;
*pc = aux;
}
}

//CASO *PB SEJA O MAIOR DE TODOS
else if (*pb > *pa && *pb > *pc) {
aux = *pa;
*pa = *pb;
*pb = aux;

//Sobrou pa e pc, vamos descobrir qual é o maior entre eles
if (*pc > *pb) {
aux = *pb;
*pb = *pc;
*pc = aux;
}
}

//CASO *PC SEJA O MAIOR DE TODOS
else if (*pc > *pa && *pc > *pb) {
aux = *pa;
*pa = *pc;
*pc = aux;

//Agora vamos ordenar o que restou (*pb e *pc)
if (*pc > *pb) {
aux = *pb;
*pb = *pc;
*pc = aux;
}
}

if (*pa == *pb && *pa == *pc) {
return 1;
}

if (*pa != *pb || *pb != *pc || *pa != *pc) {
return 0;
}

}

int main () {
int a, b, c, *pa, *pb, *pc, retorno;

printf ("Digite A: ");
scanf ("%d", &a);
buffer_clean ();

printf ("Digite B: ");
scanf ("%d", &b);
buffer_clean ();

printf ("Digite C: ");
scanf ("%d", &c);
buffer_clean ();

pa=&a; pb=&b; pc=&c;
retorno = func_order(pa,pb,pc);
printf ("A função retornou: %d\n", retorno);
printf ("Vamos testar se está ordenado!!!\n");
printf ("Valor de A: %d\nValor de B: %d\nValor de C: %d\n", *pa, *pb, *pc);

system_pause ();
return (0);
}


Não sei se o programa está 100% perfeito, porque em alguns teste acabava não ordenando (dependo de onde tava o maior, o 2º maior e etc), ai fui consertando aos poucos, até parar organizar em 100% dos testes que eu fiz, mas ainda não sei se está 100%, minha mente já esgotou rsrs
Enfim, existe alguma forma mais simples de fazer o mesmo que eu fiz?

Obrigado


  


2. Re: Ordenar Valores

Paulo
paulo1205

(usa Ubuntu)

Enviado em 09/08/2019 - 03:47h

princknoby escreveu:

Olá a todos, estou iniciando os estudos sobre ponteiros por conta própria mesmo (QUE LOUCURA!!! HAHAH), não tenho achado nada fácil, e não sei se estou implementando os ponteiros de forma correta, mas, estou na caminhada rsrs'

Me deparei com um exercício a primeira vista, bem simples rsrs, mas quando fui fazer... Deu bastante trabalho.
O exercício é o seguinte: Preciso receber 3 valores do usuário, e devo criar uma função, que recebe esses valores e ordene esses valores de forma DECRESCENTE. E isso deu muito trabalho... Então, gostaria de saber, se existe alguma forma mais simples de fazer essa ordenação. Sinto que transformei algo simples em uma dor de cabeça desnecessária kkkk
Fiz da seguinte forma: (OBS: Caso eu esteja fazendo uso errado dos ponteiros, ou de funções, por favor me corrijam, ainda estou iniciado em ponteiros, iniciei hoje)


Parece-me que seu programa vai falhar se você tiver um número pequeno e dois outros números maiores do que ele mas iguais entre si (por exemplo: *pa==1, *pb==2 e *pc==2, mas pode ser em qualquer outra ordem), pois isso vai impedir que o os testes de maioridade simultânea de um número sobre os outros dois seja verdadeira.

Isso poderia ser melhorado se você comparasse primeiro apenas um par de números, reordenando-os, se necessário, e depois comparasse o terceiro número com os números do primeiro par.

Outra possível solução seria trocar nas comparações o operador relacional > por >=, mas essa solução teria a desvantagem de produzir trocas de posição entre números que são iguais.

Outros comentários seguem abaixo.

#include <stdio.h>

void buffer_clean () {
int ch=fgetc(stdin);
while (ch != '\n' && ch != EOF);
}


Uma função razoável para esvaziamento do buffer de stdin, o que é melhor do que muitas soluções que a gente vê por aí. Contudo, melhor ainda seria se você não precisasse de tais funções.


void system_pause () {
printf ("\n\nPress any key to continue . . .");
scanf ("%*c");
}


Já essa, não está tão legal assim. Mas é realmente muito difícil implementar algo semelhante comando PAUSE do DOS apenas com as funções da biblioteca padrão e de um modo que funcione em qualquer sistema.


int func_order(int *pa, int *pb, int *pc) {
int aux;

//CASO *PA SEJA O MAIOR DE TODOS
if (*pa > *pb && *pa > *pc) {
//não precisamos fazer nada, precisamos ordenar apenas o *pb e o *pc
if (*pc > *pb) { //Não precisamos fazer: if (*pb > *pc) -> Pois dessa forma já está ordenado
aux = *pb;
*pb = *pc;
*pc = aux;
}
}

//CASO *PB SEJA O MAIOR DE TODOS
else if (*pb > *pa && *pb > *pc) {
aux = *pa;
*pa = *pb;
*pb = aux;

//Sobrou pa e pc, vamos descobrir qual é o maior entre eles
if (*pc > *pb) {
aux = *pb;
*pb = *pc;
*pc = aux;
}
}

//CASO *PC SEJA O MAIOR DE TODOS
else if (*pc > *pa && *pc > *pb) {
aux = *pa;
*pa = *pc;
*pc = aux;

//Agora vamos ordenar o que restou (*pb e *pc)
if (*pc > *pb) {
aux = *pb;
*pb = *pc;
*pc = aux;
}
}

if (*pa == *pb && *pa == *pc) {
return 1;
}

if (*pa != *pb || *pb != *pc || *pa != *pc) {
return 0;
}


Aqui você tem dois problemas interligados.

O primeiro, que não chega a ser um erro, mas acaba tornando seu código menos eficiente, é que você faz dois testes diferentes para testar essencialmente a mesma condição. O segundo teste é desnecessário, já que ele é exatamente o oposto lógico do primeiro, de modo que se ele falhar, o segundo será necessariamente bem sucedido.

O segundo problema é até um pouco estranho de descrever, porque em parte contraria o que eu disse acima. Mas ocorre que se você compilar esse código com as opções de diagnóstico do compilador ligadas, o compilador vai alarmar que o fluxo de execução chega ao final da função sem retornar um valor. Embora, do ponto de vista lógico-matemático, seja verdade que se o primeiro teste for falso o segundo será necessariamente verdadeiro (e vice-versa), o compilador C não tem como saber disso a priori, pois expressões contendo os operadores lógicos && e || podem não ser inteiramente calculadas.

Como você já deve ter aprendido, a linguagem C prescreve que testes lógicos são efetuados com curto circuito, o que significa que o compilador deve interromper tal teste lógico assim que o resultado não puder ser mais alterado. Assim, por exemplo, se você tiver as expressões E1 e E2 (possivelmente compostas), e você pedir ao compilador que teste a codição E1 && E2, o compilador avalia primeiro E1; se o valor recebido for falso, isso implica que o valor final da operação de e-lógico será necessariamente falso, de modo que o compilador nem ao menos começa a tentar avaliar E2. Analogamente, se você pedir para avaliar E1 || E2 e E1 calhar de ser verdadeiro, o compilador já sabe que o resultado final do ou-lógico será necessariamente verdadeiro, e não se dá ao trabalho de calcular E2.

Por causa disso, embora as condições dos dois comandos if imediatamente acima sejam necessariamente opostas, o compilador é obrigado a testar as duas de maneira independente. Nunca acontecerá de serem ambas falsas ao mesmo tempo (nem ambas verdadeiras, mas a mensagem mostrada se aplicaria ao caso de serem ambas falsas), mas o compilador não tem consciência que lhe permita saber disso.

Uma forma de resolver os dois problemas ao mesmo tempo é eliminar o segundo teste, já que ele é redundante, e retornar incondicionalmente o valor falso caso o teste falhe.
if(*pa==*pb && *pb==*pc)
return 1;
return 0;


Mas há um jeito ainda melhor. Se você reparar bem, você está retornando verdadeiro quando o teste é verdadeiro, e falso quando ele é falso. Desse modo, você pode abreviar o programa retornando o próprio resultado da operação lógica, sem fazer if nenhum.
return *pa==*pb && *pb==*pc; 


}

int main () {


Essa maneira de declarar main é aceita, mas não é tecnicamente a mais correta.

O padrão do C estabelece duas opções para a declaração da função em implementações que contem com um ambiente de execução hospedeiro (como os sistemas operacionais dos nossos micros), que correspondem aos casos em que o programa deve receber ou não deve receber argumentos vindos do ambiente de execução. Caso receba argumentos, tais argumentos são enviados num array de strings, e a função main deve ser declarada com a forma “int main(int argc, char **argv)”, em que argc indica a quantidade de elementos no array de strings apontado por argv, cada uma delas contendo a representação de um argumento passado pelo ambiente de execução (os nomes argc e argv são comuns, mas podem ser trocados, desde que os tipos dos argumentos seja mantido; além disso, por convenção, argv[0], que é o primeiro argumento, costuma conter uma representação do nome usado para invocar o programa, e argv[argc], que é um elemento após o último argumento passado pelo sistema, é um ponteiro nulo).

Por outro lado, se o programa não desejar receber argumentos, a forma de declarar main deve ser a seguinte: “int main(void)”. A palavra-chave void indica que a função não pode receber nenhum argumento. Isso é diferente de deixar os parênteses vazios, como você havia feito, cujo sentido (herdado de linguagens mais antigas) é de que a função pode receber qualquer quantidade de argumentos de quaisquer tipos, o que efetivamente impede o compilador de verificar se a função está sendo invocada corretamente ou não.

(NOTA: Em C++, ao contrário do C, os parênteses vazios na declaração argumentos da função indicam que ela não pode receber argumentos, de modo semelhante ao uso, em C, de uma lista de argumentos contendo apenas “void”.)

	int a, b, c, *pa, *pb, *pc, retorno;

printf ("Digite A: ");
scanf ("%d", &a);
buffer_clean ();

printf ("Digite B: ");
scanf ("%d", &b);
buffer_clean ();

printf ("Digite C: ");
scanf ("%d", &c);
buffer_clean ();

pa=&a; pb=&b; pc=&c;
retorno = func_order(pa,pb,pc);


Você não precisa das variáveis pa, pb e pc: pode chamar diretamente “func_order(&a, &b, &c)”.

	printf ("A função retornou: %d\n", retorno);
printf ("Vamos testar se está ordenado!!!\n");
printf ("Valor de A: %d\nValor de B: %d\nValor de C: %d\n", *pa, *pb, *pc);


E aqui não precisa de *pa, *pb e *pc, mas poderia usar diretamente a, b e c.


system_pause ();
return (0);
}


Não sei se o programa está 100% perfeito, porque em alguns teste acabava não ordenando (dependo de onde tava o maior, o 2º maior e etc), ai fui consertando aos poucos, até parar organizar em 100% dos testes que eu fiz, mas ainda não sei se está 100%, minha mente já esgotou rsrs
Enfim, existe alguma forma mais simples de fazer o mesmo que eu fiz?


Sim, existe. Acima, eu já dei algumas dicas.

Mas há mais que se pode fazer. Uma coisa que eu notei é que sua função func_order() está mais complicada do que poderia ser, com mais testes do que seriam necessários. Dá para fazer a ordenação com três ifs, mas você usou seis

Como você quer fazer uma ordenação, pode usar técnicas de algoritmos de ordenação, sem ter de escrever o algoritmo todo, dado que você tem apenas três elementos.


... “Principium sapientiae timor Domini, et scientia sanctorum prudentia.” (Proverbia 9:10)


3. Re: Ordenar Valores

Paulo
paulo1205

(usa Ubuntu)

Enviado em 09/08/2019 - 04:03h

Seu problema me inspirou a escrever um programinha de testes, em que eu comparo seu algoritmo original (incluindo o erro de comparação que faz com que ele não ordene casos em que você tem um número maior e dois outros maiores que ele e iguais entre si), duas versões corrigidas e ligeiramente modificadas do seu algoritmo, e mais algumas outras funções para ordenar três elementos baseadas em algoritmos tradicionais de ordenação.

O referido programa segue abaixo. Estou rodando alguns testes de desempenho com ele em loop, usando diferentes compiladores e diferentes opções de compilação, para ver qual dos algoritmos produz os melhores resultados. Quando os testes acabarem de rodar, publicarei aqui a saída.

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


/*
Faz ordenação e testa igualdade de três elementos.

Ordenação baseada na versão bottom-up do algoritmo Merge Sort (usa
memória auxiliar para copiar os elementos, depois faz um merge dos dois
primeiros e depois, na hora de reescrever os dados originais, entre esses
dois primeiros e o terceiro).
*/
int sort3_merge(int *restrict a, int *restrict b, int *restrict c){
int aa, bb, cc=*c;
if(*a>=*b){
bb=*b;
aa=*a;
}
else{
bb=*a;
aa=*b;
}
if(aa>=cc){
if(bb>=cc){
*b=bb;
/* *c=cc */ // Não precisa, pois já é igual.
}
else{
*c=bb;
*b=cc;
}
*a=aa;
}
else{
*b=aa;
*c=bb;
*a=cc;
}

return *a==*b && *a==*c;
}

/*
Semelhante a sort3_merge(), mas usando expressões com o operador ternário
(?:), em lugar de tripas de if/else.
*/
int sort3_merge_exp(int *restrict a, int *restrict b, int *restrict c){
int aa, bb, cc=*c;
aa=(*a>=*b? ((bb=*b), *a): ((bb=*a), *b));
*a=(aa>=cc? ((*b=(bb>=cc? bb: ((*c=bb), cc))), aa): ((*b=aa, *c=bb), cc));

return *a==*b && *a==*c;
}

/* Macro que implementa swap de modo inline nas funções mais abaixo. */
#define swap(x, y) do { int t=(x); (x)=(y); (y)=t; } while(0)

/*
Ordenação baseada no famoso (e infame) Bubble Sort (que, para apenas
três elementos, não é tão afrontosamente lento quanto seria no caso de
arrays muito grandes): compara sempre elementos adjacentes, empurando
o menor elemento para o fim da lista. Na primeria passada, define qual
o terceiro elemento, na segunda passada, define o segundo (e, consquente-
mente, também o primeiro).
*/
int sort3_bubble(int *restrict a, int *restrict b, int *restrict c){
// Primeira passada.
if(*a<*b) swap(*a, *b); // Se o menor for o primeiro, troca com o segundo.
if(*b<*c) swap(*b, *c); // Se o menor for o segundo, troca com o terceiro.
// Segunda passada.
if(*a<*b) swap(*a, *b); // Se o menor for o primeiro, troca com o segundo.

return *a==*b && *a==*c;
}

/*
Ordenação baseada no Selection Sort. Na primeira passada, escolhe
quem seria um possível candidato a trocar de lugar com o primeiro. Na
segunda, vê se precisa trocar segundo e terceiro.
*/
int sort3_selection(int *restrict a, int *restrict b, int *restrict c){
// Primeira passada.
int *max=*b<*c? c: b; // Seleciona candidato a trocar com o primeiro.
if(*a<*max) swap(*a, *max); // Troca apenas se for preciso.
// Segunda passada.
if(*b<*c) swap(*b, *c); // Troca apenas se for preciso.

return *a==*b && *a==*c;
}

/*
Ordenação baseada no primeiro algoritmo de ordenação que eu aprendi, que
varre os elementos como o Selection Sort, mas tem um número maior de
operações de swap. Na primeira passada, determina o primeiro elemento
(podendo ter mais de uma troca). Na segunda, determina o segundo (e o
terceiro, por conseguinte).

ATENÇÃO: Esse algoritmo é péssimo num caso de array grande (tanto que
nem ao menos tem um nome próprio)!
*/
int sort3_other(int *restrict a, int *restrict b, int *restrict c){
// Primeira passada.
if(*a<*b) swap(*a, *b);
if(*a<*c) swap(*a, *c);
// Segunda passada.
if(*b<*c) swap(*b, *c);

return *a==*b && *a==*c;
}

/*
Sua função original (incluindo erros). Ela dá problema quando *pa<*pb e
*pb==*pc e quando *pb<*pc e *pa==*pc (daria problema também quando *pc<*pa
e *pa==*pb, mas nesse caso, a liste já veio pré-ordenada, e o efeito do
erro de construção não se faz sentir).
*/
int func_order(int *restrict pa, int *restrict pb, int *restrict pc) {
int aux;
//CASO *PA SEJA O MAIOR DE TODOS
if (*pa > *pb && *pa > *pc) {
//não precisamos fazer nada, precisamos ordenar apenas o *pb e o *pc
if (*pc > *pb) { //Não precisamos fazer: if (*pb > *pc) -> Pois dessa forma já está ordenado
aux = *pb;
*pb = *pc;
*pc = aux;
}
}
//CASO *PB SEJA O MAIOR DE TODOS
else if (*pb > *pa && *pb > *pc) {
aux = *pa;
*pa = *pb;
*pb = aux;
//Sobrou pa e pc, vamos descobrir qual é o maior entre eles
if (*pc > *pb) {
aux = *pb;
*pb = *pc;
*pc = aux;
}
}
//CASO *PC SEJA O MAIOR DE TODOS
else if (*pc > *pa && *pc > *pb) {
aux = *pa;
*pa = *pc;
*pc = aux;
//Agora vamos ordenar o que restou (*pb e *pc)
if (*pc > *pb) {
aux = *pb;
*pb = *pc;
*pc = aux;
}
}
if (*pa == *pb && *pa == *pc) {
return 1;
}
if (*pa != *pb || *pb != *pc || *pa != *pc) {
return 0;
}
return 0;
}

/*
Versão de sua função original com a correção de usar ">=" em lugar de ">"
e omitindo o teste redundante.
*/
int func_order_corr(int *restrict pa, int *restrict pb, int *restrict pc) {
if (*pa >= *pb && *pa >= *pc){
if (*pc > *pb)
swap(*pb, *pc);
}
else if (*pb >= *pa && *pb >= *pc) {
swap(*pa, *pb);
if (*pc > *pb)
swap(*pb, *pc);
}
else if (*pc >= *pa && *pc >= *pb) {
swap(*pa, *pc);
if (*pc > *pb)
swap(*pb, *pc);
}
if (*pa == *pb && *pa == *pc) {
return 1;
}
return 0;
}

/*
Outra versão modificada da sua função, que substitui o teste com if
diretamente pelo return com o valor testado.
*/
int func_order_return(int *restrict pa, int *restrict pb, int *restrict pc) {
if (*pa >= *pb && *pa >= *pc){
if (*pc > *pb)
swap(*pb, *pc);
}
else if (*pb >= *pa && *pb >= *pc) {
swap(*pa, *pb);
if (*pc > *pb)
swap(*pb, *pc);
}
else if (*pc >= *pa && *pc >= *pb) {
swap(*pa, *pc);
if (*pc > *pb)
swap(*pb, *pc);
}
return *pa == *pb && *pa == *pc;
}


double gettime(void){
struct timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
return ts.tv_sec+1.0e-9*ts.tv_nsec;
}


#define BITMASK 0x3FFF
static int buffer[BITMASK+1];

void inicializa_buffer(void){
FILE *f=fopen("/dev/urandom", "rb");
if(!f){
perror("Não pode abrir /dev/random");
exit(1);
}
for(int n=0; n<sizeof buffer/sizeof buffer[0]; n++)
buffer[n]=fgetc(f);//&3;
fclose(f);
}

uintmax_t test_func(unsigned n_rodadas, int (*func)(int *restrict, int *restrict, int *restrict), const char *func_name){
uintmax_t cksum=0;
double s, e;
int i, a, b, c;

s=gettime();
i=0;
for(unsigned n=n_rodadas; n--;){
a=buffer[i++&BITMASK];
b=buffer[i++&BITMASK];
c=buffer[i++&BITMASK];
func(&a, &b, &c);
//cksum+=a+(b<<2)+(c<<4);
//cksum+=a+b+c;
cksum+=(a>=b && b>=c);
}
e=gettime();

printf("%u execuções de %s(a, b, c): tempo decorrido: %0.8gs; checksum: %ju\n", n_rodadas, func_name, e-s, cksum);
fflush(stdout);

return cksum;
}

#define m_test_func(n, func) test_func(n, func, #func)


#define N_RODADAS_DEFAULT 1000000000u


int main(int argc, char **argv){
unsigned n_rodadas;
if(argc>1)
n_rodadas=atol(argv[1]);
else
n_rodadas=N_RODADAS_DEFAULT;
inicializa_buffer();
m_test_func(n_rodadas, func_order);
m_test_func(n_rodadas, func_order_corr);
m_test_func(n_rodadas, func_order_return);
m_test_func(n_rodadas, sort3_merge);
m_test_func(n_rodadas, sort3_merge_exp);
m_test_func(n_rodadas, sort3_bubble);
m_test_func(n_rodadas, sort3_selection);
m_test_func(n_rodadas, sort3_other);
}


Uma observação que faço é que a variável cksum começou como uma forma de usar os valores de a. b e c, para que o compilador não pudesse, ao otimizar o código, concluir que elas estavam sem uso e simplesmente gerasse uma função vazia. Depois foi que eu passei a usá-lo como forma de verificar se todas as ordenações produziam resultados corretos e iguais entre si.


... “Principium sapientiae timor Domini, et scientia sanctorum prudentia.” (Proverbia 9:10)


4. Re: Ordenar Valores

Paulo
paulo1205

(usa Ubuntu)

Enviado em 21/08/2019 - 18:09h

Conforme prometido,
./x-clang-O0                        Tempo (s)   Erros (%)   Tempo (s)   Erros (%)   Tempo (s)   Erros (%)   Tempo (s)   Erros (%)   Tempo (s)   Erros (%)   Tmed. (s)   Emed. (%)
func_order(a, b, c) 70.097939 0.3784 70.137474 0.3479 71.000647 0.4822 70.325320 0.3967 70.428051 0.5188 70.397886 0.4248
func_order_corr(a, b, c) 70.816902 0.0000 70.759284 0.0000 71.007183 0.0000 70.492396 0.0000 70.913124 0.0000 70.797778 0.0000
func_order_return(a, b, c) 72.600033 0.0000 72.540734 0.0000 72.836311 0.0000 72.593049 0.0000 72.674065 0.0000 72.648838 0.0000
sort3_bubble(a, b, c) 71.115235 0.0000 70.969964 0.0000 71.126562 0.0000 71.541722 0.0000 70.908654 0.0000 71.132427 0.0000
sort3_merge(a, b, c) 67.115324 0.0000 66.250668 0.0000 66.527174 0.0000 66.087091 0.0000 66.045753 0.0000 66.405202 0.0000
sort3_merge_exp(a, b, c) 70.043473 0.0000 70.018446 0.0000 70.105133 0.0000 69.992020 0.0000 69.526190 0.0000 69.937052 0.0000
sort3_other(a, b, c) 69.955479 0.0000 69.710969 0.0000 70.015411 0.0000 69.755486 0.0000 69.822494 0.0000 69.851968 0.0000
sort3_selection(a, b, c) 76.405449 0.0000 76.292965 0.0000 76.555733 0.0000 76.417087 0.0000 76.532468 0.0000 76.440740 0.0000

./x-clang-O1 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 43.046341 0.2991 43.167448 0.4456 43.155229 0.3479 43.006444 0.3479 43.199569 0.4150 43.115006 0.3711
func_order_corr(a, b, c) 42.738882 0.0000 42.880594 0.0000 42.893512 0.0000 43.279689 0.0000 42.812272 0.0000 42.920990 0.0000
func_order_return(a, b, c) 42.756464 0.0000 42.187087 0.0000 41.966310 0.0000 42.138487 0.0000 42.276973 0.0000 42.265064 0.0000
sort3_bubble(a, b, c) 43.984133 0.0000 43.826228 0.0000 43.709144 0.0000 43.736053 0.0000 44.062904 0.0000 43.863692 0.0000
sort3_merge(a, b, c) 30.244895 0.0000 30.581813 0.0000 30.213009 0.0000 30.313893 0.0000 30.407992 0.0000 30.352320 0.0000
sort3_merge_exp(a, b, c) 31.127965 0.0000 31.406710 0.0000 31.313047 0.0000 31.189281 0.0000 31.494115 0.0000 31.306224 0.0000
sort3_other(a, b, c) 42.059407 0.0000 42.019172 0.0000 41.891295 0.0000 41.996957 0.0000 41.969258 0.0000 41.987218 0.0000
sort3_selection(a, b, c) 38.393158 0.0000 38.276359 0.0000 38.367893 0.0000 38.177784 0.0000 38.239647 0.0000 38.290968 0.0000

./x-clang-O2 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 41.150165 0.4028 41.485106 0.4089 41.166260 0.3113 41.428946 0.3723 41.342906 0.4028 41.314677 0.3796
func_order_corr(a, b, c) 40.576859 0.0000 41.399519 0.0000 40.658288 0.0000 40.607015 0.0000 41.507983 0.0000 40.949933 0.0000
func_order_return(a, b, c) 41.148772 0.0000 41.395687 0.0000 41.347225 0.0000 41.333745 0.0000 41.505635 0.0000 41.346213 0.0000
sort3_bubble(a, b, c) 39.212278 0.0000 39.345983 0.0000 39.200752 0.0000 39.469511 0.0000 39.278940 0.0000 39.301493 0.0000
sort3_merge(a, b, c) 30.610854 0.0000 30.656411 0.0000 30.590243 0.0000 30.565731 0.0000 30.644872 0.0000 30.613622 0.0000
sort3_merge_exp(a, b, c) 31.326522 0.0000 31.190737 0.0000 31.149050 0.0000 31.128040 0.0000 31.212900 0.0000 31.201450 0.0000
sort3_other(a, b, c) 40.182366 0.0000 40.039886 0.0000 40.260591 0.0000 40.397951 0.0000 40.396304 0.0000 40.255420 0.0000
sort3_selection(a, b, c) 35.480786 0.0000 35.708382 0.0000 35.538309 0.0000 35.617849 0.0000 35.631819 0.0000 35.595429 0.0000

./x-clang-O3 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 41.202849 0.3418 41.229619 0.3357 41.281398 0.4700 41.028303 0.3967 41.159555 0.3479 41.180345 0.3784
func_order_corr(a, b, c) 40.828520 0.0000 40.978991 0.0000 41.454914 0.0000 40.788026 0.0000 40.884420 0.0000 40.986974 0.0000
func_order_return(a, b, c) 41.133507 0.0000 41.075994 0.0000 41.249521 0.0000 41.124281 0.0000 41.056806 0.0000 41.128022 0.0000
sort3_bubble(a, b, c) 39.705541 0.0000 39.587975 0.0000 39.792461 0.0000 39.562762 0.0000 39.687525 0.0000 39.667253 0.0000
sort3_merge(a, b, c) 30.555033 0.0000 30.756896 0.0000 30.655687 0.0000 30.644199 0.0000 30.578940 0.0000 30.638151 0.0000
sort3_merge_exp(a, b, c) 31.070466 0.0000 31.096882 0.0000 31.094921 0.0000 31.185710 0.0000 31.009231 0.0000 31.091442 0.0000
sort3_other(a, b, c) 39.745219 0.0000 39.762278 0.0000 39.866289 0.0000 39.705526 0.0000 39.729270 0.0000 39.761716 0.0000
sort3_selection(a, b, c) 35.723938 0.0000 35.563004 0.0000 35.683202 0.0000 35.722382 0.0000 35.745879 0.0000 35.687681 0.0000

./x-gcc-O0 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 70.949589 0.3662 69.353547 0.3967 69.361567 0.3662 69.668829 0.3540 69.584305 0.3418 69.783567 0.3650
func_order_corr(a, b, c) 69.348331 0.0000 67.308072 0.0000 67.532305 0.0000 67.333648 0.0000 67.773408 0.0000 67.859153 0.0000
func_order_return(a, b, c) 69.011091 0.0000 67.633100 0.0000 67.391634 0.0000 67.478376 0.0000 67.430090 0.0000 67.788858 0.0000
sort3_bubble(a, b, c) 66.525930 0.0000 66.633043 0.0000 66.524622 0.0000 66.680393 0.0000 66.832224 0.0000 66.639242 0.0000
sort3_merge(a, b, c) 67.659838 0.0000 66.462130 0.0000 67.310813 0.0000 66.686206 0.0000 66.759160 0.0000 66.975629 0.0000
sort3_merge_exp(a, b, c) 65.647957 0.0000 65.680597 0.0000 65.714254 0.0000 65.946902 0.0000 65.867391 0.0000 65.771420 0.0000
sort3_other(a, b, c) 65.941130 0.0000 66.198770 0.0000 66.095473 0.0000 66.054387 0.0000 66.185121 0.0000 66.094976 0.0000
sort3_selection(a, b, c) 69.417972 0.0000 68.882697 0.0000 68.533670 0.0000 68.742458 0.0000 68.347828 0.0000 68.784925 0.0000

./x-gcc-O1 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 40.027953 0.4333 40.171928 0.4395 39.984737 0.4456 40.205057 0.3784 39.766398 0.3418 40.031215 0.4077
func_order_corr(a, b, c) 39.501450 0.0000 39.645479 0.0000 39.445287 0.0000 39.680509 0.0000 39.792800 0.0000 39.613105 0.0000
func_order_return(a, b, c) 39.745300 0.0000 40.160238 0.0000 39.775754 0.0000 39.974598 0.0000 40.214905 0.0000 39.974159 0.0000
sort3_bubble(a, b, c) 38.520866 0.0000 38.721985 0.0000 38.465743 0.0000 38.770015 0.0000 38.509021 0.0000 38.597526 0.0000
sort3_merge(a, b, c) 37.851948 0.0000 38.315941 0.0000 37.796477 0.0000 37.765578 0.0000 37.834973 0.0000 37.912983 0.0000
sort3_merge_exp(a, b, c) 36.602818 0.0000 36.703804 0.0000 36.611321 0.0000 36.705930 0.0000 36.560810 0.0000 36.636937 0.0000
sort3_other(a, b, c) 39.894250 0.0000 39.959273 0.0000 39.956878 0.0000 39.957875 0.0000 39.658772 0.0000 39.885410 0.0000
sort3_selection(a, b, c) 40.986240 0.0000 41.163934 0.0000 41.164426 0.0000 41.296247 0.0000 40.970937 0.0000 41.116357 0.0000

./x-gcc-O2 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 38.610740 0.3662 38.603683 0.4761 38.737310 0.3479 38.666024 0.3601 38.700181 0.3967 38.663588 0.3894
func_order_corr(a, b, c) 39.385695 0.0000 39.311884 0.0000 39.594837 0.0000 39.366596 0.0000 39.085566 0.0000 39.348916 0.0000
func_order_return(a, b, c) 39.223473 0.0000 39.151633 0.0000 39.284073 0.0000 39.127227 0.0000 39.119051 0.0000 39.181091 0.0000
sort3_bubble(a, b, c) 38.316186 0.0000 38.529843 0.0000 38.502798 0.0000 38.453162 0.0000 38.547426 0.0000 38.469883 0.0000
sort3_merge(a, b, c) 38.937492 0.0000 38.699861 0.0000 38.806248 0.0000 38.728830 0.0000 38.708532 0.0000 38.776193 0.0000
sort3_merge_exp(a, b, c) 38.064534 0.0000 37.970344 0.0000 37.929768 0.0000 37.926082 0.0000 37.991418 0.0000 37.976429 0.0000
sort3_other(a, b, c) 38.545555 0.0000 38.592494 0.0000 38.583260 0.0000 38.593200 0.0000 38.588961 0.0000 38.580694 0.0000
sort3_selection(a, b, c) 40.212693 0.0000 40.146971 0.0000 40.159345 0.0000 40.131319 0.0000 40.131982 0.0000 40.156462 0.0000

./x-gcc-O3 Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tempo (s) Erros (%) Tmed. (s) Emed. (%)
func_order(a, b, c) 40.149256 0.4578 39.222165 0.2991 39.272233 0.3723 39.281235 0.4456 39.277945 0.4883 39.440567 0.4126
func_order_corr(a, b, c) 40.009362 0.0000 39.917321 0.0000 39.936122 0.0000 39.864801 0.0000 39.974399 0.0000 39.940401 0.0000
func_order_return(a, b, c) 39.981570 0.0000 39.902445 0.0000 39.807277 0.0000 39.950399 0.0000 39.865680 0.0000 39.901474 0.0000
sort3_bubble(a, b, c) 38.734145 0.0000 38.669709 0.0000 38.820057 0.0000 38.760689 0.0000 38.795030 0.0000 38.755926 0.0000
sort3_merge(a, b, c) 36.649190 0.0000 36.825306 0.0000 36.697297 0.0000 36.711147 0.0000 36.694443 0.0000 36.715477 0.0000
sort3_merge_exp(a, b, c) 37.283139 0.0000 37.458507 0.0000 37.377845 0.0000 37.429972 0.0000 37.360711 0.0000 37.382035 0.0000
sort3_other(a, b, c) 38.012043 0.0000 38.224626 0.0000 38.780849 0.0000 38.109665 0.0000 38.117442 0.0000 38.248925 0.0000
sort3_selection(a, b, c) 39.668046 0.0000 39.650656 0.0000 39.618159 0.0000 39.556601 0.0000 39.623001 0.0000 39.623293 0.0000


Eu compilei o mesmo programa com o CLang (LLVM) e com o GCC, e com quatro níveis de otimização (-O0, -O1, -O2 e -O3) em cada um deles. Cada versão compilada era executada cinco vezes seguidas, obtendo um conjunto de dados aleatórios e aplicando sobre esse mesmo conjunto cada uma das oito versões de ordenação 4 bilhões de vezes (sério!), medindo o tempo de cada versão e conferindo se cada uma das 4 bilhões de operações de ordenação em cada estava correta ou não.

Observe como o algoritmo postado originalmente produziu erros de ordenação em cerca de 0,4% dos casos. Parece pouco, mas isso se deve ao tipo do conjunto de dados e como tais dados foram obtidos. No meu caso, usei inteiros de 0 a 255, teoricamente distribuídos aleatoriamente de maneira uniforme. Se a amplitude desses números fosse maior, a chance de se encontrarem trios em que A=B<C ou A=C<B diminuiria, mas nem por isso o bug deixaria de ser grave.


... “Principium sapientiae timor Domini, et scientia sanctorum prudentia.” (Proverbia 9:10)






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts