Ordenamientos

Ordenamiento Burbuja:

La Ordenación de 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.

A continuación una dinámica del ordenamiento burbuja.. muy practico! 

Ordenamiento Rápido....

concepto: Es un algoritmo creado por el científico británico en computación C.A.R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote.

Ordenamiento Shell

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n²) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log² n) en el peor caso. Esto es mejor que las O(n²) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Radix Sort:

En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.

Búsqueda secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. 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. 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. A continuación se muestra el pseudocódigo del algoritmo:

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
  pos: posición actual en el arreglo

pos = 0
Mientras pos < tam:
 Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario:
 pos = pos + 1
Fin (Mientras)
Devolver falso,

• C

int busquedaSimple(int  vector[], int n, int dato) {
 
    int i;
 
    for(i=0; i<n; i++){
        if(dato==vector[i]) {
            return i;
        }
    }
 
    return -1;
 
}

Búsqueda dicotómica (binaria)

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

• C

int busquedaBinaria(int  vector[], int n, int dato)
{
   int centro,inf=0,sup=n-1;
 
   while(inf<=sup){
     centro=(sup+inf)/2;
     if(vector[centro]==dato) return centro;
     else if(dato < vector [centro] ){
        sup=centro-1;
     }
     else {
       inf=centro+1;
     }
   }
   return -1;
}

Implementación recursiva en C++ 

• C++

 #include <iostream>
 #include <vector>
 
 bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){
     bool res;
     if(principio <= fin){
         int m = (principio + fin)/2;
         if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x);
         else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x);
         else res = true;
     }else res = false;
     return res;
 }
 /*{Post: Si se encuentra devuelve true, sino false}*/

Implementación recursiva en Python

• Python

def busquedaBinaria (numeros, inicio, fin, elemento):
    if (inicio == fin): return numeros [inicio] == elemento
 
    centro = (inicio + fin) // 2
 
    if (elemento < numeros [centro]):
        return busquedaBinaria (numeros, inicio, centro, elemento)
 
    elif (elemento > numeros [centro]):
        return busquedaBinaria (numeros, centro + 1, fin, elemento)
 
    else: return True
 
 
def busqueda (numeros, elemento):
    if (numeros == None) or (numeros == []):
        return False
 
    else: return busquedaBinaria (numeros, 0, len (numeros) - 1, elemento)