Bùsqueda Secuencial

Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del vector hasta que éste se encuentre, o hasta que se llegue al final del vector. La existencia se puede asegurar desde el momento que 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 código para este tipo de bùsqueda en Python:

#BUSQUEDA SECUENCIAL

def busquedaSecuencial(prueba, valorABuscar):
    posicion=0
    encontrado='No'
    posicionValorABuscar=0
    longitud=len(prueba)
    
    while posicion<longitud:
        if prueba[posicion]==valorABuscar :
            posicionValorABuscar=posicion
            encontrado='Si'
        posicion=posicion+1
    return encontrado,posicionValorABuscar

prueba=['1','33','23','45','12','78','99','21','31']
valorABuscar='12'

encontrado,posicion=busquedaSecuencial(prueba, valorABuscar)
    if encontrado=='Si':
        print 'Valor '+valorABuscar+' encontrado en posicion '+str(posicion+1)
    else:
        print 'Valor no encontrado'

Quick Sort

El ordenamiento rápido (quicksort en inglés) es un algoritmo 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.

El algoritmo trabaja de la siguiente forma:

• 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.

• 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.

A continuación se muestra el código para este tipo de ordenamiento en Python:

#QUICKSORT
    
def quickSort(a):
    izquierda=[]
    derecha=[]
    if (len(a) <= 1):
        return a
    for i in a[1:]:
        if (i < a[0]):
            izquierda.append(i)
        else:
           derecha.append(i)
    return quickSort(izquierda)+a[0:1]+quickSort(derecha)

prueba = [1,50,34,2,7,788]
quickSort(prueba)

print(prueba)

Merge Sort

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

1. Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

A continuación se muestra el código para este tipo de ordenamiento en Python:

#MERGE SORT

def mergeSort(a):
    merge_sort(a,0,len(a)-1)

#Merge_Sort
def merge_sort(a,izq,der):
    if izq<der:
        mit=(izq+der)/2
        merge_sort(a,izq,mit)
        merge_sort(a,mit+1,der)
        merge(a,izq,der,mit)
       

#Merge
def merge(a,izq,der,mit):
    list=[]
    i=izq
    j=mit+1
    while(i<=mit and j<=der):
        if(a[i]<=a[j]):
            list.append(a[i])
            i=i+1
        else:
            list.append(a[j])
            j=j+1
    while(i<=mit):
        list.append(a[i])
        i=i+1
    while(j<=der):
        list.append(a[j])
        j=j+1
    for k in range(0,der-izq+1):
        a[izq+ k]=list[k]   

prueba = [1,50,34,2,7,788]
mergeSort(prueba)

print(prueba)

Insertion Sort

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 es un 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) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

A continuación se muestra el código para este tipo de ordenamiento en Python:

#INSERTION SORT

def insertionSort(prueba):
   for j in range(1,len(prueba)):

     currentvalue = prueba[j]
     posicion = j

     while posicion>0 and prueba[posicion-1]>currentvalue:
         prueba[posicion]=prueba[posicion-1]
         posicion = posicion-1

     prueba[posicion]=currentvalue

prueba = [54,26,93,17,77,31,44,55,20]
insertionSort(prueba)

print(prueba)