ALGORITMOS COMPUTACIONALES U4
Páginas: 12 (2988 palabras)
Publicado: 12 de agosto de 2015
ALGORITMOS DE ORDENAMIENTO Y BUSQUEDA
ALGORITMOS DE ORDENAMIENTO
Ordenamiento es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.Ej. de ordenamientos:
Dir. telefónico, tablas de contenido, bibliotecas y diccionarios, etc.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente. Conviene utilizar un método de ordenamiento cuando se requiere hacer una cantidadconsiderable de búsquedas y es importante el factor tiempo.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos: Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc.).
Los externos: Sonaquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc.).
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en unasecuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas parauna ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956.[1]Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a lavariedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
La más común es clasificar según el lugar donde se realice la ordenación
Algoritmos de ordenamiento interno: en lamemoria del ordenador.
Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si...
ALGORITMOS DE ORDENAMIENTO
Ordenamiento es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.Ej. de ordenamientos:
Dir. telefónico, tablas de contenido, bibliotecas y diccionarios, etc.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente. Conviene utilizar un método de ordenamiento cuando se requiere hacer una cantidadconsiderable de búsquedas y es importante el factor tiempo.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos: Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc.).
Los externos: Sonaquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc.).
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en unasecuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas parauna ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956.[1]Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a lavariedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
La más común es clasificar según el lugar donde se realice la ordenación
Algoritmos de ordenamiento interno: en lamemoria del ordenador.
Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si...
Leer documento completo
Regístrate para leer el documento completo.