Bubble Sort Домашнее задание

Question

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

Это моя попытка в 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 Я знаю, что на самом деле у меня не должно быть отпечатков в функции, и у меня должен быть возврат, но я просто еще этого не сделал, так как мой код на самом деле еще не работает.

Answer 1

Чтобы объяснить, почему ваш скрипт не работает сейчас, я переименую переменную 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 для "индекса".

  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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 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

Answer 6

# Очень простая функция, которая может быть оптимизирована (очевидно) за счет уменьшения проблемного пространства 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 

Answer 7

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

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. Я знаю, что прошло много времени с тех пор, как этот вопрос был опубликован, но я просто хотел поделиться этой идеей.

Answer 8

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

Answer 9

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]

печать bubbleSort(alist)

Answer 10

Я свежий новичок, начал читать о 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)

Answer 11

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

Answer 12

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

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

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)

Answer 13

У вас там есть пара ошибок. Первый в длину, а второй в вашем использовании несортированные (как указано в 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)

Эта: Вы правы, вышеперечисленное глючит как ад. Мой плохой, потому что я не тестировал еще несколько примеров.

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

Answer 14

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]))

Answer 15

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

Answer 16

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 )

Answer 17

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)

Answer 18

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

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]

Answer 19

      def bubblesort(L,s):
    if s >-1 :
        bubblesort(L,s-1)
        for i in range(len(L)-1-s):
            if L[i]>L[i+1]:
                temp = L[i+1]
                L[i+1] = L[i]
                L[i] = temp

    return L

Nlist = [3,50,7,1,8,11,9,0,-1,5]
print(bubblesort(Nlist,len(Nlist)))

Answer 20

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

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

Answer 21

Я хотел бы поделиться своим решением:

def bubble_sort(list_):
    for i in range(len(list_)):
        for j in range(i, len(list_)):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]
return list_

Тестовый пример:

a = [8,1,2,4,1,3,5,1,5,6,1,8]
bubble_sort(a)

Результат:

[1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 8, 8]

Answer 22

Вот другой вариант пузырьковой сортировки без 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())

Answer 23

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 

Answer 24

ИДК, если это может помочь вам через 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]

Answer 25

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

Answer 26

Попробуй это

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)

Answer 27

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]

Answer 28

Ответы, предоставленные the-fury и Martin Cote, устранили проблему бесконечного цикла, но мой код все равно не работал бы правильно (для большого списка он не будет корректно сортироваться). Я бросил 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)

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

Answer 29

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