Пузырьковая сортировка в Python 3

Question

Напишите программу пузырьковой сортировки в Python 3. Пузырьковая сортировка - это алгоритм, который сортирует список значений по порядку.

Я пытаюсь получить этот результат к концу.

Original List: 4, 9, 74, 0, 9, 8, 28, 1
Sorted List: 0, 1, 4, 8, 9, 9, 28, 74
Number of Passes: 6

Как мне это сделать?

import sys
def bubblesort(mylist):
        changes = passes = 0
        last = len(mylist)
        swapped = True
        print("Original List: ", ','.join(map(str, mylist)) )
        while swapped:
                swapped = False
                for j in range(1, last):
                        if mylist[j - 1] > mylist[j]:
                                mylist[j], mylist[j - 1] = mylist[j - 1], mylist[j]  # Swap
                                changes += 1
                                swapped = True
                                last = j
                if swapped:
                        passes += 1
                        print('Pass', passes, ':' , ','.join(map(str, mylist)))

        print("\nOriginal List: ", ','.join(map(str, mylist)) )
        print("Sorted List: ", ','.join(map(str, mylist)))
        print("Number of passes =",passes)
        return mylist

print("Welcome to a Bubble Sort Algorithm in Python!")
mylist = " "
while True:
    print("\nBubble sort in Python 3 Program")
    mylist = input("Enter a the value or type Exit to exit: ")
    if (mylist == "exit" or mylist == "Exit" or mylist == "EXIT"):
        print("Goodbye")
        sys.exit()
    else:
        mylist = [int(v) for v in mylist.split(',')]
        bubblesort(mylist)

Вывод, который я получаю:

Original List:  4,9,74,0,9,8,28,1
Pass 0 : 4,9,74,0,9,8,28,1
Pass 1 : 4,9,0,9,8,28,1,74
Pass 2 : 4,0,9,8,9,1,28,74
Pass 3 : 0,4,8,9,1,9,28,74
Pass 4 : 0,4,8,1,9,9,28,74
Pass 5 : 0,4,1,8,9,9,28,74
Pass 6 : 0,1,4,8,9,9,28,74


Original List: 0, 1, 4, 8, 9, 9, 28, 74
Sorted List: 0, 1, 4, 8, 9, 9, 28, 74
Number of Passes: 6

Результат, который я хочу:

Original List: 4, 9, 74, 0, 9, 8, 28, 1
Pass 1:  4, 9, 0, 9, 8, 28, 1, 74
Pass 2:  4, 0, 9, 8, 9, 1, 28, 74
Pass 3 : 0, 4, 8, 9, 1, 9, 28, 74
Pass 4 : 0, 4, 8, 1, 9, 9, 28, 74
Pass 5 : 0, 4, 1, 8, 9, 9, 28, 74
Pass 6 : 0, 1, 4, 8, 9, 9, 28, 74

Original List: 4, 9, 74, 0, 9, 8, 28, 1
Sorted List: 0, 1, 4, 8, 9, 9, 28, 74
Number of Passes: 6

Answer 1

Это простое приложение для сортировки пузырьков в python

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 2

Во-первых, это занимает 7, потому что последний проход не имеет перестановок (вот когда он знает, что это сделано).Перемещение passes += 1 и оператора печати в конец цикла покажет это правильно.

Для нужного вывода измените порядок событий в цикле и добавьте оператор if для проверки изменений.,[Ниже]

Для вывода фактических проходов (включая последний, где нет изменений) просто удалите оператор if из кода ниже.

import sys

def bubblesort(mylist):
    changes = passes = 0
    last = len(mylist)
    swapped = True
    print("Original List: ", ','.join(map(str, mylist)) )
    while swapped:
        swapped = False

        for j in range(1, last):
            if mylist[j - 1] > mylist[j]:
                mylist[j], mylist[j - 1] = mylist[j - 1], mylist[j]  # Swap
                changes += 1
                swapped = True
                last = j

        # Only prints and increases number of passes if there was a swap
        # Remove if statement for the correct number of passes
        if(swapped):
          passes += 1
          print('Pass', passes, ':' , ','.join(map(str, mylist)))

    print("Number of passes =",passes)
    return mylist

print("Welcome to a Bubble Sort Algorithm in Python!")

mylist = " "
while True:
    print("\nBubble sort in Python 3 Program")
    mylist = input("Enter a the value or type Exit to exit: ")
    if (mylist == "exit" or mylist == "Exit" or mylist == "EXIT"):
        print("Goodbye")
        sys.exit()
    else:
        mylist = [int(v) for v in mylist.split(',')]
        bubblesort(mylist)

Answer 3

Вот решение:

    import sys
    def bubblesort(mylist):
        changes = passes = 0
        last = len(mylist)
        swapped = True
        print("Original List: ", ','.join(map(str, mylist)) )
        while swapped:
            swapped = False
            for j in range(1, last):
                if mylist[j - 1] > mylist[j]:
                    mylist[j], mylist[j - 1] = mylist[j - 1], mylist[j]  # Swap
                    changes += 1
                    swapped = True
                    last = j
            if swapped:
                passes += 1
                print('Pass', passes, ':' , ','.join(map(str, mylist)))

        print("Number of passes =",passes)
        return mylist

    print("Welcome to a Bubble Sort Algorithm in Python!")

    mylist = " "
    while True:
        print("\nBubble sort in Python 3 Program")
        mylist = input("Enter a the value or type Exit to exit: ")
        if (mylist == "exit" or mylist == "Exit" or mylist == "EXIT"):
            print("Goodbye")
            sys.exit()
        else:
            mylist = [int(v) for v in mylist.split(',')]
            bubblesort(mylist)

Чтобы не сортировать уже отсортированный список снова и не добавлять +1 к проходам, необходимо добавить эту строку:

    if swapped:
            passes += 1
            print('Pass', passes, ':' , ','.join(map(str, mylist)))

Затем поместите строку, в которой отображается список, в цикл ПОСЛЕ всех действий с ним, если вы не хотите получать оригинальное письмо после первого проходного цикла.

Answer 4

Относительно форматирования текста - замените ',' на ', ' (добавьте пробел).

Относительно печати прохода 0 (который еще до того, как вы запустились) - переместите вызов печати на следующий после passes += 1

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

Измененный код будет выглядеть так:

import sys
def bubblesort(mylist):
    changes = passes = 0
    last = len(mylist)
    swapped = True
    print("Original List: ", ', '.join(map(str, mylist)) )
    while swapped:
        swapped = False
        for j in range(1, last):
            if mylist[j - 1] > mylist[j]:
                mylist[j], mylist[j - 1] = mylist[j - 1], mylist[j]  # Swap
                changes += 1
                swapped = True
                last = j
        passes += 1
        print('Pass', passes, ':', ', '.join(map(str, mylist)))

    print("Number of passes =",passes)
    return mylist

print("Welcome to a Bubble Sort Algorithm in Python!")

while True:
    print("\nBubble sort in Python 3 Program")
    mylist = input("Enter a the value or type Exit to exit: ")
    if (mylist == "exit" or mylist == "Exit" or mylist == "EXIT"):
        print("Goodbye")
        sys.exit()
    else:
        mylist = [int(v) for v in mylist.split(',')]
        bubblesort(mylist)