Алгоритм сортировки пузырьков в Python

Я начинаю реализовывать основные алгоритмы сортировки. Критика в отношении реализации приветствуется.

#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))
11 голосов | спросил TravMatth 3 FebruaryEurope/MoscowbMon, 03 Feb 2014 03:06:02 +0400000000amMon, 03 Feb 2014 03:06:02 +040014 2014, 03:06:02

3 ответа


10
  1. Эта строка, кажется, оставлена ​​после сеанса отладки:

    #import pudb; pu.db
    

    Но нет необходимости редактировать код для его отладки - и вам следует стараться избегать этого, потому что слишком легко забыть удалить код отладки. (И в вашем другом вопросе вы забыли удалить его!)

    Вместо этого узнайте, как использовать инструменты. Вы можете запустить встроенный отладчик pdb из командной строки следующим образом:

    $ python -mpdb myprogram.py
    

    и вы можете запустить pudb из командной строки , как описано в документации .

  2. Докшрин записывается с неправильной точки зрения:

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

    Докстры должны быть записаны с точки зрения пользователя : что делает эта функция? Как мне это назвать? Какие значения он возвращает? Какие побочные эффекты у него есть? Например:

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

    Ваша docstring записывается с точки зрения реализации . Этот материал должен быть в комментариях.

  3. Вы указали свою переменную list_, чтобы избежать затенения встроенной функции list. Я бы предпочел найти лучшее имя для переменной, а не произвольно отменить ее так. Поскольку ваш алгоритм работает с любой измененной последовательностью (а не только списки), тогда seq может быть хорошим именем.

  4. Вместо:

    else:
        if condition:
            code
    

    записи:

    elif condition:
        code
    
  5. У вас есть специальный случай:

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

    , чтобы гарантировать, что val + 1 не сходит с конца списка. Но лучше прекратить итерацию, прежде чем это произойдет. Поэтому вместо:

    for val, item in enumerate(list_):
    

    записи:

    for val in range(len(list_) - 1):
    
  6. val - это индекс в списке: обычно такие имена переменных, как i и j.

  7. Каждый раз, когда цикл цикла while not_complete, вы делаете проход по всей последовательности. Но есть легкая оптимизация, , отмеченная Википедии :

      

    Алгоритм сортировки пузырьков можно легко оптимизировать, заметив, что n-й проход находит n-й самый большой элемент и помещает его в свое последнее место. Таким образом, внутренний цикл может не смотреть на последние n-1 элементы при запуске в течение n-го раза.

    Поэтому я бы написал это следующим образом:

    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. У вас есть тестовый код в конце скрипта. Лучше всего организовать тестовый код в модульных тестах с помощью unittest . Например:

    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)
    

    Обратите внимание, как я использовал рандомизацию для получения более широкого диапазона тестовых примеров. (Я также сделал длину тестового массива достаточно большой, чтобы дать заметную задержку, и поэтому подчеркнуть, насколько слабкий тип пузырька алгоритма.)

ответил Gareth Rees 3 FebruaryEurope/MoscowbMon, 03 Feb 2014 17:41:02 +0400000000pmMon, 03 Feb 2014 17:41:02 +040014 2014, 17:41:02
7
for val, item in enumerate(list_):

Вы не используете item, поэтому не получите его. Вместо этого используйте xrange(len(list_))

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

Повторное повторное позиционирование 0. Это не нужно делать. Вместо этого измените цикл, чтобы он стал менее круглым.

ответил Winston Ewert 3 FebruaryEurope/MoscowbMon, 03 Feb 2014 04:14:48 +0400000000amMon, 03 Feb 2014 04:14:48 +040014 2014, 04:14:48
0
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)

Предположим, что x = [3,2,1,6,7]

sortMyL(x) распечатает [1,2,3,6,7]

Не стесняйтесь задавать любые вопросы.

ответил user41149 23 AMpWed, 23 Apr 2014 07:14:12 +040014Wednesday 2014, 07:14:12

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132