Домашнее задание пузырьковой сортировки

130

В классе мы разрабатываем алгоритмы сортировки, и хотя я прекрасно понимаю их, когда говорю о них и пишу псевдокод, у меня возникают проблемы с написанием для них реального кода.

Это моя попытка на Python:

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
            else:
                unsorted = True

print bubble(mylist)

Теперь это (насколько я могу судить) сортируется правильно, но как только он завершается, он просто бесконечно зацикливается.

Как можно исправить этот код, чтобы функция правильно завершила свою работу и правильно отсортировала список любого (разумного) размера?

PS Я знаю, что у меня не должно быть отпечатков в функции, и у меня должен быть возврат, но я просто еще не сделал этого, так как мой код еще не работает.

Джош Хант
источник
29
@KM - Он должен убраться с твоей лужайки?
Эйден Белл
123
По сути, это сообщение: «У меня проблемы с кодированием, это то, что я сделал, это не работает». Очевидно, есть неявное «Может кто-нибудь подскажет, пожалуйста?» В отличие от многих домашних заданий, этот (а) хорошо написан, (б) прямо говорит о домашнем задании и (в) включает хорошую попытку решения проблемы. Я не думаю, что отсутствие настоящего вопросительного знака слишком сильно отвлекает ...
Джон Фухи,
36
Пузырьковая сортировка используется как средство обучения, потому что это самый простой алгоритм сортировки для понимания большинства людей. Это хорошая отправная точка для изучения сортировки и алгоритмов в целом. Если бы мы учили только тому, что люди действительно использовали бы, обсуждение сортировки началось бы и закончилось бы словами «использовать процедуру сортировки библиотеки».
Bill the Lizard
38
Этот вопрос - пример того, как задавать хорошие «домашние» вопросы. По мнению Джона Фухи, есть образец кода, он хорошо написан, и плакат изо всех сил пытается облегчить нам помощь. Молодец, Джошхант.
Джаррет Харди
20
Bubble сортировка не простой алгоритм сортировки для людей , чтобы понять. Исходя из моего собственного опыта и опыта преподавания, я могу с уверенностью сказать, что сортировка вставкой, сортировка выбора, минимальная сортировка (минимальная сортировка элементов), даже (для некоторых студентов) сортировка слиянием и быстрая сортировка легче понять - в конце концов, они в некоторой степени соответствуют естественные способы сортировки списка, но пузырьковая сортировка просто искусственная. Кроме того, пузырьковая сортировка подвержена множеству одиночных ошибок и ошибок бесконечного цикла, как этот вопрос здесь. Как говорит Кнут, «пузырьковой сортировке, кажется, нечего рекомендовать, кроме броского названия ...»
ShreevatsaR

Ответы:

127

Чтобы объяснить, почему ваш скрипт сейчас не работает, я переименую переменную unsortedв sorted.

Сначала ваш список еще не отсортирован. Конечно, мы устанавливаем sortedв False.

Как только мы запускаем whileцикл, мы предполагаем, что список уже отсортирован. Идея такова: как только мы обнаруживаем два элемента, которые расположены не в правильном порядке, мы sortedвозвращаемся к ним False. sortedостанется True только в том случае, если не было элементов в неправильном порядке .

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

Есть также мелкие мелкие проблемы, которые могут помочь сделать код более эффективным или читаемым.

  • В forцикле вы используете переменную element. Технически elementэто не элемент; это число, представляющее индекс списка. Кроме того, это довольно долго. В этих случаях просто используйте имя временной переменной, например, iдля «index».

    for i in range(0, length):
  • Команда rangeтакже может принимать только один аргумент (с именем stop). В этом случае вы получите список всех целых чисел от 0 до этого аргумента.

    for i in range(length):
  • Руководство по стилю Python рекомендует называть переменные строчными буквами с подчеркиванием. Это очень незначительная придирка для такого маленького сценария; это больше для того, чтобы вы привыкли к тому, на что чаще всего похож код Python.

    def bubble(bad_list):
  • Чтобы поменять местами значения двух переменных, запишите их как присвоение кортежа. Правая часть оценивается как кортеж (скажем, (badList[i+1], badList[i])есть (3, 5)), а затем присваивается двум переменным в левой части ( (badList[i], badList[i+1])).

    bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

Сложите все вместе, и вы получите следующее:

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

(Кстати, я удалил и ваше выражение для печати.)

Wesley
источник
1
Только в этом последнем фрагменте кода пузырь ничего не возвращает, поэтому в конечном результате печатается «None». Вы, вероятно, захотите либо вернуть список, либо создать пузырек (my_list), а затем распечатать my_list.
Тунг Нгуен
9
+1 хорошо структурированный, четкий совет. Приятно видеть, что вы знакомите читателя с тем, что вы сделали и почему, а не просто пишете быстрое исправление.
Tom Leys,
1
Я программист на C #, так что это может быть потому, что у меня нет Python, но разве вам не нужно что-то в цикле while, чтобы вычесть 1 из длины, чтобы получить нормальный алгоритм пузырьковой сортировки?
Мартин Браун,
20
Это наивная (но не неправильная) реализация пузырьковой сортировки. После каждой итерации whileцикла самый большой элемент «всплывает» в конец списка. Таким образом, после одной итерации последний элемент определенно находится в нужном месте (и не будет перемещен при последующих итерациях). Вычитая 1 из длины, вы оптимизируете алгоритм, сортируя только подсписок, который еще не отсортирован (самые length-nпередние элементы списка). Я решил пропустить эту оптимизацию, поскольку это скорее оптимизация, чем жизненно важная часть алгоритма.
Уэсли
2
Put it all together, and you get this:... ну, вы пропустили это:The range command can also take just one argument (named stop).
Петер Перхач
10

Цель пузырьковой сортировки - перемещать более тяжелые предметы внизу в каждом раунде, а более легкие перемещать вверх. Во внутреннем цикле, где вы сравниваете элементы, вам не нужно перебирать весь список на каждом шагу . Самый тяжелый уже ставится последним. Местами переменная является дополнительная проверка , поэтому мы можем отметить , что список теперь сортируется и избежать продолжения ненужных вычислений.

def bubble(badList):
    length = len(badList)
    for i in range(0,length):
        swapped = False
        for element in range(0, length-i-1):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                swapped = True
        if not swapped: break

    return badList

Ваша версия 1, исправлено:

def bubble(badList):
    length = len(badList) - 1
    unsorted = True
    while unsorted:
        unsorted = False
        for element in range(0,length):
            #unsorted = False
            if badList[element] > badList[element + 1]:
                 hold = badList[element + 1]
                 badList[element + 1] = badList[element]
                 badList[element] = hold
                 unsorted = True
                 #print badList
             #else:
                 #unsorted = True

     return badList
Ник Дандулакис
источник
8

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

sorted = False
while not sorted:
    ...

С другой стороны, логика алгоритма немного неверна. Вам нужно проверить, поменялись ли два элемента местами во время цикла for. Вот как бы я это написал:

def bubble(values):
    length = len(values) - 1
    sorted = False
    while not sorted:
        sorted = True
        for element in range(0,length):
            if values[element] > values[element + 1]:
                 hold = values[element + 1]
                 values[element + 1] = values[element]
                 values[element] = hold
                 sorted = False
    return values
Мартин Кот
источник
1
Жаль, что нет кнопки "НЕПРАВИЛЬНО", которую я могу нажать для этого ответа. Я думаю, что этот вопрос и ответы - и особенно голосование - должны быть представлены в следующий раз, когда Джоэл Спольски расскажет о том, насколько хорошо он настроил социальные взаимодействия в stackoverflow.
Дэниел Мартин
@ Дэниел: вы можете делать то, что могут делать другие люди с достаточной репутацией (100) - проголосуйте против неправильного ответа. Есть росток истины - отрицание условий, закрепленных во флаговых переменных, - это плохо. Однако это не полный ответ - я думаю, @McWafflestix прав.
Джонатан Леффлер,
2
Ребята, вы правы, я ответил на этот вопрос раньше времени. Извини за это.
Мартин Кот,
2
@Martin - и я должен отметить, что я больше удивлен / шокирован голосованием, чем ответом. Система репутации побуждает вас сразу же получить первый ответ. Неисправная часть - это голосование за неправильный ответ.
Дэниел Мартин
2
Я подозреваю, что большинство людей голосуют, вообще не понимая вопроса (точно так же, как я ответил на вопрос). OTOH, человек, задающий вопрос, имеет право впоследствии выбрать «правильный» ответ.
Мартин Кот,
7

Вы неправильно используете переменную Unsorted; вы хотите иметь переменную, которая сообщает вам, поменяли ли вы местами два элемента; если вы это сделали, вы можете выйти из цикла, в противном случае вам нужно будет снова выполнить цикл. Чтобы исправить то, что у вас здесь, просто поместите "unsorted = false" в тело вашего if case; удалите свой else case; и поместите "unsorted = true" перед вашим forциклом.

Пол Сонье
источник
5
def bubble_sort(l):
    for passes_left in range(len(l)-1, 0, -1):
        for index in range(passes_left):
            if l[index] < l[index + 1]:
               l[index], l[index + 1] = l[index + 1], l[index]
    return l
mtasic85
источник
1
Я действительно полагаю, что вопрос был больше похож на «Как можно исправить этот код», а не «какова ваша пузырьковая сортировка?»
Джош Хант
4
Вы абсолютно правы, но сделать это правильно - важнее
mtasic85
6
Верно, возможно, mtasic ... но все, что помечено как домашнее задание, наиболее поучительно настраивается, а не переписывается (особенно когда оно помечено как домашнее задание ОП).
Джаррет Харди
1
Это идеальное переписывание учебника С пузырьковой сортировкой, изучаемого большинством людей. Я написал то же самое.
Лакшман Прасад
2
На мой взгляд, добавление хорошей информации полезно. так что хороший ответ ... хотя вы могли бы использовать флаг, чтобы сломать как можно раньше.
Grijesh Chauhan
3

# Очень простая функция, которую можно оптимизировать (очевидно), уменьшив проблемное пространство 2-го массива. Но такая же сложность O (n ^ 2).

def bubble(arr):
    l = len(arr)        
    for a in range(l):
        for b in range(l-1):
            if (arr[a] < arr[b]):
            arr[a], arr[b] = arr[b], arr[a]
    return arr 
Waqas
источник
Немного менее изощренно то, как вы можете менять значения в Python: arr[a], arr[b] = arr[b], arr[a]
Макото,
1

У вас там пара ошибок. Первый - по длине, а второй - в использовании вами несортированного (как указано McWafflestix). Вы, вероятно, также захотите вернуть список, если собираетесь его распечатать:

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 2
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False

            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
                unsorted = True

    return badList

print bubble(mylist)

eta: Вы правы, это чертовски глючит. Плохо, что я не тестировал еще несколько примеров.

def bubble2(badList):
    swapped = True
    length = len(badList) - 2

    while swapped:
        swapped = False
        for i in range(0, length):
            if badList[i] > badList[i + 1]:

                # swap
                hold = badList[i + 1]
                badList[i + 1] = badList[i]
                badList[i] = hold

                swapped = True

    return badList
Тревор Оке
источник
Разве «unsorted = False» не должно быть вне цикла for?
Svante
У него было еще несколько проблем;)
Trevor Oke
1

Я свежий новичок, вчера начал читать о Python. Вдохновленный вашим примером, я создал что-то, может быть, больше в стиле 80-х, но тем не менее это вроде работает.

lista1 = [12, 5, 13, 8, 9, 65]

i=0
while i < len(lista1)-1:
    if lista1[i] > lista1[i+1]:
        x = lista1[i]
        lista1[i] = lista1[i+1]
        lista1[i+1] = x
        i=0
        continue
    else:
        i+=1

print(lista1)
Игорь
источник
1

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

Я упростил код, и теперь он будет работать для любого списка чисел, независимо от списка, и даже если есть повторяющиеся числа. Вот код

mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2]
print mylist

def bubble(badList):
    length = len(badList) - 1
    element = 0
    while element < length:
        if badList[element] > badList[element + 1]:
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
            element = 0
            print badList
        else:
            element = element + 1

print bubble(mylist)
Вайнберг
источник
1
def bubble_sort(l):
    exchanged = True
    iteration = 0
    n = len(l)

    while(exchanged):
        iteration += 1
        exchanged = False

        # Move the largest element to the end of the list
        for i in range(n-1):
            if l[i] > l[i+1]:
                exchanged = True
                l[i], l[i+1] = l[i+1], l[i]
        n -= 1   # Largest element already towards the end

    print 'Iterations: %s' %(iteration)
    return l
Зиле Рехман
источник
1
Пузырьки большего элемента полностью до конца. И уменьшите конечный счетчик «n», чтобы вам не пришлось снова его сравнивать. Продолжайте цикл while, пока есть обмены. Худший случай: O (N ^ 2) Лучший случай: O (N)
Зиле Рехман
1
def bubbleSort(alist):
if len(alist) <= 1:
    return alist
for i in range(0,len(alist)):
   print "i is :%d",i
   for j in range(0,i):
      print "j is:%d",j
      print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j])
      if alist[i] > alist[j]:
         alist[i],alist[j] = alist[j],alist[i]
return alist

alist = [54,26,93,17,77,31,44,55,20, -23, -34,16,11,11,11]

печать пузырьков (список)

pythonnewbie
источник
Пожалуйста, сделайте отступ в образце кода правильно: это, конечно, особенно важно в Python. Вы также можете объяснить, почему ваше решение стоит рассмотреть, есть также ответ со 100 голосами
kdopen
1
def bubble_sort(a):
    t = 0
    sorted = False # sorted = False because we have not began to sort
    while not sorted:
    sorted = True # Assume sorted = True first, it will switch only there is any change
        for key in range(1,len(a)):
            if a[key-1] > a[key]:
                sorted = False
                t = a[key-1]; a[key-1] = a[key]; a[key] = t;
    print a
pinkopink
источник
1

Более простой пример:

a = len(alist)-1
while a > 0:
    for b in range(0,a):
        #compare with the adjacent element
        if alist[b]>=alist[b+1]:
            #swap both elements
            alist[b], alist[b+1] = alist[b+1], alist[b]
    a-=1

Это просто берет элементы от 0 до a (в основном, все несортированные элементы в этом раунде) и сравнивает их с соседним элементом, и выполняет замену, если он больше, чем его соседний элемент. В конце раунда последний элемент сортируется, и процесс снова запускается без него, пока не будут отсортированы все элементы.

Нет необходимости в условии, что sort истинно оно или нет.

Обратите внимание, что этот алгоритм учитывает положение чисел только при замене местами, поэтому повторяющиеся числа не повлияют на него.

PS. Я знаю, что этот вопрос был опубликован очень давно, но я просто хотел поделиться этой идеей.

txsaw1
источник
1
arr = [5,4,3,1,6,8,10,9] # array not sorted

for i in range(len(arr)):
    for j in range(i, len(arr)):
        if(arr[i] > arr[j]):
            arr[i], arr[j] = arr[j], arr[i]

            print (arr)
сим
источник
0
def bubble_sort(li):
    l = len(li)
    tmp = None
    sorted_l = sorted(li)
    while (li != sorted_l):
        for ele in range(0,l-1):
            if li[ele] > li[ele+1]:
                tmp = li[ele+1]
                li[ele+1] = li [ele]
                li[ele] = tmp
    return li
скалистый
источник
0
def bubbleSort ( arr ):
    swapped = True 
    length = len ( arr )
    j = 0

    while swapped:
        swapped = False
        j += 1 
        for i in range ( length  - j ):
            if arr [ i ] > arr [ i + 1 ]:
                # swap
                tmp = arr [ i ]
                arr [ i ] = arr [ i + 1]
                arr [ i + 1 ] = tmp 

                swapped = True

if __name__ == '__main__':
    # test list
    a = [ 67, 45, 39, -1, -5, -44 ];

    print ( a )
    bubbleSort ( a )
    print ( a )
Aldo Núñez
источник
0
def bubblesort(array):
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return(array)

print(bubblesort([3,1,6,2,5,4]))
Люк Уилли
источник
1
Хотя этот код может ответить на вопрос, предоставление дополнительного контекста относительно того, как и / или почему он решает проблему, улучшит долгосрочную ценность ответа.
Александр
0

Я рассматриваю возможность добавления своего решения, потому что любое решение здесь имеет

  1. большее время
  2. большая космическая сложность
  3. или делать слишком много операций

тогда должно быть

Итак, вот мое решение:


def countInversions(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        _count = count
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                count += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if _count == count:
            break
    return count
Акшат Тамракар
источник
0

Если кого-то интересует более короткая реализация с использованием списка:

def bubble_sort(lst: list) -> None:
    [swap_items(lst, i, i+1) for left in range(len(lst)-1, 0, -1) for i in range(left) if lst[i] > lst[i+1]]


def swap_items(lst: list, pos1: int, pos2: int) -> None:
    lst[pos1], lst[pos2] = lst[pos2], lst[pos1]
Лирам Заррук
источник
0

Вот другой вариант пузырьковой сортировки без forпетли. В основном вы рассматриваете lastIndexиз arrayи медленно decrementing, пока она первый индекс массива.

Он algorithmбудет продолжать движение по массиву таким образом, пока не будет выполнен весь проход без каких-либо swapsпроисшествий.

Пузырь в основном проявляется, Quadratic Time: O(n²)когда дело доходит до производительности.

class BubbleSort: 
  def __init__(self, arr):
    self.arr = arr;

  def bubbleSort(self):
    count = 0;
    lastIndex = len(self.arr) - 1;
    
    while(count < lastIndex):
      if(self.arr[count] > self.arr[count + 1]):
        self.swap(count)  
      count = count + 1;

      if(count == lastIndex):
        count = 0;
        lastIndex = lastIndex - 1;   

  def swap(self, count):
    temp = self.arr[count];
    self.arr[count] = self.arr[count + 1];
    self.arr[count + 1] = temp;
    
arr = [9, 1, 5, 3, 8, 2]
p1 = BubbleSort(arr)

print(p1.bubbleSort())
Thalaivar
источник
-1

Ответы, предоставленные the-fury и Мартином Коте, устранили проблему бесконечного цикла, но мой код по-прежнему работал некорректно (для большего списка он не сортировался бы правильно). В итоге я отказался от unsortedпеременной и вместо этого использовал счетчик.

def bubble(badList):
    length = len(badList) - 1
    n = 0
    while n < len(badList):
        for element in range(0,length):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                n = 0
            else:
                n += 1
    return badList

if __name__ == '__main__':
    mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99]
    print bubble(mylist)

Если бы кто-нибудь мог указать в комментариях, как улучшить мой код, я был бы очень признателен.

Джош Хант
источник
Вы можете ускорить пузырьковую сортировку, пропустив часть вашего списка, которая, как вы знаете, уже отсортирована (из-за предыдущих итераций). См en.wikipedia.org/wiki/Bubble_sort#Alternative_implementations
Blorgbeard выходит
3
опять же, все, что вам действительно нужно сделать, это использовать логическое значение (назовите его нетронутым). объявите это вне вашего цикла; цикл до нетронутого = true. в вашем цикле while установите значение true; в теле вашего if, установите нетронутый как ложный. Поступив так, вы можете отказаться от своего дела else. таким образом, если вы когда-нибудь переключите два элемента, ваш цикл продолжится; если вы этого не сделаете, петля не будет.
Пол Сонье
-1

Попробуй это

a = int(input("Enter Limit"))


val = []

for z in range(0,a):
    b = int(input("Enter Number in List"))
    val.append(b)


for y in range(0,len(val)):
   for x in range(0,len(val)-1):
       if val[x]>val[x+1]:
           t = val[x]
           val[x] = val[x+1]
           val[x+1] = t

print(val)
Вивек Шинде
источник
-1

idk, если это может помочь вам через 9 лет ... это простая программа пузырьковой сортировки

    l=[1,6,3,7,5,9,8,2,4,10]

    for i in range(1,len(l)):
        for j in range (i+1,len(l)):
            if l[i]>l[j]:
                l[i],l[j]=l[j],l[i]
деревенщина
источник
-1
def merge_bubble(arr):
    k = len(arr)
    while k>2:
        for i in range(0,k-1):
            for j in range(0,k-1):
                if arr[j] > arr[j+1]:
                    arr[j],arr[j+1] = arr[j+1],arr[j]

        return arr
        break
    else:
        if arr[0] > arr[1]:
            arr[0],arr[1] = arr[1],arr[0]
        return arr 
user11689497
источник
-1
def bubble_sort(l):
    for i in range(len(l) -1):
        for j in range(len(l)-i-1):
            if l[j] > l[j+1]:
                l[j],l[j+1] = l[j+1], l[j]
    return l
Амандип Сингх
источник
Было бы лучше добавить пояснения к вашему коду.
Масуд Рахими
-1
def bubble_sorted(arr:list):
    while True:
        for i in range(0,len(arr)-1):
            count = 0
            if arr[i] > arr[i+1]:
                count += 1
                arr[i], arr[i+1] = arr[i+1], arr[i]
        if count == 0:
            break
    return arr
arr = [30,20,80,40,50,10,60,70,90]
print(bubble_sorted(arr))
#[20, 30, 40, 50, 10, 60, 70, 80, 90]
Luffy
источник
-3

def bubbleSort(a): def swap(x, y): temp = a[x] a[x] = a[y] a[y] = temp #outer loop for j in range(len(a)): #slicing to the center, inner loop, python style for i in range(j, len(a) - j):
#find the min index and swap if a[i] < a[j]: swap(j, i) #find the max index and swap if a[i] > a[len(a) - j - 1]: swap(len(a) - j - 1, i) return a

Ник Радаев
источник