elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Curso de javascript por TickTack


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion  (Leído 5,742 veces)
Dark00

Desconectado Desconectado

Mensajes: 9


Ver Perfil
Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« en: 14 Noviembre 2012, 01:04 am »

 Ola, sucede que estoy tratando de que mi algoritmo sea mas eficiente, ya que podria suceder de
que los numeros que el usuario haya ingresado ya estivieran totalmente ordenado o parcialmente
 En esta situacion igual se cumplen los dos ciclos, lo cual no es bueno el metodo que utilizo es el
ordenamiento burbuja, alguien tiene alguna idea de como pueda encararlo, aki el codigo :

Código
  1. #include <iostream>
  2. #define TAM 6
  3.  
  4. using namespace::std;
  5.  
  6. int main()
  7. {
  8.    int C[TAM] = {0, 0};
  9.    int temporal;
  10.  
  11.    for( int i=0; i<TAM; i++)
  12.    {    
  13.    cout << "\nIgrese el elemento " << i + 1 << " : " << endl;
  14.    cin >> C[i];
  15.     }
  16.  
  17.    for( int i=0; i<TAM-1; i++)
  18.       for( int j=0; j<=TAM-1; j++)
  19.       {      
  20.          if ( C[j] > C[j + 1] )
  21.          {  
  22.            temporal = C[j];
  23.            C[j] = C[j + 1];
  24.            C[j + 1] = temporal;
  25.          }
  26.       }
  27.    cout << "\nElementos ordenados con el metodo de ordenamiento burbuja\n" << endl;
  28.  
  29.    for( int j=0; j<TAM; j++)
  30.    {
  31.       cout << "\t" << C[j];
  32.     }
  33.  
  34.    return 0;
  35. }

Desde ya gracias


« Última modificación: 14 Noviembre 2012, 01:28 am por Dark00 » En línea

apache_888

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #1 en: 14 Noviembre 2012, 01:40 am »

El algoritmo de ordenación de la burbuja no es el más eficiente. El mejor sería el Quicksort. De todas formas si quieres usar el de la burbuja se me ocurre una cosa que hará más eficiente tu programa, aunque obviamente se notará en listas grandes...muy grandes.

Veo que el intercambio de las variables lo haces usando una variable temporal, pues se puede hacer sin necesitar esa temporal, y además bastante más rápido, simplemente tienes que trabajar a nivel de bits de la siguiente forma.

Supón que quieres intercambiar X e Y:
Código:
   x = x^y;
   y = x^y;
   x = x^y;

La operación ^ es la XOR. Con esto se intercambian las variables mucho antes y sin necesidad de gastar memoria en ninguna variable temporal.

Espero te sirva de algo.


En línea

AgnesBlack

Desconectado Desconectado

Mensajes: 44


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #2 en: 14 Noviembre 2012, 01:57 am »

hmm yo lo mejoraria de la siguiente manera , te lo escribo en  pseucodigo procedure

1:ingresar I=2 , B=0
2: Mientra(Ciclo Condicionado)I<N Y B=0
2.1. hacer B=1
2.2 Ciclo Incondicionado J:=N paso -1 hasta I
2.2.1 Pregunto a[j]<a[j-1]
2.2.2 Si es si B=0
2.2.3 aux=a[j]
2.2.4 a[j]=a[j-1]
2.2.5 a[j-1]=aux
2.3 salgo del ciclo incondicionado e incremento I=I+1


y otra manera es la tecnica de burbuja de plomo si quieres te paso , ese es el procedimiento , me gusta este metodo ya que es eficiente cuando los vectores tan ordenados
En línea

Dark00

Desconectado Desconectado

Mensajes: 9


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #3 en: 14 Noviembre 2012, 03:04 am »

apache_888 con el metodo que me proporcionaste mi algoritmo quedaria algo asi no:

Código
  1. for( int i=0; i<TAM-1; i++)
  2.       for( int j=0; j<=TAM-1; j++)
  3.       {      
  4.          if ( C[j] > C[j + 1] )
  5.          {  
  6.            C[j] ^= C[j + 1];
  7.            C[j + 1] ^= C[j];
  8.            C[j] ^= C[j + 1];
  9.  
  10.          }
  11.       }
Pero segun mi entender el intercambio de valores con una variable temporal, es algo mas rapida
en tiempo de ejecucion, ya que en CPU modernas el metodo XOR es bastante mas lenta respecto a una variable temporal.
AgnesBlack me gustaria ver en que consiste la tecnica de burbuja de plomo me la pasas

Un saludo  ;D
En línea

Ferno


Desconectado Desconectado

Mensajes: 375


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #4 en: 14 Noviembre 2012, 13:14 pm »

En vez de tener 2 ciclos for, podrías reemplazar por dos ciclos while, y tener un flag que te indique si el vector ya está ordenado o no.

Es decir, el code que vos tenés realiza los dos ciclos SIEMPRE, pero si tuvieras un flag que te indique si alguna vez en esos dos ciclos NO entras a hacer el swap (es decir, que el vector ya está ordenado) entonces seteas el flag y al momento de volver al while, sale del loop (no tiene sentido seguir si el vector ya está ordenado).

Espero se haya entendido! (Yo lo conozco como "Burbujeo optimizado" pero desconozco si ese nombre es universal je).

Saludos! Avisame si no entendiste algo!
En línea

Dark00

Desconectado Desconectado

Mensajes: 9


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #5 en: 14 Noviembre 2012, 15:01 pm »

Muchas gracias Ferno gracias a la recomendacion que me diste lo he dejado asi:

Código
  1. for ( int i=1; ((i<TAM)&&(flag==1)); i++ )
  2.    {  flag = 0;
  3.       for ( int j=0; j<(TAM-i); j++ )
  4.       {      
  5.          if ( C[j] > C[j + 1] )
  6.          {  
  7.            temporal = C[j];
  8.            C[j] = C[j + 1];
  9.            C[j + 1] = temporal;
  10.            flag = 1;
  11.           }
  12.        }
  13.    }

Ferno que opinais al respecto cualquier mejora a esta sera bien recibida, por lo menos evitamos el peor de los casos O(TAM^2) jeje.

Un saludo  ;D
« Última modificación: 14 Noviembre 2012, 16:58 pm por Dark00 » En línea

Ferno


Desconectado Desconectado

Mensajes: 375


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #6 en: 14 Noviembre 2012, 15:05 pm »

Si lo hacés de ese modo, creo que la variable flag tenés que inicializarla en 0 al entrar al primer for (fijate que siempre es 1 en tu caso). Es decir, la condición para que entre al for es que i < TAM y flag == 1. Por ende, entrás al for, inicializás en 0 el flag, entra al segundo ciclo, y si nunca entro al if ( para hacer el swap ) entonces el vector está ordenado, por ende, la variable flag siempre será 0, y así, sale del for. Espero que se entienda!

BTW, creo que al método del burbujeo no hay más que hacerle. Si es por complejidad algorítmica, lo máximo que se le puede hacer es cortar cuando el algoritmo ve que el vector ya está ordenado (es decir, es un algoritmo un poco más inteligente que el burbujeo común).

Para algo más eficiente, hay que buscar otro método de ordenamiento, no se podría estrujar más el burbujeo a mi parecer :P
« Última modificación: 14 Noviembre 2012, 15:08 pm por Ferno » En línea

Dark00

Desconectado Desconectado

Mensajes: 9


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #7 en: 14 Noviembre 2012, 15:24 pm »

Si efectivamente modificado ando distraido, investigare sobre otros metodos de ordenamiento ya
que este ya no se puede estrujar asi como lo dices jeje

Un saludo amigo  ;D
En línea

Ferno


Desconectado Desconectado

Mensajes: 375


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #8 en: 14 Noviembre 2012, 15:26 pm »

Que bueno que haya servido!

Métodos de ordenamiento hay muchos. Lo interesante es estudiar y entender el orden de cada uno para comparar la eficiencia.
Te recomiendo ver el quicksort.

Saludos!
En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: Problemas al intentar hacer mas eficiente un algoritmo de ordenacion
« Respuesta #9 en: 14 Noviembre 2012, 17:18 pm »

En el caso del método de ordenación BubbleSort puedes utilizar el contador del bucle externo (numero de elementos a ordenar) para indicar el limite superior del bucle interno (ultimo elemento a verificar), mas o menos así:
Código
  1. for (i = N - 1; i > 0; i--){
  2.   intercambio = 0;
  3.  
  4.   for (j = 0; j < i; j++)
  5.      if (elem[j] > elem[j + 1]){
  6.         /* Intercambiar elementos j y j + 1 */
  7.  
  8.         intercambio = 1;
  9.      }
  10.  
  11.   if (!intercambio)
  12.      break;
  13. }

Un saludo
En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[SOLUCIONADO] duda algoritmo ordenacion c#
.NET (C#, VB.NET, ASP)
CrÄsH 5 6,171 Último mensaje 27 Marzo 2009, 00:50 am
por CrÄsH
[ASM]Algoritmo de Ordenacion Quicksort
ASM
ny0x 9 12,731 Último mensaje 26 Junio 2009, 19:20 pm
por ny0x
Algun algoritmo para la ordenacion del source?
Programación C/C++
taul 5 3,275 Último mensaje 4 Mayo 2010, 18:43 pm
por bizco
Puzzle 8 mi algoritmo sera eficiente? o no lo es?
Programación C/C++
nolasco281 7 5,961 Último mensaje 16 Abril 2014, 22:28 pm
por NikNitro!
Algoritmo de ordenación.
Programación C/C++
Leafar77 1 1,971 Último mensaje 11 Marzo 2015, 17:16 pm
por NOIS
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines