TODOPIC

Lenguajes de programación para PC => Python => Mensaje iniciado por: Daniel1952 en 22 de Noviembre de 2021, 11:09:49

Título: Ordenar una lista sin el método sort(), a mano.
Publicado por: Daniel1952 en 22 de Noviembre de 2021, 11:09:49
Hola gente, ¿Cómo están?, les cuento, estoy practicando con listas y el libro que estoy leyendo
me sugiere que ordene una lista a mano o sea sin utilizar el método sort().-
La duda surge porque me parece que no debe ser necesario utilizar tantas variables, bueno si Picuino
o alguien tiene alguna sugerencia bienvenida sea.-
Un fuerte abrazo desde Argentina.

Slds, Daniel.

Código: Python
  1. vector = [20, 10, 50, 5, 21, 15]
  2.  
  3. l = len(vector)
  4.  
  5. while True:
  6.     ind1, ind2, temp, band = 0, 1, 0, 0    
  7.     for num1 in vector:
  8.         if num1 > vector[ind2]:
  9.             temp = num1
  10.             vector[ind1] = vector[ind2]
  11.             vector[ind2] = temp
  12.             band = 1
  13.         ind1 += 1
  14.         ind2 += 1
  15.  
  16.         if ind2 == l:
  17.             break
  18.        
  19.     if band == 0:
  20.         break
  21.    
  22. print(vector)
   
Título: Re:Ordenar una lista sin el método sort(), a mano.
Publicado por: Picuino en 22 de Noviembre de 2021, 11:42:22
Hay muchos métodos para ordenar listas. Uno que resulta fácil de entender y de implementar (aunque no es demasiado rápido) es el método de la Selección directa.
Primero buscamos el número más pequeño de la lista que queda por ordenar y luego lo intercambiamos con el primer elemento. Ahora volvemos a buscar el elemento más pequeño de la lista restante y lo intercambiamos con el segundo elemento. Así hasta que todos estén ordenados:

Código: Python
  1. import random
  2. vector = list(range(1,21))
  3. random.shuffle(vector)
  4.  
  5. for position in range(len(vector) - 1):
  6.     minimum = position
  7.     for i in range(position+1, len(vector)):
  8.        if vector[i] < vector[minimum]:
  9.            minimum = i
  10.     vector[position], vector[minimum] = vector[minimum], vector[position]
  11.  
  12. print(vector)
Título: Re:Ordenar una lista sin el método sort(), a mano.
Publicado por: Picuino en 22 de Noviembre de 2021, 12:01:03
Otro método que nos suena porque lo solemos utilizar a la hora de ordenar cosas es el método de la Inserción directa.
Lo bueno que tiene es que la lista puede ir creciendo a medida que ordenamos elementos. Por eso, aunque es un algoritmo lento, puede venir bien para implementarlo poco a poco (ciclo a ciclo) en un microcontrolador lento aunque la lista de elementos a ordenar vaya creciendo y la de elementos ordenados decreciendo a medida que ordenamos. En un número de ciclos igual al número de elementos, estarán todos ordenados.
Viene bien para que un PLC pueda ordenar listas grandes sin que pierda mucho tiempo en cada ciclo.

Primero consideramos que el primer elemento de la lista ya está ordenado. Después tomamos el siguiente elemento y lo insertamos en la posición que debería tener dentro de la lista de elementos ya ordenados. Seguimos así hasta que hemos tomado el último elemento y lo hemos insertado en su lugar.

Código: Python
  1. import random
  2. vector = list(range(1,21))
  3. random.shuffle(vector)
  4.  
  5. for position in range(1, len(vector)):
  6.     for i in range(position):
  7.        if vector[i] > vector[position]:
  8.            temp = vector[position]
  9.            for j in range(position, i, -1):
  10.                vector[j] = vector[j-1]
  11.            vector[i] = temp
  12.  
  13. print(vector)


El algoritmo se puede mejorar más todavía si tenemos en cuenta que la lista está ordenada y buscamos el sitio del nuevo elemento mediante una búsqueda binaria. Primero buscamos en el medio de la lista, luego en la mitad de la primera mitad o en la mitad de la segunda mitad, así hasta que encontramos el sitio del nuevo elemento. Es algo más rápido pero no quiero complicar más el algoritmo.
Título: Re:Ordenar una lista sin el método sort(), a mano.
Publicado por: Picuino en 22 de Noviembre de 2021, 12:06:56
Hay muchos más métodos simples, pero estos son los más significativos.

Luego puedes comenzar a estudiar los métodos rápidos (y más complejos de entender aunque tengan implementaciones casi tan sencillas como los anteriores): Heapsort, Quicksort, Mergesort, Timsort, etc.

Edito: Si oyes hablar o lees algo sobre el método de burbuja, en realidad no es un método de ordenación simple, es un método para hacer que el ordenador pierda mucho tiempo. No merece la pena tenerlo en cuenta.


https://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
Título: Re:Ordenar una lista sin el método sort(), a mano.
Publicado por: Daniel1952 en 23 de Noviembre de 2021, 11:40:26
Hola gente, que tengan todos un muy lindo Martes.
Gracias picuino, no se te puede ni sugerir mas ya que es evidente
que la palabra egoísmo no existe en tu vocabulario.-
Estoy practicando (sin copiarte nada) con el método Selección directa
pero comencé al revés, lo que logre es el for interno
(el que busca el numero menor) me falta el externo que recorre toda
la lista y la va ordenando.
Slds. Daniel
Título: Re:Ordenar una lista sin el método sort(), a mano.
Publicado por: Picuino en 23 de Noviembre de 2021, 17:49:07
Muchas gracias Daniel, aunque las respuestas que escribo no las hago por altruismo ni nada por el estilo, es que me gusta escribir y comentar sobre Python y sobre programación en general y me divierto enseñando lo que sé sobre ello.
Un saludo.