CONSULTA TIPOS DE ORDENAMIENTO Algoritmo Burbuja Bubble Sort recorre el arreglo intercambiando los elementos adyacentes que estn

desordenados. Recorre el arreglo tantas veces hasta que ya no haya cambios. Prcticamente lo que hace es tomar el elemento mayor y lo coloca en las ltimas posiciones o tomar el menor y colocarlo en las primeras posiciones. CDIGO EN C++ void burbuja(void) { int x, z, aux, ARREGLO[N]; x = 0; while(x < N) { z = N; while(z >= 0) { if(ARREGLO[z] < ARREGLO[z - 1]) { aux = ARREGLO[z]; ARREGLO[z] = ARREGLO[z - 1]; ARREGLO[z - 1] = aux; } z--; } x++; } } Tiempo de ejecucin: El ciclo interno se ejecuta n veces. El ciclo externo tambin se ejecuta n veces, la complejidad es n * n = O(n2). Elcomportamiento del caso promedio depende del orden de entrada de los datos, pero es slo un poco mejor que el del peor caso, y sigue siendo O(n2). Estabilidad: No intercambia registros con claves iguales.

Pablo Salazar

Ventajas:

Fcil implementacin. No requiere memoria adicional.

Desventajas:

Muy lento. Muchas comparaciones. Muchos intercambios. Algoritmo Insercin

Este mtodo consiste en insertar un elemento en una parte ya ordenada del vector y comenzar de nuevo con los elementos restantes. Este tambin es un algoritmo lento, pero puede ser de utilidad para listas semiordenadas, pues en ese caso realiza pocos desplazamientos. CDIGO EN C++ void insercion(void) { int x,z, aux, ARREGLO[N]; bool b; for(x = 1; x < N; x++) { aux = ARREGLO[x]; z = x - 1; flag = false; while(b == false && z >= 0) { if(aux < ARREGLO[z]) { ARREGLO[z + 1] = ARREGLO[z]; z--; } else b = true; }

Pablo Salazar

ARREGLO[z + 1] = aux; } } Ejemplo: [0] [1] 15 15 10 10 10 10 10 10 15 15 15 14 14 15 15 15 15 15 15 7 10 10 10 10 14 14 11 11 14 14 14 14 15 15 15 15 15 10 11 10 11 11 14 10 7 10 10 11 11

[2]

14 14 14

14 14 15

[3]

11 11 11 11 11 11

14 14

[4]

7 2

7 3

7 7 4

15

15 15 5

X Z B

1 0 F -1

1 F 14

0 T

2 F 11

0 T

3 F 7

-1

4 F ?

AUX 10

Tiempo de Ejecucin: Para una lista de n elementos el ciclo externo se ejecuta n-1 veces. El ciclo interno se ejecuta como mximo 1, 2, 3 veces a la tercera iteracin, etc., esto tratndose del pero caso posible. Esto produce una complejidad O(n2). Estabilidad: No intercambia registros con claves iguales. Por lo tanto es estable. Ventajas:

Fcil implementacin. Requerimientos mnimos de memoria.

Desventajas:

Pablo Salazar

Lento. Numerosas comparaciones. Algoritmo Seleccin

El mtodo de ordenamiento por seleccin consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que est en la primera posicin y as excluirlo de la lista. Luego el segundo mas pequeo, y as sucesivamente hasta ordenar todo el arreglo. Es un algoritmo lento, a pesar que slo realiza un intercambio en cada ejecucin del ciclo externo, puede ser una buena eleccin para listas con registrosgrandes y claves pequeas. CDIGO EN C++ void seleccion(void) { int i, j, min, ARREGLO[N], aux; i=0 while(i < N) { min = i; j = i + 1; while (j < N) { if(ARREGLO[j] < ARREGLO[i]) { min = j; aux = ARREGLO[i]; ARREGLO[i] = ARREGLO[min]; ARREGLO[min] = aux; } j++; } i++; } }

Pablo Salazar

Ejemplo: [0] [1] [2] [3] [4] 15 10 10 10 15 15 14 11 7 I J MIN 0 1 0 0 1 0 0 2 1 0 3 1 0 4 4 14 11 7 14 11 7 10 15 14 11 7 7 15 14 11 7 7 7 7 7 7 10 7 10 7 10 7 10 11 7 10 11

15 14 11 10 10 14 15 15 11 15

15 14 11 11 14 15 15

11 14 14 10

15 14 14

10 10 1 2 1

10 11 11

11 14 14 15 15 2 3 3 2 4 4 3 4 3 3 4 4 4 5 4

1 2 2

1 3 3

1 4 4

2 3 2

Tiempo de Ejecucin: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada bsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Estabilidad: Puede que haya algo de discrepancia pero esta implementacin parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable. Ventajas:

Fcil implementacin. No requiere memoria adicional. Realiza pocos intercambios. Rendimiento constante: poca diferencia entre el peor y el mejor caso.

Desventajas:

Lento. Realiza numerosas comparaciones.

Pablo Salazar

Ejemplo #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <dos.h> #define MAX 100

//Prototipos. void burbuja(int a[],int n); void burbujam(int a[],int n); void insercion(int a[],int n); void seleccion(int a[],int n);

int numelem(); void tipocap(int a[],int n); void captura(int a[],int n); void capinsercion(int a[],int n); void caleat(int a[],int n); void ver(int a[],int n); char menu(); int mcap();

//Principal. void main(){

Pablo Salazar

int a[MAX],b[MAX],c[MAX],n,m,k; int salir=0; do { switch(menu()){ case 'a': case 'A': clrscr(); n=numelem(); tipocap(a,n); clrscr(); printf("Su Arreglo:\n"); ver(a,n); printf("\n\nPresione Cualquier Tecla, "); printf("Para Comenzar Ordenamiento..."); getch(); burbuja(a,n); clrscr(); printf("Arreglo ordenado:\n"); ver(a,n); getch(); break; case 'b': case 'B': clrscr();

Pablo Salazar

n=numelem(); tipocap(a,n); clrscr(); printf("Su Arreglo:\n"); ver(a,n); printf("\n\nPresione Cualquier Tecla, "); printf("Para Comenzar Ordenamiento..."); getch(); clrscr(); burbujam(a,n); clrscr(); printf("Arreglo ordenado:\n"); ver(a,n); getch(); break; case 'c': case 'C': clrscr(); n=numelem(); capinsercion(a,n); clrscr(); printf("Arreglo ordenado:\n"); ver(a,n); getch();

Pablo Salazar

break; case 'd': case 'D': clrscr(); n=numelem(); tipocap(a,n); clrscr(); printf("Su Arreglo:\n"); ver(a,n); printf("\n\nPresione Cualquier Tecla, "); printf("Para Comenzar El Ordenamiento..."); getch(); seleccion(a,n); clrscr(); printf("Arreglo ordenado:\n"); ver(a,n); getch(); break; case 's': case 'S': salir=1; break; default: printf("Opcion No Valida.");

Pablo Salazar

getch(); break; } }while(salir!=1); clrscr();

//Funciones de Prototipos. void tipocap(int a[],int n){ switch(mcap()){ case 1: captura(a,n); break; case 2: caleat(a,n); break; } }

void capinsercion(int a[],int n){ int i; for(i=0;i<n;i++){ a[i]=20000;

Pablo Salazar

} for(i=0; i<n; i++){ printf("Elemento %d: ", i+1); scanf("%d",& a[i]); insercion(a,n); } } char menu(){ char opc; clrscr(); printf("Menu de Metodos de Ordenamiento.\n\n"); printf("a) Burbuja Simple.\nb) Burbuja Mejorada.\n"); printf("c) Insercion.\nd) Seleccion.\n"); printf("\ns) Salir.\n\nMetodo a Utilizar: "); fflush(stdin); scanf("%c", &opc); return(opc); }

int mcap(){ int cap; clrscr(); printf("Modo de Captura.\n\n"); printf("1) Manual.\n2) Aleatoria.\n");

Pablo Salazar

printf("\nCaptura de forma: "); scanf("%d", &cap); return(cap); }

int numelem(){ int elems; clrscr(); printf("Numero de elementos: "); scanf("%d", &elems); return(elems); }

void captura(int a[],int n){ int i; for(i=0;i<n;i++){ printf("Elemento %d: ",i+1); scanf("%d", &a[i]); } }

void caleat(int a[], int n){ int i; randomize();

Pablo Salazar

for(i=0;i<n;i++){ a[i]=(rand()%100); } }

void ver(int a[], int n){ int i; for(i=0;i<n;i++){ printf("Elemento %d: %d\n",i+1, a[i]); }

void burbuja(int a[],int n){ int i,j,k=0,aux; for(i=0;i<=n;i++){ clrscr(); printf("Pasada N%d\n",k); k++; for(j=0;j<n-i;j++){ if(a[j]>a[j+1]){ aux=a[j]; a[j]=a[j+1]; a[j+1]=aux;

Pablo Salazar

} printf("\n"); ver(a,n); } } }

void burbujam(int a[],int n){ int i,j=0,band=1,aux; while(j<n && band==1){ band=0; for(i=0;i<n;i++){ if(a[i]>a[i+1]){ aux=a[i]; a[i]=a[i+1]; a[i+1]=aux; band=1; } } printf("\nPasada N%d\n",j); ver(a,n); j++; } }

Pablo Salazar

void insercion(int a[],int n){ int i,j,aux; for(i=1; i<n; i++){ j=i; aux=a[i]; while(j>0 && aux<a[j-1]){ a[j]=a[j-1]; j--; } a[j]=aux;

} printf("Los Elementos son:\n "); for(j=0; j<n; j++) printf("%d\n ",a[j]); getch(); clrscr(); }

void seleccion(int a[],int n){ int i=0,j=0,x=0,im,aux;

Pablo Salazar

for(i=0;i<n-1;i++){ x++; im=i; for(j=i+1;j<n;j++){ if(a[j]<a[im]){ im=j; } } aux=a[i]; a[i]=a[im]; a[im]=aux; clrscr(); printf("Pasada N%d:\n",x); ver(a,n); } }

Pablo Salazar