CODEWITHSUNDEEP
pythonbubble-sort
sung moon
sung moon

Reputation: 21

Need help understanding bubble sort solution code

So, I was learning about Bubble Sort and saw this code:

def bubblesort(list_a):
    indexing_length = len(list_a) - 1  
    sorted = False

    while not sorted:  
        sorted = True  
        for i in range(0, indexing_length):
            if list_a[i] > list_a[i+1]:
                sorted = False  
                list_a[i], list_a[i+1] = list_a[i+1], list_a[i]  # flip position

    return list_a

I tried running this code on my notebook so I could understand this better. I tried 5, 2, 3, 7, 10, 1, 8 and the process was like this:

--> 2, 5, 3, 7, 10, 1, 8
--> 2, 3, 5, 7, 10, 1, 8
--> 2, 3, 5, 7, 1, 10, 8
--> 2, 3, 5, 7, 1, 8, 10

I ended up with unsorted array because I thought for loop does only one iteration. Am I understanding something wrong? Could anyone explain it to me little bit easier please?

Upvotes: 1

Views: 225

Answers (2)

Ali Hassan
Ali Hassan

Reputation: 966

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. This sorting algorithm also known as Brute Force Approach, the reason is that during sorting each element of list will compare with the every other element of the same list and if the compared number are not in order so it will swap the position. Lets have a look on your example list [5, 2, 3, 7, 10, 1, 8].

1st pass: compare 0th index(5) and 1st index(2) and compare it if 0th index(5) > 1st index(2) then it will swap the position else no swap counter will increase. [5, 2, 3, 7, 10, 1, 8] condition True(5 > 2), SWAP [2, 5, 3, 7, 10, 1, 8], then again compare [2, 5, 3, 7, 10, 1, 8] condition True(5 > 3), SWAP [2, 3, 5, 7, 10, 1, 8], and so on.

  • [2, 3, 5, 7, 10, 1, 8] True(10>1).
  • [2, 3, 5, 7, 1, 10, 8] True(10>8).
  • [2, 3, 5, 7, 1, 8, 10]

2nd pass:

  • [2, 3, 5, 7, 1, 8, 10]
  • [2, 3, 5, 7, 1, 8, 10]
  • [2, 3, 5, 7, 1, 8, 10] True(7>1).
  • [2, 3, 5, 1, 7, 8, 10]
  • [2, 3, 5, 1, 7, 8, 10]

3rd pass:

  • [2, 3, 5, 1, 7, 8, 10]
  • [2, 3, 5, 1, 7, 8, 10] True(5>1).
  • [2, 3, 1, 5, 7, 8, 10]
  • [2, 3, 1, 5, 7, 8, 10]

4th pass:

  • [2, 3, 1, 5, 7, 8, 10] True(3>1).
  • [2, 1, 3, 5, 7, 8, 10]
  • [2, 1, 3, 5, 7, 8, 10]

5th pass:

  • [2, 1, 3, 5, 7, 8, 10] True(2>1).
  • [1, 2, 3, 5, 7, 8, 10]
  • [1, 2, 3, 5, 7, 8, 10]

6th pass:

  • [1, 2, 3, 5, 7, 8, 10]

7th pass:

  • [1, 2, 3, 5, 7, 8, 10]

    def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        print(arr[i])
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                print(arr[j], arr[j+1])
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            print(arr)

arr = [5, 2, 3, 7, 10, 1, 8]
bubbleSort(arr)
print("Sorted array")
print(arr)

Upvotes: 2

water_ghosts
water_ghosts

Reputation: 736

The list will be [2, 3, 5, 7, 1, 8, 10] after the for loop completes the first time, but the value of sorted will be False. Since you're still inside the while not sorted loop, everything inside that loop will run again, including another for loop starting at index 0.

This will keep going until the list is sorted when the for loop completes, since that will make the while loop's condition False.

Upvotes: 0

Related Questions