Sorting

Bubble Sort

for i in range(len(a)):
	for j in range(len(a)-i):
		if a[j] > a[j+1]:
			swap(j,j+1)

Orden: O(n^2)

De los peores algoritmos de ordenamiento en los casos reales

Selection Sort

for i in range(len(a)):
    min_idx = i
    for j in range(i+1, len(a)):
        if a[j] < a[min_idx]:
            min_idx = j
    a[i], a[min_idx] = a[min_idx], a[i]

Orden: O(n^2)

Busca el mínimo y lo pone al principio

Una mejora sobre el bubble sort, pero todavía no es ideal para grandes conjuntos de datos.

Insertion Sort

El algoritmo de ordenamiento por inserción trabaja de la manera en que muchas personas ordenan una mano de cartas de póker. Comienza con el segundo elemento de la lista (el primer elemento forma una lista ordenada por sí mismo) y lo inserta en la posición correcta en la lista ordenada formada por los elementos anteriores, desplazando los elementos necesarios. Luego, pasa al siguiente elemento y repite el proceso hasta que toda la lista está ordenada.

for i in range(1, len(a)):
    val = a[i]
    j = i-1
    while j >=0 and val < a[j] :
            a[j+1] = a[j]
            j -= 1
    a[j+1] = val

Orden de complejidad: O(n^2)

Funciona bien para conjuntos de datos pequeños, pero es ineficiente para conjuntos de datos grandes.

Cuando son pocos se comporta como O(n)

Peor caso: cuando está ordenado al revés