Ordenar lista de enteros en Python

Resultado de imagen de python

Ordenar una lista de enteros en Python se puede realizar de diversas formas. En este post os traigo tres formas de hacerlo.

Ordenar lista directamente

Python provee dos operaciones para obtener una lista ordenada a partir de una lista desordenada.

Para dejar la lista original intacta pero obtener una nueva lista ordenada a partir de ella, se usa la funci贸n聽sorted:

lista=[9,8,10,7,90]
print(sorted(lista))

La segunda opci贸n si modifica la lista original, la funci贸n es聽sort聽y a continuaci贸n se puede ver un ejemplo de uso:

lista=[9,8,10,7,90]
lista.sort
print(lista)

Ordenamiento por selecci贸n en Python

El ordenamiento por selecci贸n聽(Selection Sort聽en聽ingl茅s) es un聽algoritmo de ordenamiento que sigue los siguientes pasos:

  • Buscar el m铆nimo elemento de la lista
  • Intercambiarlo con el primero
  • Buscar el siguiente m铆nimo en el resto de la lista
  • Intercambiarlo con el segundo
  • Y as铆 sucesivamente…

funcionamiento del algoritmo ordenamiento por selecci贸n

La implementaci贸n de este algoritmo en Python podr铆a ser la siguiente:

def selection_sort(list):
    for i in range(0, len(list)-2):
        for j in range(i+1, len(list)-1):
            if list[j] < list[i]:
                list[i], list[j] = list[j], list[i]  # Intercambio

    return list

Para probar el algoritmo podemos introducir la misma lista de enteros que en el caso anterior:

print(selection_sort([9, 8, 10, 7, 90]))

Merge Sort en Python

El ordenamiento por mezcla (merge sort en ingl茅s) es un algoritmo de ordenamiento externo estable basado en la t茅cnica Divide y Vencer谩s.

ordenamiento mergesort

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

  • Si la longitud de la lista es 1, entonces ya est谩 ordenada. En otro caso:
    • Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tama帽o, visualmente una para la parte derecha y otra para la izquierda.
    • Ordenar ambas sublistas recursivamente aplicando el algoritmo.
    • Mezclar ambas sublistas para obtener la lista completa ordenada

La caracter铆stica principal de este algoritmo es que tiene una complejidad muy buena, por contra es complicado de entender e implementar.

Una posible implementaci贸n del algoritmo puede ser la siguiente:

def merge_sort(array):

    if len(array) > 1:
       pivot = len(array)//2
       array1 = array[:pivot]
       array2 = array[pivot:]
       merge_sort(array1)
       merge_sort(array2)
       
       i = j = k = 0
       
       while i < len(array1) and j < len(array2):
            if array1[i] < array2[j]:
                array[k] = array1[i]
                i += 1
            else:
                array[k] = array2[j]
                j += 1
            k += 1
       
       while i < len(array1):
           array[k] = array1[i]
           i += 1
           k += 1
       while j < len(array2):
            array[k] = array2[j]
            j += 1
            k += 1
        

    return array

Para probar el algoritmo podemos introducir la misma lista de enteros que en el caso anterior:

print(merge_sort([9, 8, 10, 7, 90]))

 

Deja un comentario