Alumno: Ivo Andrés Astudillo Bustamante
Ordenamiento
El propósito principal de un ordenamiento es el de facilitar las búsqueda de los elementos que se encuentran en un arreglo.
Criterios de Ordenamiento:
Ordenamiento por Intercambio o Burbuja.
Ordenamiento por Selección.
Ordenamiento por Inserción.
Ordenamiento por Intercambio o Burbuja:
El método de intercambio se basa en comparar los elementos del
arreglo e intercambiarlos si su posición actual o inicial es contraria
inversa a la deseada. Pertenece a este método el de la burbuja
clasificado como intercambio directo. Aunque no es muy eficiente para
ordenar listas grandes, es fácil de entender y muy adecuado para ordenar
una pequeña lista de unos 100 elementos o menos.
Una pasada por
la ordenación de burbujeo consiste en un recorrido completo a través del
arreglo, en el que se comparan los contenidos de las casillas
adyacentes, y se cambian si no están en orden. La ordenación por
burbujeo completa consiste en una serie de pasadas ("burbujeo") que
termina con una en la que ya no se hacen cambios porque todo está en
orden.
Ordenamiento por Selección:
Los métodos de ordenación por selección se basan en dos principios básicos:
Seleccionar el elemento más pequeño (o más grande) del arreglo.
Colocarlo en la posición más baja (o más alta) del arreglo.
A
diferencia del método de la burbuja, en este método el elemento más
pequeño (o más grande) es el que se coloca en la posición final que le
corresponde.
Ordenamiento por Inserción:
El fundamento de este método consiste en insertar los elementos no
ordenados del arreglo en subarreglos del mismo que ya estén ordenados.
Dependiendo del método elegido para encontrar la posición de inserción
tendremos distintas versiones del método de inserción.
BÚSQUEDA
La búsqueda es una operación que tiene por objeto la localización de
un elemento dentro de la estructura de datos. A menudo un programador
estará trabajando con grandes cantidades de datos almacenados en
arreglos y pudiera resultar necesario determinar si un arreglo contiene
un valor que coincide con algún valor clave o buscado.
Siendo el
array de una dimensión o lista una estructura de acceso directo y a su
vez de acceso secuencial, encontramos dos técnicas que utilizan estos
dos métodos de acceso, para encontrar elementos dentro de un array:
búsqueda lineal y búsqueda binaria.
Tipos de Búsqueda:
Búsqueda Binaria.
Búsqueda Lineal.
Búsqueda Binaria:
Para poder ejecutar el Método de Búsqueda Binaria, se debe de contar con un Array ordenado.
El procedimiento que se realiza es el siguiente:
- El Programa internamente selecciona el elemento central del Array.
- Si el elemento a buscar es el dato central el proceso termina.
- Si el elemento a buscar no coincide con el elemento central, continua la búsqueda:
- Se subdivide en dos partes al Array.
- Si el elemento a buscar es menor que el dato central, entonces selecciona la mitad de la parte izquierda.
- La parte seleccionada se subdivide nuevamente y se repite todo el proceso.
- El proceso termina cuando el dato es encontrado.
Búsqueda Lineal:
La búsqueda secuencial es la técnica más simple para buscar un
elemento en un arreglo. Consiste en recorrer el arreglo elemento a
elemento e ir comparando con el valor buscado (clave). Se empieza con la
primera casilla del arreglo y se observa una casilla tras otra hasta
que se encuentra el elemento buscado o se han visto todas las casillas.
El resultado de la búsqueda es un solo valor, y será la posición del
elemento buscado o cero. Dado que el arreglo no está en ningún orden en
particular, existe la misma probabilidad de que el valor se encuentra ya
sea en el primer elemento, como en el último. Por lo tanto, en
promedio, el programa tendrá que comparar el valor buscado con la mitad
de los elementos del arreglo.
El método de búsqueda lineal
funciona bien con arreglos pequeños o para arreglos no ordenados. Si el
arreglo está ordenado, se puede utilizar la técnica de alta velocidad de
búsqueda binaria, donde se reduce sucesivamente la operación eliminando
repetidas veces la mitad de la lista restante.
Biografia:
- http://www.programandoconjava.es.tl/Metodos-De-Busqueda-y-Orenacion.htm
- http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
No hay comentarios:
Publicar un comentario