Bubble sort using ADT in python

Question

I am given an assignment, where the input will be a list and my task is to bubble sort the list to ascending order. Here's a sample input and output that I want.

Input:

45 22 34 79 23

Output:

22 45 34 79 23
22 34 45 79 23
22 34 45 79 23
22 34 45 23 79
22 34 45 23 79
22 34 45 23 79
22 34 23 45 79
22 34 23 45 79
22 23 34 45 79
22 23 34 45 79

However I tried a piece of code but it didn't work, the I tried:

l = list(map(int, input().split()))

swapped = True
while swapped:
    swapped = False
    for i in range(len(l) - 1):
        if l[i] > l[i + 1]:
            l[i] , l[i + 1] = l[i + 1], l[i]
            swapped = True
            print(*l)

I just wanted to know the python code and explanation of the code that could provide me result exactly like the output in assignment.

trincot · Accepted Answer · 2023-09-27 18:16:50Z

3

The algorithm is correct, but the output does not correspond to the expected output for two reasons:

Your code performs a print when a swap has happened, but we can see from the example's expected output that there are consecutive lines that are copies, which indicates that we need to print also when no swap happened. For this you must move your print outside of the if block (unindent)

After this fix, there will be more lines in the output than are expected. And this brings us to the second reason:

Your code's inner loop always iterates the data to len(l) - 1, but this is not necessary. The array will have a sorted section at its right end that grows with at least one element at each iteration of the outer loop, so it is not needed that the inner loop iterates over that sorted partition. So make the number of iterations for that loop dynamic: reduce it by one each time that loop is executed from scratch.

For instance, with these minimal adjustments your code could produce the expected output:

l = list(map(int, inp.split()))

swapped = True
n = len(l) - 1  # number of iterations of the inner loop
while swapped:
    swapped = False
    for i in range(n):
        if l[i] > l[i + 1]:
            l[i] , l[i + 1] = l[i + 1], l[i]
            swapped = True
        print(*l)  # also print when no swap is performed
    n -= 1  # next time the inner loop can make one less iteration

Now the output for the example input will be:

22 45 34 79 23
22 34 45 79 23
22 34 45 79 23
22 34 45 23 79
22 34 45 23 79
22 34 45 23 79
22 34 23 45 79
22 34 23 45 79
22 23 34 45 79
22 23 34 45 79

answered Sep 27, 2023 at 18:16

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

UpAndAdam Over a year ago

You addressed the issues properly about his mostly correct code, and covered what I thought was lacking about the other answers, the key explanatory bit about the growing sorted section at the "right end". Didnt think I'd be upvoting anything about bubble sort but here I am doing it. Bravo sir.

Viknesh TPK Over a year ago

I have tried your code and be able to pass 5/6 test case. I have updated the question. Please do check the question for the updated info.

trincot Over a year ago

Your edit was rolled back, because you inserted answer code into your question. Instead, append the test input and expected output for it(!) to your question as a second example. Don't destroy anything you already had in the question, and don't modify your code that is in the question.

Monkeysoop · Accepted Answer · 2023-09-27 18:02:28Z

0

code is from https://www.programiz.com/dsa/bubble-sort

def bubbleSort(array):
  for i in range(len(array)):
    for j in range(0, len(array) - i - 1):
      if array[j] > array[j + 1]:
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp
      print(*array)
        
        
bubbleSort([45,22,34,79,23])

edit: the site has an explanation of the algorithm

answered Sep 27, 2023 at 18:02

Monkeysoop

224 bronze badges

1 Comment

Thierry Lathuille Over a year ago

Please note that Programiz terms and conditions state that " you may not in any form or by any means reproduce, copy, adapt, translate, store, distribute, re-distribute, purport to sub-license, on-sell, print, display in public, perform, communicate to the public or create derivative works from the Service, any Materials or any substantial part of either. ". Note also that we expect original content in the answers. You might put such a link in a comment, though, once you reach the necessary reputation (50)

Collectives™ on Stack Overflow

Bubble sort using ADT in python

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related