Algoritmo de clasificación de burbujas en Python -- python campo con algorithm campo con sorting campo con reinventing-the-wheel camp codereview Relacionados El problema

Bubble sort algorithm in Python


11
vote

problema

Español

Estoy empezando a implementar algoritmos de clasificación básicos. Las críticas en la implementación son bienvenidas.

  #import pudb; pu.db def bubble_sort(list_):     """Implement bubblesort algorithm: iterate L to R in list, switching values     if Left > Right. Break when no alterations made to to list. """     not_complete = True     while not_complete:         not_complete = False         for val, item in enumerate(list_):             if val == len(list_)-1: val = 0             else:                 if list_[val] > list_[val+1]:                     list_[val], list_[val+1] = list_[val+1], list_[val]                     not_complete = True     return list_  if __name__ == '__main__':     assert bubble_sort(list(range(9))[::-1]) == list(range(9))   
Original en ingles

I'm starting to implement basic sorting algorithms. Criticisms on the implementation is welcome.

#import pudb; pu.db def bubble_sort(list_):     """Implement bubblesort algorithm: iterate L to R in list, switching values     if Left > Right. Break when no alterations made to to list. """     not_complete = True     while not_complete:         not_complete = False         for val, item in enumerate(list_):             if val == len(list_)-1: val = 0             else:                 if list_[val] > list_[val+1]:                     list_[val], list_[val+1] = list_[val+1], list_[val]                     not_complete = True     return list_  if __name__ == '__main__':     assert bubble_sort(list(range(9))[::-1]) == list(range(9)) 
           

Lista de respuestas

11
 
vote
vote
La mejor respuesta
 
  1. Esta línea parece ser dejada de una sesión de depuración:

      #import pudb; pu.db   

    Pero no hay necesidad de editar su código para depurarlo "y debe esforzarse por evitarlo, porque es demasiado fácil olvidarse de eliminar el código de depuración. (Y en su otra pregunta ¡Olvidó eliminarlo!)

    En su lugar, aprenda cómo usar las herramientas. Puede ejecutar el depurador incorporado pdb de la línea de comando como esta:

      $ python -mpdb myprogram.py   

    y puede ejecutar pudb desde la línea de comandos como se describe en la documentación .

  2. El Docstring está escrito desde el punto de vista incorrecto:

      """Implement bubblesort algorithm: iterate L to R in list, switching values if Left > Right. Break when no alterations made to to list. """   

    DOCSTRINGS debe escribirse desde el punto de vista del usuario : ¿Qué hace esta función? ¿Cómo debo llamarlo? ¿Qué valores devuelve? ¿Qué efectos secundarios tiene? Por ejemplo:

      >>> help(abs) Help on built-in function abs in module builtins:  abs(...)     abs(number) -> number      Return the absolute value of the argument.   

    Su documentos se escribe desde el punto de vista del implementador . Este tipo de material debe estar en comentarios.

  3. Usted deletreó su variable list_ Para evitar sombrear la función incorporada list . Preferiría encontrar un mejor nombre para la variable en lugar de respetarlo arbitrariamente así. Dado que su algoritmo trabaja en cualquier secuencia mutable (no solo listas), entonces 9988776655544338 podría ser un buen nombre.

  4. en lugar de:

      else:     if condition:         code   

    Escribir:

      pdb0  
  5. usted tiene un caso especial:

      pdb1  

    Para asegurarse de que pdb2 no se agota del extremo de la lista. Pero sería mejor detener la iteración antes de que eso suceda. Así que en lugar de:

      pdb3  

    Escribir:

      pdb4  
  6. pdb5 es un índice en la lista: es convencional para darles nombres de variables como pdb6 y pdb7 .

  7. Cada vez alrededor del bucle pdb8 , realiza un pase de la totalidad de la secuencia. Pero hay una optimización fácil, notado por wikipedia :

    El algoritmo de clasificación de burbujas se puede optimizar fácilmente observando que el pase N-TH encuentra el elemento más grande de N y lo pone en su lugar final. Por lo tanto, el bucle interno puede evitar mirar los últimos artículos N-1 cuando se ejecuta para el N-Th Time.

    Así que lo escribiría así:

      pdb9  
  8. Tiene algún código de prueba al final del script. Es mejor organizar el código de prueba como este en las pruebas de la unidad usando el $ python -mpdb myprogram.py 0 Módulo. Por ejemplo:

      $ python -mpdb myprogram.py 1  

    Nota cómo he utilizado la aleatorización para obtener una gama más amplia de casos de prueba. (También he hecho la longitud de la matriz de prueba lo suficientemente grande como para dar un retraso notable y enfatizar lo que es un tipo de burbuja de algoritmo.)

 
  1. This line seems to be left over from a debugging session:

    #import pudb; pu.db 

    But there is no need to edit your code to debug it xe2x80x94 and you should strive to avoid doing so, because it's too easy to forget to remove the debugging code. (And in your other question you did forget to remove it!)

    Instead, learn how to use the tools. You can run the built-in debugger pdb from the command line like this:

    $ python -mpdb myprogram.py 

    and you can run pudb from the command line as described in the documentation.

  2. The docstring is written from the wrong point of view:

    """Implement bubblesort algorithm: iterate L to R in list, switching values if Left > Right. Break when no alterations made to to list. """ 

    Docstrings should be written from the user's point of view: What does this function do? How should I call it? What values does it return? What side effects does it have? For example:

    >>> help(abs) Help on built-in function abs in module builtins:  abs(...)     abs(number) -> number      Return the absolute value of the argument. 

    Your docstring is written from the point of view of the implementer. This kind of material should be in comments.

  3. You spelled your variable list_ to avoid shadowing the built-in function list. I would prefer to find a better name for the variable rather than arbitrarily respelling it like this. Since your algorithm works on any mutable sequence (not just lists), then seq might be a good name.

  4. Instead of:

    else:     if condition:         code 

    write:

    elif condition:     code 
  5. You have a special case:

    if val == len(list_)-1: val = 0 

    to ensure that val + 1 does not run off the end of the list. But it would be better to stop the iteration before that happens. So instead of:

    for val, item in enumerate(list_): 

    write:

    for val in range(len(list_) - 1): 
  6. val is an index into the list: it's conventional to give such variables names like i and j.

  7. Each time around the while not_complete loop, you make a pass over the whole of the sequence. But there is an easy optimization, noted by Wikipedia:

    The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time.

    So I would write it like this:

    def bubble_sort(seq):     """Sort the mutable sequence seq in place and return it."""     for i in reversed(range(len(seq))):         finished = True         for j in range(i):             if seq[j] > seq[j + 1]:                 seq[j], seq[j + 1] = seq[j + 1], seq[j]                 finished = False         if finished:             break     return seq 
  8. You have some test code at the end of the script. It is best to organize test code like this into unit tests using the unittest module. For example:

    from unittest import TestCase from random import random  class BubbleSortTest(TestCase):     def test_bubble_sort(self):         seq = [random() for _ in range(4000)]         sorted_seq = sorted(seq)         self.assertEqual(bubble_sort(seq), sorted_seq) 

    Note how I've used randomization to get a wider range of test cases. (I've also made the length of the test array large enough to give a noticeable delay and so emphasize how poor an algorithm bubble sort is.)

 
 
7
 
vote
  $ python -mpdb myprogram.py 2  

No usa $ python -mpdb myprogram.py 3 , así que no lo entendas. En su lugar, use $ python -mpdb myprogram.py 4

  $ python -mpdb myprogram.py 5  

Esto vuelve a comprobar la posición 0 nuevamente. No hay necesidad de hacer eso. En su lugar, cambie el bucle para que se vuelva menos redondo.

 
for val, item in enumerate(list_): 

You don't use item, so don't get it. Instead, use xrange(len(list_))

if val == len(list_)-1: val = 0 

This rechecks position 0 again. There is no need to do that. Instead, change the loop so it goes one less round.

 
 
0
 
vote
  $ python -mpdb myprogram.py 6  

Digamos x = [3,2,1,6,7]

$ python -mpdb myprogram.py 7 imprimirá [1,2,3,6,7]

Siéntase libre de hacer cualquier pregunta.

 
def swap(mylist,i):     temp1 = mylist[i]                       temp2 = mylist[i+1]     mylist[i] = temp2     mylist[i+1] = temp1  def one_scan(mylist):     for i in range (len(mylist)-1):          if(mylist[i] >= mylist[i+1]):             swap(mylist,i)  def sortMyL(L):     i = 0     while(i<len(L)):         one_scan(L)         i+=1     print("Sorted list")     print(L) 

Let's say x = [3,2,1,6,7]

sortMyL(x) will print out [1,2,3,6,7]

Feel free to ask any questions.

 
 

Relacionados problema

5  Implementar el análisis de STRTOD  ( Implement strtod parsing ) 
en este comentario la OP escribió, Soy un novato, así que me gustaría saber ¿Cómo me gustaría analizar los números / argumentos de Negetive? en Esta ...

2  Fusionar la implementación de Sort Java  ( Merge sort java implementation ) 
¿Puede alguien revisar mi implementación de tipo de fusión en Java? ¿Es bueno / malo y puede mejorarse más? public class MyMergeSort { private int [] d...

12  Autenticación simple en ASP.NET MVC 5  ( Simple authentication in asp net mvc 5 ) 
Estoy construyendo una aplicación ASP.NET MVC 5 y, por razones que son irrelevantes en este punto, estoy intentando construir mi propio medio para autenticar ...

5  Método de cálculo del día del año  ( Day of year calculation method ) 
El ejercicio que quería resolver es de aquí . Copiando desde esa página: public static int dayOfYear(int month, int dayOfMonth, int year) { if (month...

0  Producto cartesiano de dos tuplas - Python  ( Cartesian product of two tuples python ) 
Estoy resolviendo el ejercicio 4 de Discusión 3 de CS 61A (2012) de Berkley (2012) (consulte la página 4): Rellene la definición de cartesian_product . ...

3  Implementando de forma libre, crecer y encogerse en una tabla de hash  ( Implementing cleartable grow and shrink on a hash table ) 
He pasado por preguntas anteriores sobre la implementación de tablas de hash en Python, pero tengo algo más específico. Estoy manejando colisiones con sondeo ...

4  Iniciar sesión en la base de datos con el núcleo ASP.NET  ( Logging into database with asp net core ) 
En el Container9 de mi aplicación ASP.NET Core Quiero configurar el 99887766655443330 para que inicie sesión en la base de datos. Por lo tanto, creo despu...

6  C Getline () Implementación  ( C getline implementation ) 
Estoy practicando mi codificación C y quería implementar mi propia versión del getline Función en C para fines de aprendizaje. Me gustaría una revisión sobr...

9  Comandos de Linux en Python  ( Linux commands in python ) 
He decidido escribir algunos comandos de Linux en Python. A continuación se muestra una lista, junto con algunas restricciones (si no está familiarizado con L...

11  Yaai (otro de otra implementación)  ( Yaai yet another any implementation ) 
Soy un desarrollador de juegos de C # actualmente aprendiendo C ++ y este es mi proyecto de segundo Big-ish (el primero es un Implementación vectorial ). E...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos