Bubble Sort in Python 3

Question

Write a bubble sort program in Python 3. A bubble sort is an algorithm that will sort a list of values into order.

I am trying to get this result towards the end.

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

How can I accomplish it?

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)

The output that I get:

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

The result that I want:

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

score 1 · Answer 1 · answered Apr 28 '20 at 06:13

Each time you go through the list, you assume the list is sorted. (1)

Then you iterate the list checking every pair, if the pair is not in the correct order. Swap them. (2)

Because of that incorrect pair: "The whole list must still not be sorted, right?" (assuming again) (3)

Therefore you must repeat until at some point the if-condition is not hit. Then that must mean they are all in correct order. You stop (and print). (4)

def bubble(original_list):
    l = original_list.copy() # make a temporary list
    sorted = False  # Assume list is not sorted at first to kick-start the while loop
    count = 0
    while not sorted: 
        sorted = True # (1) Assume that it's sorted
        for i in range(0, len(l) - 1): # (2) len(l)-1 because the last element                                          
                                       # has no thing on the right to compare to.
            if l[i] > l[i + 1]: # (2) check condition
                sorted = False  # (3) 
                count += 1
                l[i], l[i + 1] = l[i + 1], l[i] # (2) swap

    print("Original: {}".format(original_list)) # (4)
    print("Sorted: {}".format(l))
    print("Number of swaps: {}".format(count))

Conclusion: Some programming people love assumptions.

score 0 · Answer 2 · answered Jan 26 '19 at 21:48

Regarding text formatting - replace the ',' with ', ' (add a space).

Regarding printing of Pass 0 (which is before you even run) - move the print invocation to be after passes += 1

And finally - the number of passes done by bubble sort in your example would be 7 - 6 passes in which you still modify the list, and a final pass in which you detect the list is sorted.

The modified code would look be:

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)

Domenick · Answer 3 · 2019-01-26T22:01:02.517

First, it does take 7 because the last pass has no swaps (that's when it knows its done). Moving the passes += 1 and the print statement to the end of the loop will show this correctly.

For the output you want, change around the order of events in your loop and add an if statement to check for changes. [ Given Below ]

For the output of the actual passes (including the last one where there is no change) just remove the if statement from the code below.

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)

score 0 · Answer 4 · answered Jan 26 '19 at 22:00

That's the solution:


    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)

In order to not to sort already sorted list again and not to add +1 to passes you have to add this line:


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

Next, put the line where you display a list in loop AFTER all actions with it if you don't want to get original letter after the first pass through loop.

score 0 · Answer 5 · answered Oct 23 '19 at 17:11

I believe this is the most effective (and simple to understand) bubble sort method:

def bubbleSort(arr):
n = len(arr)

for i in range(n):  # i : 1 -> n

    for j in range(0, n - i - 1):  # j -> n -i -1 , -1 for the j+1 comparison of last element
        if arr[j] > arr[j + 1]:  # if current is bigger than next
            arr[j], arr[j + 1] = arr[j + 1], arr[j]  # swap current and next
return arr

score 0 · Answer 6 · answered Feb 13 '20 at 12:21

Use code below and repeat for the numbers in the list.

theList = [18, 9, 6, 10]
currentNumber = theList[0]
nextNumber = theList[1]

`if` nextNumber < currentNumber:
   toSwap = theList[0]
   theList[0] = theList[1]
   theList[1
           ] = toSwap

currentNumber = theList[1]
nextNumber = theList[2]

score 0 · Answer 7 · edited Feb 23 '20 at 14:21

0

def bubblesort(lis):
    num_of_iterations = 0
    for i in range(len(lis)):
        for j in range(i):
            if lis[j]>lis[j+1]:
                lis[j], lis[j+1] = lis[j+1], lis[j]
                num_of_iterations += 1

    print(lis,"\n num_of_iterations : ",num_of_iterations)

y =[19,2,31,45,6,11,121,27]
bubblesort(y)

edited Feb 23 '20 at 14:21

kaya3

47,440
4
68
97

answered Feb 23 '20 at 14:19

Samyukta Reddy Vanga

36
2

1

Welcome to Stack Overflow. While this code snippet may solve the problem, **[including an explanation](//meta.stackexchange.com/q/114762) really helps to improve the quality of your post**. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. – kaya3 Feb 23 '20 at 14:23

Bubble Sort in Python 3

7 Answers7

Linked