ESTRUCTURA DE DATOS

MÉTODOS DE BÚSQUEDA Y ORDENAMIENTO Ordenación y búsqueda, son operaciones básicas en el campo de la documentación y en las que, según señalan las estadísticas, las computadoras emplean la mitad de su tiempo. La ordenación (clasificación) es la operación de organizar un conjunto de datos en algún orden dado, tal como creciente o decreciente en datos numéricos, o bien en orden alfabético directo o inverso. Operaciones típicas de ordenación son: lista de números, archivos de clientes de banco, nombres de una agenda telefónica, etc. En síntesis, la ordenación significa poner objetos en orden (orden numérico para los números y alfabético para los caracteres) ascendente o descendente. La búsqueda de información es, al igual que la ordenación, otra operación muy frecuente en el tratamiento de información.  La búsqueda es una actividad que se realiza diariamente en cualquier aspecto de la vida: búsqueda de palabras en un diccionario, nombres en una guía telefónica, localización

MÉTODO DE SELECCIÓN Este método se basa en buscar el elemento menor del vector y colocarlo en primera posición. Luego se busca el segundo elemento más pequeño y se coloca en la segunda posición, y así sucesivamente. Los pasos sucesivos a dar son: 1. Seleccionar el elemento menor del vector de n elementos. 2. Intercambiar dicho elemento con el primero. 3. Repetir estas operaciones con los n – 1 elementos restantes, seleccionando el segundo elemento; continuar con los n – 2 elementos restantes hasta que sólo quede el mayor.

MÉTODO POR INSERCIÓN Este método consiste en insertar un elemento en el vector en una parte ya ordenada de este vector y comenzar de nuevo con los elementos restantes. Por ser utilizado generalmente por los jugadores de cartas se le conoce también por el nombre de método de la baraja.

MÉTODO DE INTERCAMBIO Burbuja u ordenamiento por intercambio, intercambia todo par de elementos consecutivos que no se encuentran en orden. Al final de cada pasada haciendo este intercambio, un nuevo elemento queda ordenado y todos los demás elementos se acercaron a su posición final. Se llama burbuja porque al final de cada iteración el mayor va surgiendo al final.

MÉTODO SHELL Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “Shell” —en honor de su inventor Donald Shell— y también método de inserción con incrementos decrecientes. En el método de clasificación por inserción cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño —por ejemplo—, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modificó los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de más de una posición.

BÚSQUEDA SECUENCIAL La búsqueda secuencial o lineal, consiste en recorrer y examinar cada uno de los elementos del arreglo, mediante un bucle voraz de izquierda a derecha, hasta encontrar el o los elementos buscados, o hasta que se han evaluado todos los elementos del arreglo. Supongamos una lista de elementos almacenados en un vector (array unidimensional). El método más sencillo de buscar un elemento en un vector es explorar secuencialmente el vector o, dicho en otras palabras, recorrer el vector desde el primer elemento al último. Si se encuentra el elemento buscado, visualizar un mensaje similar a 'Fin de búsqueda'; en caso contrario, visualizar un mensaje similar a 'Elemento no existe en la lista'.

BÚSQUEDA BINARIA Si los elementos sobre los que se realiza la búsqueda están ordenados, entonces podemos utilizar un algoritmo de búsqueda mucho más rápido que el secuencial: la búsqueda binaria. Consiste en reducir en cada paso el ámbito de búsqueda a la mitad de los elementos, basándose en comparar el elemento a buscar con el elemento que se encuentra en la mitad del intervalo y con base en esta comparación: ·                Si el elemento buscado es menor que el elemento medio, entonces sabemos que elemento está en la mitad inferior de la tabla.            Si es mayor es porque el elemento está en la mitad superior.         Si es igual se finaliza con éxito la búsqueda ya que se ha encontrado el elemento. Si se vuelve a repetir el mismo proceso anterior con la parte del arreglo que no hemos descartado, iremos avanzando rápidamente hacia el valor que queremos localizar. Puede darse el caso en el que el sub-arreglo a dividir está vacío y aún no se ha enco

ORDENACIÓN RÁPIDA (QUICKSORT) Este algoritmo divide en array en dos subarray, que se pueden ordenar de modo independiente. Se selecciona un elemento específico del array arreglo[centro] llamado pivote. Luego, se debe re situar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. Finalmente, se divide el array original en dos subarrays que se ordenarán de modo independiente mediante llamadas recursivas del algoritmo.

      ALGORITMO QUICKSORT La primera etapa en el algoritmo de partición es obtener el elemento pivote; una vez que se ha seleccionado se ha de buscar el sistema para situar en la sublista izquierda todos los elementos menores que el pivote y en la sublista derecha todos los elementos mayores que el pivote. Supongamos que todos los elementos de la lista son distintos, aunque será preciso tener en cuenta los casos en que existan elementos idénticos.         

              MÉTODO DE BINSORT Este método, también llamado clasificación por urnas, persigue conseguir funciones de tiempo de ejecución menores de O(n log n), para ordenar una secuencia de n elementos siempre que se conozca algo acerca del tipo de las claves por las que se están ordenando. Supóngase que se tiene un vector v[] de registros, se quiere ordenar respecto un campo clave de tipo entero, además se sabe que los valores de las claves se encuentran en el rango de 1 a n, sin claves duplicadas y siendo n el número de elementos. En estas circunstancias es posible colocar los registros ordenados en un array auxiliar t[] mediante este bucle: for 1:= 1 to n do        t[v[i].clave] = v[i]; Sencillamente determina la posición que le corresponde según el valor del campo clave. El bucle lleva un tiempo de ejecución de complejidad O(n). Esta ordenación tan sencilla que se ha expuesto es un caso particular del método de ordenación por urnas (binsort). Este método

     MÉTODO DE RADIXSORT Este método puede considerarse como una generalización de la clasificación por urnas. Aprovecha la estrategia de la forma más antigua de clasificación manual, consistente en hacer diversos montones  de fichas, cada uno caracterizado por tener sus componentes un mismo dígito (letra, si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte de nuevo en montones según el siguiente dígito de la clave.

Archivos PDF https://drive.google.com/open?id=1CoqHEX_fsZMF9rIMNJKpPJogpfQ0Pa_c https://drive.google.com/open?id=1sZ98kqSb1VIbQ5YEUodXCE3aBsxyLoGW https://drive.google.com/open?id=1zUwo0s_skkYhfnefEjWNnGmZnrbt_bKc