Practica No.1 Algoritmos de Ordenamiento

Ordenamiento de Burbuja

Este algoritmo de ordenamiento es de los más sencillos de implementar pero al mismo tiempo el que peor rendimiento tiene, consiste en ir comparando elemento por elemento del vector, de manera que se van intercambiando si están mal acomodados de modo que el valor más pequeño este en la primera posición, volver a comparar los elementos y así sucesivamente, hasta que todo el vector esta ordenado, el problema de este algoritmo es que al realizar las búsquedas siguientes, se vuelven a comparar los elementos ya ordenados, teniendo una complejidad:

$$\Omega(n^2)$$
A continuación se muestra la implementación de este algoritmo en Python:

def BubbleSort(vector):
    print("Algoritmo de Burbuja")
    tam=len(vector)
    for i in range(0,tam):
        for j in range (i+1,tam):
            if (vector[i] > vector[j]):
                temp = vector[i]
                vector[i] = vector[j]
                vector[j] = temp
    return vector

Ordenamiento de Selección

Este algoritmo consiste en encontrar el elemento de menor valor en la primera iteración y colocarlo en la primera posición, después encontrar el segundo menor y ponerlo en la segunda posición y así sucesivamente, hasta ordenar todo el vector, tiene la misma complejidad que el ordenamiento por burbuja, su implementación en Python se muestra a continuación:

def SelectionSort(vector):
    print("Algoritmo de Selección")
    tam=len(vector)
    for i in range(0,tam):
        minimo=i
        for j in range (i+1,tam):
            if (vector[minimo]>vector[j]):
                minimo=j
        temp = vector[i]
        vector[i] = vector[minimo]
        vector[minimo] = temp
    return vector

Ordenamiento de Inserción

Este algoritmo se basa en la idea de ir ordenado los elementos del vector de forma ordenada como se vayan recorriendo asumiendo que los elementos del lado izquierdo ya están ordenados adecuadamente, por lo que solo se necesita encontrar su posición en esos elementos, tiene la misma complejidad que los anteriores y su implementación se muestra a continuación:

def InsertionSort(vector):
    print("Algoritmo de Inserción")
    tam=len(vector)
    for i in range(1,tam):
        valor=vector[i]
        j=i-1
        while j>=0 and vector[j]>valor:
            vector[j+1] = vector[j]
            j=j-1
        vector[j+1]=valor
    return vector

Ordenamiento por Mezclas

Este algoritmo se basa en la técnica de divide y vencerás, el vector original se divide en dos, estas dos listas se ordenan de manera separada, volviéndose a dividir hasta que se obtiene vectores de un solo elemento, entonces consideramos que ya está ordenada. Cuando ambas listas están ordenada se juntan para formar el arreglo ordenado. Este Algoritmo tiene una complejidad de:

$$\Omega(n \log n)$$

Por lo cual ofrece un mejor rendimiento que los algoritmos anteriores. Este método requiere de dos funciones para su implementación una que divida el arreglo, la cual se muestra a continuación en Python:

def MergeSort(vector):
    tam=len(vector)
    if tam==1:
        return vector
    else:
        mitad = len(vector)//2
        mitizq = MergeSort(vector[:mitad])
        mitder = MergeSort(vector[mitad:])
        return Mezcla(mitizq,mitder)

Y una que permita unir los dos arreglos ordenados, esta función se muestra a continuación codificada en Python:

def Mezcla(mitizq,mitder):
    resultado = []
    i=0
    j=0
    tizq=len(mitizq)
    tder=len(mitder)
    while (i < tizq or j < tder):
        if(i >= tizq):
            resultado.append(mitder[j])
            j=j+1
        elif(j >= tder):
            resultado.append(mitizq[i])
            i=i+1
        elif(mitizq[i] < mitder[j]):
            resultado.append(mitizq[i])
            i=i+1
        else:
            resultado.append(mitder[j])
            j=j+1
    return resultado

Ordenamiento QuickSort 

Este es al algoritmo más eficiente de ordenamiento actualmente, y se basa en la recursividad, se escoge un elemento del vector que será considerado pivote y en base a este elemento, se crean dos listas una que contenga los elementos menores y otra que contenga los elementos mayores, este proceso se vuelve a repetir hasta que quedan arreglos de un solo momento, que es cuando ha quedado ordenado el arreglo.
El punto central de este algoritmo es encontrar un pivote adecuado ya que dependiendo de este, la complejidad del algoritmo puede variar desde ser $\Omega(n \log n)$ en el mejor de los casos, hasta $\Omega(n^2)$ en el peor de los casos, la implementación del algoritmo se muestra a continuación.

def QuickSort(vector,primero,ultimo):
    i = primero
    j = ultimo   
    pivote = (vector[i] + vector[j]) / 2
    while i < j:
        while vector[i] < pivote:
            i+=1
        while vector[j] > pivote:
            j-=1
        if i <= j:
            x = vector[j]
            vector[j] = vector[i]
            vector[i] = x
            i+=1
            j-=1
    if primero < j:
        vector = QuickSort(vector, primero, j)
    if ultimo > i:
        vector = QuickSort(vector, i, ultimo)
    return vector

El programa de prueba con la implementación de todos estos algoritmos se puede encontrar en el siguiente link
Los algoritmos de ordenamiento por mezclas y quicksort fueron realizados basándose en las implementaciones encontradas en los siguientes sitios:
Merge Sort
Quick Sort