Computacion

1.- Defina los siguientes métodos de ordenación: Inserción y Selección
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente esun conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
En el siguiente ejemplo, 32debe ser insertado entre 26 y 47, y por lo tanto 47, 59 y 96 deben ser desplazados.
k+1
11 26 47 59 96 32
11 26 47 59 96
11 26 32 47 59 96
En la implementación computacional, el elemento k+1 va comparándose de atrás para adelante, deteniéndose con el primer elemento menor. Simultáneamente se van haciendo losdesplazamientos.
11 26 47 59 96 32
11 26 47 59 96
11 26 47 59 96
11 26 47 59 96
11 26 32 47 59 96
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
* Buscar el mínimo elemento de la lista
* Intercambiarlo con el primero
* Buscar elmínimo en el resto de la lista
* Intercambiarlo con el segundo
Y en general:
* Buscar el mínimo elemento entre una posición i y el final de la lista
* Intercambiar el mínimo con el elemento de la posición i
De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:
-------------------------------------------------para i=1 hasta n-1
-------------------------------------------------
minimo = i;
-------------------------------------------------
para j=i+1 hasta n
-------------------------------------------------
si lista[j] < lista[minimo] entonces
-------------------------------------------------minimo = j /* (!) */
-------------------------------------------------
fin si
-------------------------------------------------
fin para
-------------------------------------------------
intercambiar(lista[i], lista[minimo])
-------------------------------------------------
fin para

2.- Defina los siguientesmétodos de búsqueda: Secuencial y Binario
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 dela 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 funcionabien 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.
Búsqueda Binaria: Es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento...