metodos de ordenamiento
TRANSCRIPT
1
UNIVERSIDAD AUTÓNOMA DE
CHIAPAS
UNIDAD ACADEMICA:
Programación estructurada
Titulo:
Métodos de ordenamiento en C
(Burbuja, quicksort, shellsort y sort)
Nombre del docente:
MC. Felipe Antonio Román Albores
Presenta:
Efraín Gómez Gómez
Semestre:
2’
GRUPO:
“B”
TUXTLA GUTIERREZ CHIAPAS A 19 de abril del 2013
2
INDICE
Tema pagina
1. Introducción……………………………………………………………….3
2. Ordenación por el método de la burbuja……………………………….4
3. Ordenación por el método quicksort……………………………………6
4. Método de ordenación shellsort…………………………………………8
5. Ordenación Radix sort…………………………………………………...10
6. Archivo fuente métodos de ordenamiento………………………….…12
7. Archivo fuente VariablesExternas.h…………………………………...13
8. Archivo fuente burbuja…………………………………………………..14
9. Archivo fuente quick sort………………………………………………..15
10. Archivo fuente sort……………………………………………………….17
11. Archivo fuente Shell sort………………………………………………...19
12. Conclusión…………………………………………………………………22
13. Bibliografía…………………………………………………………………23
Índice de imágenes
1. Salida en pantalla del menú……………………………………………...20
2. Salida en pantalla del método burbuja…………………………………..21
3. Salida en pantalla del quick sort………………………………………….21
4. Salida en pantalla del sort………………………………………………...21
5. Salida en pantalla del Shell sort………………………………………….22
3
INTRODUCION
Los arreglos son un tipo de estructura que tiene un tamaño definido, el
tamaño de un arreglo es definido a la hora de ser declarado y no se puede
modificar una vez determinado su tamaño. Un arreglo puede tener varias
dimensiones, en el caso del ordenamiento de Sort se ocupa un arreglo de una lista
declarada para poder ordenar los números, este arreglo es de una sola dimensión.
En la siguiente documentación se mostrara mas métodos de ordenamiento
en el leguaje de programación C, para lo cual se investigara en diferentes fuentes
de internet para así aclarar dudas o ver si va de acuerdo a nuestros ejemplos de
programas dadas.
El documento contendrá los siguientes métodos de ordenamiento:
1. Burbuja
2. Quicksort
3. Sort
4. Shell sort
Cada uno de ellos contendrá un ejemplo para así dejar mas en claro estas
definiciones o temas.
4
ORDENACIÓN POR EL MÉTODO DE LA BURBUJA
Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande en la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los numeros desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo.
Este algoritmo es muy deficiente ya que al ir comparando las casillas para
buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.
Entonces:
Dado un vector a1, a2, a3,... an 1) Comparar a1 con a2 e intercambiarlos si a1>a2 (o a1<a2)
2) Seguir hasta que todo se haya comparado an-1 con an 3) Repetir el proceso anterior n-1 veces</a
Algoritmo: Complejidad
for(i=0; i < n-1; i++){ T(n2
)
for(j=0; j < n-1; j++){ T(n)
if(vec[j] > vec[j+1]){ T(1)
aux=vec[j]; T(1)
vec[j]=vec[j+1]; T(1)
vec[j+1]=aux;} T(1)
}
}
El procedimiento de la burbuja es el siguiente:
Ir comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él.
Este procedimiento seguirá así hasta que haya ordenado todas las casillas del vector.
Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.
5
Ejemplo:
Variables Vector
pos 0 1 2 3 4 5 6 7
i j a[j] a[j+1] inicio 44 55 12 42 94 18 6 67
0 1 55 12 cambio 44 12 55 42 94 18 6 67
0 2 55 42 cambio 44 12 42 55 94 18 6 67
0 4 94 18 cambio 44 12 42 55 18 94 6 67
0 5 94 6 cambio 44 12 42 55 18 6 94 67
0 6 94 67 cambio 44 12 42 55 18 6 67 94
1 0 44 12 cambio 12 44 42 55 18 6 67 94
1 1 44 42 cambio 12 42 44 55 18 6 67 94
1 3 55 18 cambio 2 42 44 18 55 6 67 94
1 4 55 6 cambio 12 42 44 18 6 55 67 94
2 2 44 18 cambio 12 42 18 44 6 55 67 94
2 3 44 6 cambio 12 42 18 6 44 55 67 94
3 1 42 18 cambio 12 18 42 6 44 55 67 94
3 2 42 6 cambio 12 18 6 42 44 55 67 94
4 1 18 6 cambio 12 6 18 42 44 55 67 94
5 0 12 6 ordenado 6 12 18 42 44 55 67 94
6
ORDENACION POR EL METODO QUICKSORT
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana. Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así. La idea central de este algoritmo consiste en los siguiente: Se toma un elemento x de una posición cualquiera del arreglo. Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x. Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo. Ejemplo: A: 15, 67, 08, 16, 44, 27, 12, 35 Se selecciona A[i] x=15 Primera pasada (DER-IZQ) A [8] >= x 35 >= 15 No hay intercambio A [7] >= x 12 >= 15 Si hay intercambio A: 12, 67, 08, 16, 44, 27, 15,35 (IZQ-DER) A [2] < = X 67 < = 15 Si hay intercambio A: 12, 15, 08, 16, 44, 27, 67,35 2da. Pasada (DER-IZQ) A [6] >= x 27 >= 15 No hay intercambio A [5] >= x 44 >= 15 No hay intercambio A [4] >= x 16 >= 15 No hay intercambio A [3] >= x 08 >= 15 Si hay intercambio A: 12, 08, 15, 16, 44, 27, 67,35
7
Como el recorrido de izquierda a derecha debería iniciarse en la misma posición donde se encuentra el elemento x, el proceso se termina ya que el elemento x, Se encuentra en la posición correcta. A: 12, 08, 15, 16, 44, 27, 67, 35 1er 2do Conjunto Conjunto 16, 44, 27, 67, 35 X16 (DER-IZQ) A[8]>=x No hay intercambio A[7]>=x No hay intercambio A[6]>=x No hay intercambio A[5]>=x No hay intercambio A: 12, 08, 15, 16, 44, 27, 67, 35 xß44 (DER-IZQ) A [8]>= x Si hay intercambio A: 12, 08, 15, 16, 35, 27, 67, 44 (IZQ-DER)
A[6] < = x No hay intercambio A[7] < = x Si hay intercambio 12, 08, 15, 16, 35, 27, 44, 67 12, 08, 15, 16, 35, 27, 44, 67 35, 27, 44, 67 xß35 (DER-IZQ) A[8] >= x No hay intercambio A[7] >= x No hay intercambio A[6] >= x Si hay intercambio 12, 08, 15, 16, 27, 35, 44, 67 12,08 xß12 (DER-IZQ) A[2]>=x Si hay intercambio EL VECTOR ORDENADO: 08, 12, 15, 16, 27, 35, 44,67
8
MÉTODO DE ORDENACIÓN SHELL
El método Shell pertenece a los métodos de clasificación avanzados,
nombrado así en honor a su desarrollador, Donald Shell.
Este método utiliza una segmentación entre los datos. Funciona
comparando elementos que estén distantes; la distancia entre comparaciones
decrece conforme el algoritmo se ejecuta hasta la última fase, en la cual se
comparan los elementos adyacentes, por esta razón se le llama ordenación por
disminución de incrementos.
La ordenación de Shell usa una secuencia, h1, h2, . . ., ht, conocida como la
secuencia de incrementos. Al principio de todo proceso, se fija una secuencia
decreciente de incrementos. Cualquier secuencia funcionará en tanto que empiece
con un incremento grande, pero menor al tamaño del arreglo de los datos a
ordenar, y que el último valor de dicha secuencia sea 1.
Una elección muy común (pero no tan eficiente) para la secuencia de
incrementos es adoptar la secuencia sugerida por Shell: ht = [n / 2], y hk = [hk+1 /
2]. A continuación se muestra un programa que implanta la ordenación de Shell
usando esta secuencia.
Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
“Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos.”
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.
9
Ejemplo:
Para el arreglo a = [6, 1, 5, 2, 3, 4, 0]
Tenemos el siguiente recorrido:
Recorrido Salto Lista Ordenada Intercambio
1 3 2,1,4,0,3,5,6 (6,2),(5,4),(6,0)
2 3 0,1,4,2,3,5,6 (2,0)
3 3 0,1,4,2,3,5,6 Ninguno
4 1 0,1,2,3,4,5,6 (4,2),(4,3)
5 1 0,1,2,3,4,5,6 Ninguno
10
ORDENAMIENTO RADIX SORT
Radix Sort
Para el ordenamiento con Radix Sort lo primero que se necesita saber es la
cantidad de veces que se aplicará el ordenamiento, esto es igual al número de
dígitos del número con más longitud en la lista.
Ejemplo:
Lista: 31, 75, 560, 1, 62, el número con más dígitos es el 560, que contiene
3 dígitos, por lo tanto se darán 3 vueltas en la ordenación.
Lista: 6, 4, 8, 2, en este caso todos los números son de un dígito entonces
el número mayor de dígitos es 1, por lo tanto se dará solo una vuelta para ordenar.
Después se verifica el primer dígito de derecha a izquierda y se acomoda
dependiendo su valor, este proceso se repite las veces necesarias para el
ordenamiento, es decir, el número mayor de dígitos del número con más longitud
de la lista.
Ejemplo:
Lista de números: 35, 62, 56, 3, 16.
Representación en una lista enlazada:
El número de veces que se repetirá el ordenamiento es 2.
Se toma en cuenta el primer dígito de derecha a izquierda, 35, 62, 56, 3, 16,
estos número se acomodan en un arreglo de listas enlazadas del 0 al 9
dependiendo que valor les corresponda.
11
Se vuelven a juntar los números como haya quedado en una lista enlazada:
Se vuelve a hacer otra vuelta, pero ahora tomando en cuenta el siguiente
dígito, en el caso de que ya no tenga más dígitos a la izquierda se le agrega un
cero imaginario (como en el caso del número 3), 62, 03, 35, 56, 16 y se acomodan
de nuevo en la lista del 0 al 9.
Se junta nuevamente y nos queda:
Esta es la última vuelta por lo tanto los números ya están ordenados.
12
En las paginas anteriores se vieron los conceptos y pruebas manuales de cómo funciona cada método ahora veremos ejemplos ya hechos como programas.
Ejemplo del método burbuja, quick sort, sort y shellsort hecho en Dev c++:
Nota: El programa se hizo como modo proyecto para ahorrar espacio y tiempo en
pruebas y ejecuciones.
archivo fuente METODOS DE ORDENAMIENTO:
Este archivo fuente contiene el menú y las llamadas a las funciones para que se ejecuten según su función.
#include <stdio.h>
#include <conio.h>
#define MAX 5
int opcion;
int datoA;
main()
{ printf("\n<<<<<<<<<<<<<<<<<<<<<<MENU>>>>>>>>>>>>>>>>>>>>>>>>>>>"); printf("\n1.-BURBUJA");
printf("\n2.-QUICKSORT");
printf("\n3.-SORT");
printf("\n4.-SHELLSORT");
printf("\n----->ELIGE UNA OPCION DEL MENU:<-----\n");
scanf("%d",&opcion);
system("cls");
pasodeparametro(datoA);//paso de dato por parametro
getch();
}
pasodeparametro(){ //llamada a la Funcion
if(opcion==1){
printf("\n----->METODO DE ORDENAMIENTO BURBUJA<----------\n\n");
llamarburbuja(); //llamada a la Funcion en VariablesExternas.h
}
13
if(opcion==2){ //llamada a la Funcion
printf("\n----------->METODO DE ORDENAMIENTO QUICKSORT<------------\n\n");
llamarquicksort(); //llamada a la Funcion en VariablesExternas.h
}
if(opcion==3){ //llamada a la Funcion
printf("\n----------------->METODO DE ORDENAMIENTO SORT<---------------\n\n");
llamarsort(); //llamada a la Funcion en VariablesExternas.h
}
if(opcion==4){ //llamada a la Funcion
printf("\n------------->METODO DE ORDENAMIENTO SHELLSORT<------------\n\n");
llamarshellsort(); //llamada a la Funcion en VariablesExternas.h
}
}
Archivo fuente VariablesExternas.h
En este archivo fuente se encuentran declaradas todas las funciones que se harán llamadas para el funcionamiento del programa.
extern void llamarsort();
extern void llamarquicksort();
extern void llamarshellsort();
extern void llamarburbuja();
extern void pasodeparametro();
extern void OrdenQuicksort();
14
Archivo fuente burbuja:
En este archivo fuente se encuentra contenida el proceso que hace el ingreso y
ordenamiento de los datos. Solo se le hace llamad a la función principal llamar
burbuja y este se ejecuta y realiza la operación.
llamarburbuja()
{
int areglo[10];
int i=0; /*indice para ordenar*/
int j=0; /*indice para comparar*/
int numdatos=6; /*total de datos en el vector o areglo*/
int vauxiliar=0;
printf("\n INGRESA 10 NUMEROS: \n");
for (i=0;i<=5;i++)
{
scanf("%d",&areglo[i]);
}
printf("\n \n");
for(i=0;i<numdatos-1;i++) /*ciclo para ordenamiento*/
for(j=0;j<numdatos-1;j++) /*ciclo para comparar*/
if(areglo[j]<areglo[j+1]) /*comparacion, ordenamiento ascendente*/
{
vauxiliar=areglo[j]; //intercambio de valores con indices para el
areglo[j]=areglo[j+1]; //ordenamiento
areglo[j+1]=vauxiliar;
}
printf("\nVECTOR O ARREGLO ORDENADO POR EL METODO BURBUJA:");
for(i=0;i<numdatos;i++)
printf("\n%d",areglo[i]); /*resultado en pantalla*/
getch();
}
15
Archivo fuente quick sort:
En este archivo fuente se encuentra contenida el proceso que hace el ingreso y
ordenamiento de los datos. Solo se le hace llamad a la función principal llamar
quicksort y este se ejecuta y realiza la operación del ordenamiento con el método
quick sort.
int i=0; //indice del vector a conocer int dato=1; void OrdenQuicksort(); //variable indice que manejara los datos de ingreso en pantalla void llamarquicksort(){ int long Arreglo[5]; //arreglo con un tamaño max declarado anteriormente como constante printf("INGRESA 5 DATOS\n\n"); for(i=0;i<5;i++) // ciclo que maneja los ingresos de datos { printf("DATO %d-->",dato); scanf("%d",&Arreglo[i]);//va guardando los datos ingresados en la posicion i del arreglo dato++; //incremento en pantalla de los numeros de datos a pedir } OrdenQuicksort(Arreglo, 0,5-1); /* llamada a la funcion ingresando los parametros indicados, el cero indica en que posicion comenzara a ordenar los datos */ printf("\nDATOS ORDENADOS POR EL METODO QUICKSORT:"); for(i = 0; i < 5; i++) printf("\n%d\n",Arreglo[i]);// imprime en pantalla los numeros ya ordenados getch(); } void OrdenQuicksort(int* arr, int izq, int der) //funcion que hace el procedimiento de arreglo de los numeros { int i = izq, j = der, tmp; /*igualamos las variables (indices,"i","j") y la variablr tmp que sirve para el intercambi de valor*/ int p = arr[(izq + der) / 2];/*declaramos la variable pivote sumando los valores de los extremos y dividimos entre 2 para obtener la media del arreglo*/
16
while (i <= j) { while (arr[i] < p) i++; /*mientras que el valor en la pocision i sea menor que el valor del pivote la variable I se incrementara en 1 */ while (arr[j] > p) j--;/*mientras que el valor en la pocision j sea mayor que el valor del pivote la variable j decrementara */ if (i <= j) { tmp = arr[i]; // en estos 5 linea se haran los intercambios de valores para el ordenamiento arr[i] = arr[j]; //asi quedandonos listo los datos arr[j] = tmp; i++; j--; } } if (izq < j) OrdenQuicksort(arr, izq, j);/*llamada a la funcion Quicksort indicando el parametro a llamar si la condicion se cumple*/ if (i < der) OrdenQuicksort(arr, i, der);/*llamada a la funcion Quicksort indicando el parametro a llamar si la condicion se cumple*/ }
17
Archivo fuente sort: En este archivo fuente se encuentra contenida el proceso que hace el ingreso y
ordenamiento de los datos. Solo se le hace llamad a la función principal llamarsort
y este se ejecuta y realiza la operación del ordenamiento con el método sort.
llamarsort(){
int Arreglo[5]; //declaracion del arreglo
int j=0; /*declaracion de variable global tipo entero*/
int i=0; //indice para el arreglo
int aux=0; //variable auxiliar para el intercambio de
valores
int igreso=0; //variable que maneja los datos que ingrese el
usuario
int numero=0;
int valorA;
printf("INGRESA LA CANTIDAD DE ARREGLOS: ");
scanf("%d", &igreso);
for(i=1;i<=igreso;i++) /*condicion del ingreso de la cantidad de
datos en pantalla*/
{
scanf("%d", &Arreglo[i]);
}
for(numero=igreso;numero>0;numero--) /*ciclo para las condiciones
siguientes*/
{
for(i=1;i<=numero;i++)
{
aux=Arreglo[i];
j=i/2;
while(j>0 && Arreglo[j]<aux)
18
{
Arreglo[i]=Arreglo[j]; /*intercambio de datos para comparar*/
i=j;
j=j/2;
}
Arreglo[i]=aux;
}
valorA=Arreglo[1]; /* comparacion de datos y ordenamiento
con las siguientes lineas*/
Arreglo[1]=Arreglo[numero];
Arreglo[numero]=valorA;
}
printf("\n\nDATOS ORDENADOS POR EL METODO SORT:\n");
for(i=1;i<=igreso;i++)
{
printf("\n%d",Arreglo[i]);
}
getch();
}
19
Archivo fuente Shell sort:
En este archivo fuente se encuentra contenida el proceso que hace el ingreso y
ordenamiento de los datos. Solo se le hace llamad a la función principal
llamarshellsort y este se ejecuta y realiza la operación del ordenamiento con el
método shellsort.
llamarshellsort(){ int Arreglo[5]; /*declaracion del arreglo con una cantidad de caracteres definido */ int n; //variable que guardara los datos de ingreso en pantalla int inicio; int i; //variable contador para incremento de datos en pantalla ej. DATO [X] int j; //variable global que servira para comparar los valores int aux; //variable auxiliar para el ordenamiento printf("CUANTOS DATOD QUIERES INGRESAR: "); scanf("%d",&n); for (i=1; i<=n; i++) //ciclo para el ingreso de datos en pantalla { printf("\nELEMENTO NUMERO %d--> ", i); scanf("%d",&Arreglo[i]); //los datos ingresados en pantalla los ira posicionando el el arreglo i } inicio = n/2; //la cantidad de datos ingresados sera dicidida entre dos y asi sucesivamente while (inicio > 0) //mientras que ninicio sea mayor a cero { for (i = inicio +1; i<=n; i++) //ciclo para comparar los datos ingresados ya divididos
20
{ aux = Arreglo[i]; j=i; while ( (j-inicio) > 0 ) //mientras que el indice j -inicio sea mayor a cero { if (aux < Arreglo[j-inicio]) //condicion del ordenamiento { Arreglo[j]=Arreglo[j-inicio]; //intercamb para ordenamiento j=j-inicio; } else break; } // fin del while Arreglo[j]=aux; } // fin del for inicio = inicio/2; } // fin del while printf("\n"); printf("\nDATOS ORDENADOS POR EL METODO SHELLSORT\n"); for (i=1; i<=n; i++) printf("\n%d", Arreglo[i]); getch(); }
Salida en pantalla del menu:
21
Salida en pantalla del método burbuja:
Salida en pantalla del quick sort:
Salida en pantalla del sort:
22
Salida en pantalla del shell sort:
CONCLUSIÓN
En conclusión estos métodos de ordenamiento que se mostraran
anteriormente es una manera fácil o practico de cómo ordenar ciertos datos en un
arreglo, en este caso solo hicimos mención de cuatro de ellas, tendré que recalcar
que no solo estos cuatro métodos existen si no que hay más de estas pero nos
enfocamos principalmente en cuatro que son las que ya vimos en las paginas
anteriores.
Para dar fin a esta documentación les agradezco la atención prestada
afirmando así los conocimientos adquiridos en este trabajo, por mencionar algunas
al manejo de los for anidados cosa que yo no sabía muy bien y también algunos
detalles sobre arreglos.
Así pues dejo por concluido este tema
23
BIBLIOGRAFIA
Codifícalo. Programando. Disponible en: http://codificalo.com/index.php/categorias/8-estructuras-de-datos/4-ordenamiento-radix-sort consulta [2013 18 abril]
Wikipedia. Metododeordenamiento. Disponible en: http://es.wikipedia.org/wiki/Ordenamiento_Radix consulta[2013 18 abril]
Galeón. Disponible en: http://www.estructuradedatos.galeon.com/burbujatext.htm Consulta [2013 18 abril]
Angel fire. Disponible en: http://www.angelfire.com/wy2/est_info/quicksort.html Consulta [2013 18 abril]
Al rincón del vago. Métodos de ordenamiento. Disponible en: http://html.rincondelvago.com/ordenacion-por-shell.html Consulta [2013 18 abril]
DOTNETCR. Disponible en: http://www.dotnetcr.com/metodo-de-ordenamiento-shell/ Consulta [2013 18 abril]