ndicendice Pgina 2 Resumen Introduccin Pgina 4 Desarrollo Pgina
5 Pgina 3
METODO DE BURBUJA Pgina 5
METODO SHELL SORTPgina 5
METODO QUICK SORTPgina 6
METODO DE SELECCION DIRECTA METODO DE RADIX METODO DE MERGE SORT
(o MEZCLA) METODO DE SHAKE SORT (o SACUDIDA) METODO DEL HEAP SORT
(o MONTICULO) METODO INSORT (o INSERCION DIRECTA)Bibliografa Anexos
documentales
Pgina 6 Pgina 7 Pgina 7 Pgina 7 Pgina 7 Pgina 8 Pgina 9 Pgina 10
Pgina 10
Cdigo
ResumenInforme de Investigacin que presenta un cdigo que
desarrolla separados por funciones los siguientes nueve mtodos de
ordenamiento:
1. METODO DE BURBUJA2. METODO SHELL SORT 3. METODO QUICK SORT 4.
METODO DE SELECCION DIRECTA 5. METODO DE RADIX 6. METODO DE MERGE
SORT (o MEZCLA) 7. METODO DE SHAKE SORT (o SACUDIDA) 8. METODO DEL
HEAP SORT (o MONTICULO) 9. METODO INSORT (o INSERCION DIRECTA)
2
IntroduccinSegn la prestigiosa biblioteca Wikipedia, los mtodos
de ordenamiento son: En computacin y matemticas un algoritmo de
ordenamiento recursivo es un algoritmo que pone elementos de una
lista o un vector en una secuencia dada por una relacin de orden,
es decir, el resultado de salida ha de ser una permutacin de la
entrada que satisfaga la relacin de orden dada. En base a esta
descripcin es que nosotros como grupo desarrollaremos un cdigo en
el lenguaje de programacin C que desarrolle diferentes algoritmos
de ordenamiento utilizando vectores y funciones como parte del
cdigo y que ordene diferentes nmeros.
3
DesarrolloMETODO DE BURBUJA El algoritmo de ordenacin por el
mtodo de la burbuja, tambin conocido como intercambio directo, es
uno de los ms simples que se conocen. Se basa en una serie de
intercambios entre elementos adyacentes. Esos intercambios dan la
impresn de que cada elemento va ascendiendo a travs del array
acercndose cada vez ms a su posicin final, recordando a cmo
ascienden las burbujas de gas en un lquido. A efectos prcticos, el
algoritmo de la burbuja no es adecuado prcticamente para ninguna
situacin, ya que realiza muchas comparaciones y muchos
intercambios. Los hay similares que se comportan bastante mejor. Su
inters es ms bien terico, ya que sirve para establecer comparativas
con otros mtodos y extraer conclusiones tericas. No obstante, es un
algoritmo sencillo y vistoso que se sigue viendo en casi cualquier
curso o asignatura de programacin. Muchos profesores prefieren no
perder tiempo con este algoritmo en las clases de programacin...
bueno... quiz sea una decisin acertada. Sin embargo, es uno de los
imprescindibles en algoritmia... as que vamos a echarle un vistazo.
Este algoritmo se basa en hacer comparaciones, as que para que
realice su trabajo de ordenacin son imprescindibles dos cosas: un
array o estructura similar de elementos comparables y un criterio
claro de comparacin, tal que dados dos elementos nos diga si estn
en orden o no. (ver Algoritmos de ordenacin). Es un algoritmo
estable de ordenacin interna, y su complejidad temporal en el peor
caso es de O(n2), mientras que en el mejor caso -que el array ya
est totalmente ordenado- puede llegar a (n) siendo n el tamao del
array a ordenar. En cuanto a la complejidad espacial, es muy
ahorrativo: tan solo necesita una variable temporal para realizar
los intercambios, as que su gasto de memoria es constante, sea cual
sea el tamao del array. El algoritmo consiste en realizar varias
pasadas sobre el array, logrando que en cada pasada el elemento de
mayor valor se coloque al final del array. Para lograrlo, en cada
pasada es necesario recorrer el array realizando comparaciones e
intercambios. Por eso, se suele implementar con dos bucles, uno
anidado dentro del otro. El bucle exterior realiza las pasadas y el
interior recorre el array realizando comparaciones e intercambios.
METODO SHELL SORT Es un algoritmo de ordenacin interna muy sencillo
pero muy ingenioso, basado en comparaciones e intercambios, y con
unos resultados radicalmente mejores que los que se pueden obtener
con el mtodo de la burbuja, el de seleccin directa o el de insercin
directa. Aunque a menudo, es un algoritmo un tanto olvidado por dos
motivos: en primer lugar, en los cursos bsicos de programacin se
suele pasar por alto o se pasa "de puntillas" por este algoritmo,
dado que su comprensin requiere un cierto esfuerzo y algo de
tiempo, y se suele centrar la atencin en los tres algoritmos ms
bsicos (burbuja, seleccin e insercin); y en segundo lugar, el
algoritmo QuickSort, desarrollado por Hoare en 1962 puede dar
mejores resultados an que ste, con lo cual, le suele hacer bastante
sombra en los temarios de los cursos de programacin bsicos. Sin
embargo, es necesario romper una lanza a favor del algoritmo
ShellSort, ya que es el mejor algoritmo de ordenacin in-situ... es
decir, el mejor de aquellos en los que la cantidad de memoria
adicional que necesita -aparte de los propios datos a ordenar,
claro est- es constante, sea cual sea la cantidad de datos a
ordenar. El algortimo de la burbuja, el de seleccin directa, el de
insercin directa y el de Shell son todos in-situ, y
4
ste ltimo, el de Shell, es el que mejor resultados da, sin
ninguna duda de todos ellos y sus posibles variantes. Por supuesto
que otros mtodos de ordenacin, como QuickSort, BinSort, HeapSort o
RadixSort pueden pueden superar a ShellSort en cuanto al tiempo de
ejecucin, pero ninguno de ellos es ya un algoritmo in-situ. En
todos ellos es necesario gestionar una cantidad adicional de
memoria proporcional al tamao de los datos a ordenar... METODO
QUICK SORT Este mtodo se basa en la tctica divide y vencers, que
consiste en ir subdividiendo el arreglo en arreglos ms pequeos, y
ordenar stos. Para hacer esta divisin, se toma un valor del arreglo
como pivote, y se mueven todos los elementos menores que este
pivote a su izquierda, y los mayores a su derecha. A continuacin se
aplica el mismo mtodo a cada una de las dos partes en las que queda
dividido el arreglo. Normalmente se toma como pivote el primer
elemento de arreglo, y se realizan dos bsquedas: una de izquierda a
derecha, buscando un elemento mayor que el pivote, y otra de
derecha a izquierda, buscando un elemento menor que el pivote.
Cuando se han encontrado los dos, se intercambian, y se sigue
realizando la bsqueda hasta que las dos bsquedas se encuentran.
METODO DE SELECCION DIRECTA Se basa en realizar varias pasadas,
intentando encontrar en cada una de ellas el elemento que segn el
criterio de ordenacin es mnimo y colocndolo posteriormente en su
sitio. A efectos prcticos, no suele dar resultados buenos si se
compara con otros mtodos de ordenacin. Realiza una enorme cantidad
de comparaciones, pero en contrapartida, muy pocos intercambios.
Eso hace que su utilizacin se restrinja en general a dos
situaciones: o bien necesitamos un algoritmo sencillito para
ordenar unos pocos datos y cogemos ste mismo que no est mal y es
facil de recordar, o bien tenemos una situacin en la cual escribir
en el array es mucho ms gravoso que leer, como puede ser un
escenario en el que intervengan determinados dispositivos de
almacenamiento o memorias tipo flash, eeprom, etc. para el soporte
de los datos. Este algoritmo se basa en hacer comparaciones, as que
para que realice su trabajo de ordenacin son imprescindibles dos
cosas: un array o estructura similar de elementos comparables y un
criterio claro de comparacin, tal que dados dos elementos nos diga
si estn en orden o no. (ver Algoritmos de ordenacin). Es un
algoritmo no estable de ordenacin interna y su complejidad temporal
en el peor caso es de O(n2) y en el mejor caso -que el array ya est
totalmente ordenado- pues tambin es (n2) siendo n el tamao del
array a ordenar... el caso es que ste algoritmo siempre hace el
mismo nmero de comparaciones e intercambios para un n dado... as
que no aprovecha una posible ordenacin parcial del array. En cuanto
a la complejidad espacial, es muy ahorrativo: tan solo necesita una
variable temporal para realizar los intercambios, as que su gasto
de memoria es constante, sea cual sea el tamao del array. Aunque se
suele utilizar para ordenacin interna, puede usarse para ordenacin
externa si nos es imprescindible una complejidad espacial constante
y muy baja. Esa situacin no suele darse, excepto, quiz, en pequeos
dispositivos dotados de una cantidad de memoria principal muy muy
reducida y en los que adems, los datos estn en un soporte cuya
lectura sea mucho ms rpida que la escritura. El algoritmo consiste
en realizar varias pasadas sobre el array, logrando que en cada
pasada el elemento de menor valor se coloque al principio del array
en un solo intercambio. En cada pasada se recorre la parte no
ordenada del array realizando comparaciones con objeto de buscar el
elemento de menor valor. Una vez localizado, se intercambia por el
primer elemento de la parte no ordenada, y entonces ya est en
5
orden. Por eso, se suele implementar con dos bucles, uno anidado
dentro del otro. El bucle exterior realiza las pasadas y el
interior localiza el menor elemento. METODO DE RADIX Este algoritmo
se basa en ordenar las llaves de forma tal que todas las que
inicien con un bit en 0 aparezcan antes que todas las que inicien
con un bit en 1 y proceder sucesivamente con el resto de los bits
mientras queden elementos pendientes de ordenar. Esto da lugar a un
algoritmo recursivo. Para reordenar el arreglo inspeccionar
comenzando por la izquierda hasta encontrar una llave que empiece
con un bit en 1, despus inspeccionar por la derecha hasta encontrar
una llave que empiece con un bit en 0, intercambiar las llaves y
continuar hasta que se crucen los apuntadores de ambas
inspecciones. METODO DE MERGE SORT (o MEZCLA) Una tcnica muy
poderosa para el diseo de algoritmos es Dividir para conquistar.
Los algoritmos de este tipo se caracterizan por estar diseados
siguiendo estrictamente las siguientes fases: Dividir: Se divide el
problema en partes ms pequeas. Conquistar: Se resuelven
recursivamente los problemas ms chicos. Combinar: Los problemas mas
chicos de combinan para resolver el grande. Los algoritmos que
utilizan este principio son en la mayora de los casos netamente
recursivos como es el caso de mergesort. El algoritmo de Mergesort
es un ejemplo clsico de algoritmo que utiliza el principio de
dividir para conquistar. Si el vector tiene ms de dos elementos se
lo divide en dos mitades, se invoca recursivamente al algoritmo y
luego se hace una intercalacin de las dos mitades ordenadas. METODO
DE SHAKER SORT (o SACUDIDA) En este algoritmo cada pasada tiene dos
etapas. En la primera etapa (Que se efectua de derecha a izquierda)
se trasladan los elementos ms pequeos hacia la parte izquierda del
arreglo, almacenando en una variable la posicin del ltimo elemento
intercambiado. En la segunda pasada (Que se efecta de izquierda a
derecha) se trasladan los elementos ms grandes hacia la parte
derecha del arreglo, almacenando en otra variable la posicin del
ltimo elemento intercambiado. Luego se siguen efectuando nuevos
barridos comprendidos entre las posiciones almacenadas en las
variables. El algoritmo termina cuando en una etapa no se producen
intercambios o bien cuando el contenido de la variable que almacena
el extremo izquierdo del arreglo es mayor que el contenido de la
variable que almacena el extremo derecho. METODO DEL HEAP SORT (o
MONTICULO) El ordenamiento por montculos (heapsort en ingls) es un
algoritmo de ordenamiento no recursivo, no estable, concomplejidad
computacional Este algoritmo consiste en almacenar todos los
elementos del vector a ordenar en un montculo (heap), y luego
extraer el nodo que queda como nodo raz del montculo (cima) en
sucesivas iteraciones obteniendo el conjunto ordenado. Basa su
funcionamiento en una propiedad de los montculos, por la cual, la
cima contiene siempre el menor elemento (o el mayor, segn se haya
definido el montculo) de todos los almacenados en l. METODO INSORT
(o INSERCION DIRECTA)6
Se basa en intentar construir una lista ordenada en el interior
del array a ordenar. De estos tres algoritmos es el que mejor
resultado da a efectos prcticos. Realiza una cantidad de
comparaciones bastante equilibrada con respecto a los intercambios,
y tiene un par de caractersticas que lo hacen aventajar a los otros
dos en la mayor parte de las situaciones. Este algoritmo se basa en
hacer comparaciones, as que para que realice su trabajo de
ordenacin son imprescindibles dos cosas: un array o estructura
similar de elementos comparables y un criterio claro de comparacin,
tal que dados dos elementos nos diga si estn en orden o no. (ver
Algoritmos de ordenacin). Es un algoritmo estable de ordenacin
interna y su complejidad temporal en el peor caso es de O(n2) y en
el mejor caso -que el array ya est totalmente ordenado- puede
llegar a (n) siendo n el tamao del array a ordenar. El algoritmo
consiste en realizar varias pasadas sobre el array. En cada pasada
se analiza un elemento, y se intenta encontrar su orden relativo
entre los analizados en pasadas anteriores. Con esto se logra ir
manteniendo una lista ordenada constantemente. Cada elemento a
analizar se desplaza por esa lista hasta encontrar su lugar. Cuando
todos los elementos del array han sido analizados, la lista est
completamente ordenada. Esa es una diferencia importante con
BubbleSort y SelectionSort. En ellos, en cada pasada se colocaba
una carta en su sitio definitivo. En InsertionSort, el array no est
totalmente ordenado hasta que el algoritmo termina. Por otro lado,
en cada pasada no se recorre todo el array, sino solo los elementos
analizados y ordenados en pasadas anteriores. Eso convierte a
InsertionSort en un Algoritmo en lnea (online) , es decir, un
algoritmo que no necesita disponer de todos los elementos a ordenar
desde el principio, sino que puede aceptarlos de uno en uno y
procesarlos a medida que los recibe.
7
BibliografaEnciclopedia libre Wikipedia Foro comunitario Foros
del Web Web de consulta Programacin Fcil Pgina web La Tecla de
Escape
8
Anexos#include #include #include #include #include #define max
100 #define MAX 100 struct lista { int numero; struct lista *sig;
}; typedef struct lista LISTATYPE; typedef LISTATYPE * LISTAPTR;
void CreaLista (LISTAPTR *); void AVerLaLista (LISTAPTR); void
FreeLista (LISTAPTR *); void MS (int, int, LISTAPTR *); void mezcla
(int, int, int, int, LISTAPTR *); /*PARTE DEL METODO DE MERGE
SORT*/ void mostrar (int A[],int x); void quicksort (int A[], int
inf, int sup); void radixsort(int x[], int n); void shakesort (int
A[], int m); void mostrarshake(int A[],int x); void SortHeap(int[],
int); void BURBUJA(); void SHELL(); void SELDIR(); void QUICK();
void RADIX(); void MERGES(); void SHAKE(); void INSORT(); void
MONTICULO(); main() { int op; do{ printf(" \n"); printf(" METODOS
DE ORDENAMIENTO printf(" \n\n\n"); printf(" \n"); printf("1.-
METODO DE BURBUJA printf("2.- METODO SHELL SORT
printf("3.- METODO QUICK SORT \n"); printf("4.- METODO DE
SELECCION DIRECTA \n"); printf("5.- METODO DE RADIX \n");
printf("6.- METODO DE MERGE SORT (o MEZCLA) \n"); printf("7.-
METODO DE SHAKE SORT (o SACUDIDA) \n"); printf("8.- METODO DEL HEAP
SORT (o MONTICULO) \n"); printf("9.- METODO INSORT (o INSERCION
DIRECTA) \n"); printf("0.- SALIR \n"); printf(" \n");
printf("selecione opcion::"); scanf("%d",&op); switch(op) {
case 1: BURBUJA();break; case 2: SHELL();break; case 3:
QUICK();break; case 4: SELDIR();break; case 5: RADIX();break; case
6: MERGES();break; case 7: SHAKE();break; case 8:
MONTICULO();break; case 9: INSORT();break; case 0:printf("SALIENDO
DEL SISTEMA \n(Presione una tecla para Salir)");break; }getch();
}while(op!=0); } void BURBUJA() { int i,n,m,j,A[max]; cout
