ORDENAMIENTO Y BUSQUEDA

¿Qué es 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.

METODOS DE ORDENAMIENTO

• BURBUJA.-
  burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar. 
  • QUICKSORT.- es un algoritmo creado por el científico británico en computación basado en la técnica de divide y venceras, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
  El algoritmo consta de los siguientes pasos:
  
• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
• Resituar 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.
• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

• SHELL SORT.-
  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 modifico 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 mas de una posición.
  Supongamos un vector de elementos
  4          12        16        24        36        3
  
  
  En el método de inserción directa, los saltos se hacen de una posición en una posición y se necesitaran cinco comparaciones. En el método de Shell, si los saltos son de dos posiciones, se realizaran comparaciones.
              4          12        16        24        36        3
  El método se basa en tomar como salto N/2 (siendo N el numero de elementos) y luego reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1
  Considerando la variable salto, se tendría para el caso de un determinado vector X los siguientes recorridos:
  Vector X         [X[1], X[3],  …,X[N]]
  Vector X1       [X[1], X[1] + salto, X[2],  …]
  Vector XN       [salto1, salto2, salto3,  …]

• En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

TIPOS DE BUSQUEDA.

• SECUENCIAL.-
  

  Presentación: Búsqueda Secuencial

  Definición:
  
  
  Está diseñada para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.
  
  
  
  
  Utilización:
  
  
  Se utiliza cuando algún elemento no está ordenado o no puede ser ordenado previamente.
  v Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final.
  v La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo .
  
  
  
  
  Ventajas y desventajas:
  DESVENTAJA.-.- en un vector de N posiciones este algoritmo va a buscar posición a posición hasta dar con el dato solicitado y en el caso de que no exista pues también va a recorrer todo el arreglo.
   VENTAJA.- Lo bueno de este tipo de búsqueda es que es muy sencillo de implementar.
  
  
  • BINARIO.-
    Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.
    Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).
    Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.
    A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array.
    

    • Datos de entrada:
        vec: vector en el que se desea buscar el dato
        tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.
        dato: elemento que se quiere buscar.
      
      Variables
        centro: subíndice central del intervalo
        inf: límite inferior del intervalo
        sup: límite superior del intervalo
      
      inf = 0
      sup = tam-1
      
      Mientras inf <= sup:
        centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción
        Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:
         Si dato < vec[centro] entonces:
          sup = centro - 1
         En caso contrario:
          inf = centro + 1
      Fin (Mientras)
      Devolver Falso 

    • HASH.-
      En informática, hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo
      Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.
      
      
      Las tablas hash, una de las aplicaciones más extendidas de las funciones de hash, aceleran el proceso de búsqueda de un registro de información según una clave (nota: este uso de la palabra poco se relaciona con su significado habitual). Por ejemplo, una cadena alfanumérica puede ser utilizada para buscar la información de un empleado en la base de datos de un sistema.
      La utilización de tablas hash provee un acceso casi directo a dichos registros, lo que significa que, en promedio, una búsqueda puede llegar a requerir sólo uno o dos intentos en la memoria o el archivo que contiene la información. Naturalmente, se prefiere una buena función de hash que evitará colisiones de hash.