Blog gratis
Reportar
Editar
¡Crea tu blog!
Compartir
¡Sorpréndeme!
Programación 1
¡Bienvenidos a nuestro Blog! Espero puedan disfrutarlo y aprender. Este será un contacto que podrá superar los límites de tiempo de las horas de clase: aprovéchenlo para construir algo nuevo.
09 de Mayo, 2016    TEORIA

Ordenamiento

1 Ordenamiento Burbuja (Bubblesort)

1. Descripción.

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. ¿Sencillo no?

2. Pseudocódigo en C.

Tabla de variables
NombreTipoUso
listaCualquieraLista a ordenar
TAMConstante enteraTamaño de la lista
iEnteroContador
jEnteroContador
tempEl mismo que los elementos de la listaPara realizar los intercambios
 
 1. for (i=1; i<TAM; i++)
 2. for j=0 ; j<TAM - 1; j++)
 3. if (lista[j] > lista[j+1])
 4. temp = lista[j];
 5. lista[j] = lista[j+1];
 6. lista[j+1] = temp;
 

3. Un ejemplo

Vamos a ver un ejemplo. Esta es nuestra lista:

4 - 3 - 5 - 2 - 1

Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos:

3 - 4 - 5 - 2 - 1

Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos:

3 - 4 - 2 - 5 - 1

Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente:

3 - 4 - 2 - 1 - 5

Repitiendo este proceso vamos obteniendo los siguientes resultados:

3 - 2 - 1 - 4 - 5

2 - 1 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

4. Optimizando.

Se pueden realizar algunos cambios en este algoritmo que pueden mejorar su rendimiento.

  • Si observas bien, te darás cuenta que en cada pasada a través de la lista un elemento va quedando en su posición final. Si no te queda claro mira el ejemplo de arriba. En la primera pasada el 5 (elemento mayor) quedó en la última posición, en la segunda el 4 (el segundo mayor elemento) quedó en la penúltima posición. Podemos evitar hacer comparaciones innecesarias si disminuimos el número de éstas en cada pasada. Tan sólo hay que cambiar el ciclo interno de esta manera:

    for (j=0; j<TAM - i; j++)

  • Puede ser que los datos queden ordenados antes de completar el ciclo externo. Podemos modificar el algoritmo para que verifique si se han realizado intercambios. Si no se han hecho entonces terminamos con la ejecución, pues eso significa que los datos ya están ordenados. Te dejo como tarea que modifiques el algoritmo para hacer esto :-).
  • Otra forma es ir guardando la última posición en que se hizo un intercambio, y en la siguiente pasada sólo comparar hasta antes de esa posición.

5. Análisis del algoritmo.

Éste es el análisis para la versión no optimizada del algoritmo:

  • Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable.
  • Requerimientos de Memoria: Este algoritmo sólo requiere de una variable adicional para realizar los intercambios.
  • Tiempo de Ejecución: El ciclo interno se ejecuta n veces para una lista de n elementos. El ciclo externo también se ejecuta n veces. Es decir, la complejidad es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n2).

Ventajas:

  • Fácil implementación.
  • No requiere memoria adicional.

Desventajas:

  • Muy lento.
  • Realiza numerosas comparaciones.
  • Realiza numerosos intercambios.

Este algoritmo es uno de los más pobres en rendimiento. Si miras la demostración te darás cuenta de ello. No es recomendable usarlo. Tan sólo está aquí para que lo conozcas, y porque su sencillez lo hace bueno para empezar. Ya veremos otros mucho mejores. Ahora te recomiendo que hagas un programa y lo pruebes. Si tienes dudas mira el programa de ejemplo.

Palabras claves
publicado por mariof2005 a las 16:14 · Sin comentarios  ·  Recomendar
 
Más sobre este tema ·  Participar
Comentarios (0) ·  Enviar comentario
Esta entrada no admite comentarios.
SOBRE MÍ
FOTO

Héctor Mario Freschinaldi

Mail: enviotp@gmail.com
En AS.: PROG1 2016(su nombre y apellido)

En un mundo donde los cambios se suceden vertiginosamente, incluso los tecnológicos, es menester asimilar las nuevas tecnologías para su aplicación inmediata y su proyección a futuro.

» Ver perfil

CALENDARIO
Ver mes anterior Septiembre 2017 Ver mes siguiente
DOLUMAMIJUVISA
12
3456789
10111213141516
17181920212223
24252627282930
TÓPICOS
» COMO SE EVALUA (2)
» COMUNICADOS (16)
» EVALUACIONES (3)
» Información Tecnológica (91)
» LENGUAJE C (18)
» PROGRAMA (2)
» TEORIA (10)
» Trabajos prácticos (8)
SECCIONES
» Inicio
ENLACES
» ¿Hay seguridad en lo que ponés en la WEB?
» ¡Te estoy espìando! (y colaborás conmigo)
» Los peligros de la WEB
» Otra de Facebook
» Historias del CHAT
» 1984/George Orwell
» Revistas de Informática, Tecnica y Nuevas Tecnolog
MÁS LEÍDOS
» 07 Elementos léxicos del lenguaje de programación C
» 1. Algoritmos.
» 10 aplicaciones útiles para llevar a todos lados 10 en un pendrive
» 03- Datos y tipos de datos
» EE UU recurre a una gran conspiración para minar la privacidad en Internet
» McAfee reveló un masivo pero silencioso ataque informático
» Por qué el jefe de seguridad tiene razón
» Seguridad en el aire
» Software gratis: los programas que no deben faltar en la PC
» TEORIA EN PDF
NUBE DE TAGS  [?]
AL MARGEN
¡Bienvenidos!
Este será un canal de comunicación entre nosotros.
Tendrá diferentes instancias dinamizadoras, y utilidades para trabajar los diferentes trabajos prácticos en diversas modalidades.
BUSCADOR
Blog   Web
SE COMENTA...
» Seguridad en el aire
2 Comentarios: uk vpn, uk vpn
FULLServices Network | Crear blog | Privacidad