Hola!
Hace mucho que no escribia un post en el foro. Hoy lo hago por varias razones. por dudas y sugerencias.
Estuve viendo el post de ordenacion por el metodo de ma burbuja en C#, para empezar yo soy programador de C. me di cuenta, de que sus implementaciones estan mal, aqui hay un ejemplo:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
char[] array = new char[5];
char b = ' ';
array[0] = '8';
array[1] = '4';
array[2] = '3';
array[3] = '7';
array[4] = '9';
for (int e = 0; e < 5; e++)
{
for (int i = 0; i < 4; i++)
{
if (array[i] < array[i + 1])
{
b = array[i];
array[i] = array[i + 1];
array[i + 1] = b;
}
}
}
Console.WriteLine("Array Colocado de mayor a menor");
Console.Read();
}
}
El codigo anterior es pesimo, de por si la ordenacion de la burbuja es una de las peores para una gran cantidad de elementos, y para colmo todavia la degradan mas.
Estos son mis argumentos:
Con la ordenacion de la burbuja, el numero de comparaciones es siempre
el mismo ya que los dos bucles for se repetiran el numero de veces
especficado, aunque la lista estuviese inicialmente ordenada.
La ordenacion de la burbuja debe realizar:
1/2(n^2-n) comparaciones, donde n es el numero de elementos que hay
que ordenar.
Asi es que reclamenle a su profesor o libro de texto por no instruirlos bien.
Su version de la burbuja, si no me equivoco, esta realizando:
1(n^2-n) comparaciones.
Este es mi codigo:
/*
Fecha: 23-SEP-07.
Programador: Luis C.
Archivo: BURBUJA.C
Funcion: Ordenar una cadena de caracteres introducida desde el teclado en
orden ascendente; haciendo uso de la ordenacion de la burbuja (y otras
variantes de esta); as¡ mismo, se muestra en pantalla el tiempo consumido
por cada una de ellas.
Nota: La primera ordenacion, es tomada del libro de Herbert Schildt (que en
mi opinion es uno de los mejores programadores en lenguaje C) "C Manual de
Referencia" (el mejor libro para aprender C). Las posteriores ordenaciones
son optimizaciones implementadas por mi; para mejorar el tiempo de
ejecucion de las mismas.
Estas ordenaciones pueden utilizarse como base para ordenar estructuras
de datos complejas, realizando las respectivas modificaciones.
*/
#include<stdio.h>
#include<string.h>
#include<time.h>
#define MAX 500
/**************************Prototipos de Funciones**************************/
void burbuja1(char *cad, int max);
void burbuja2(char *cad, int max);
void burbuja3(char *cad, int max);
void burbuja4(char *cad, int max);
/**************************Funcion Principal********************************/
int main(void) {
clock_t inicio, final;
float seg;
int cont;
char cad1[MAX], cad2[MAX], cad3[MAX], cad4[MAX];
clrscr();
printf("\n Introduce una cadena: ");
gets(cad1);
strcpy(cad2,cad1);
strcpy(cad3,cad1);
strcpy(cad4,cad1);
puts("\n Ordenando por el metodo de la burbuja (indice de array)...");
inicio = clock();
burbuja1(cad1,strlen(cad1)-1);
final = clock();
printf(" La cadena ordenada en orden ascendente es: %s",cad1);
printf("\n Tiempo consumido: %.2f segundos", (final-inicio)/CLK_TCK);
puts("\n\n Ordenando por el metodo de la burbuja (aritmetica de punteros)...");
inicio = clock();
burbuja2(cad2,strlen(cad2)-1);
final = clock();
printf(" La cadena ordenada en orden ascendente es: %s",cad2);
printf("\n Tiempo consumido: %.2f segundos", (final-inicio)/CLK_TCK);
puts("\n\n Ordenando por el metodo de la burbuja (recursiva-indice de array)...");
inicio = clock();
burbuja3(cad3,strlen(cad3)-1);
final = clock();
printf(" La cadena ordenada en orden ascendente es: %s",cad3);
printf("\n Tiempo consumido: %.2f segundos", (final-inicio)/CLK_TCK);
puts("\n\n Ordenando por el metodo de la burbuja (recursiva-aritmetica de punteros)...");
inicio = clock();
burbuja4(cad4,strlen(cad4)-1);
final = clock();
printf(" La cadena ordenada en orden ascendente es: %s",cad4);
printf("\n Tiempo consumido: %.2f segundos", (final-inicio)/CLK_TCK);
getch();
return 0;
}
/***********************Ordenacion de la Burbuja****************************/
/**********************Utilizando Indice de Array***************************/
void burbuja1(char *cad, int max) {
int a, b;
for(; max>0; max--)
for(a=0; a<max; a++)
if(cad[a] > cad[a+1]) {
/*intercambio de elementos*/
b = cad[a];
cad[a] = cad[a+1];
cad[a+1] = b;
delay(100); }
}
/***********************Ordenacion de la Burbuja****************************/
/*******************Utilizando aritmetica de punteros***********************/
void burbuja2(char *cad, int max) {
char *a, *b;
char aux;
for(b=cad+max; b>cad; b--)
for(a=cad; a<b; a++)
if(*a > *b) {
/*intercambio de elementos*/
aux = *a;
*a = *b;
*b = aux;
delay(100); }
}
/***********************Ordenacion de la Burbuja****************************/
/*************Utilizando Recursividad e Indice de Array*********************/
void burbuja3(char *cad, int max) {
int i;
char aux;
if(max==0) return;
for(i=1; i<=max; i++)
if(cad[i] < cad[i-1]) {
aux = cad[i];
cad[i] = cad[i-1];
cad[i-1] = aux;
delay(100); }
burbuja3(cad,--max);
}
/***********************Ordenacion de la Burbuja****************************/
/**********Utilizando Recursividad y Aritmetica de Punteros*****************/
void burbuja4(char *cad, int max) {
char aux, *a, *b;
if(max==0) return;
for(a=cad, b=cad+1; a<cad+max; a++, b++)
if(*b < *a) {
aux = *a;
*a = *b;
*b = aux;
delay(100); }
burbuja4(cad,--max);
}
Esta claro que esta ordenacion es la peor de todas, pero la mas facil de implementar.
La primera verion es la mas comunmente implementada.
La segunda version vemos que es mas rapida por el uso de punteros, aqui accedemos a direcciones de memoria, lo que acelera el proceso.
La tercera y cuarta version utiliza recursividad, pense que se iban a ejecutar mas rapido que la normal, pero tardan el mismo tiempo o hasta un poco mas.
Creo que no se puede hacer mas por optimizar esta ordenacion, alguien tiene alguna idea de como?
Eso es todo respecto a la ordenacion de la burbuja.
Autor