CODEWITHSUNDEEP
pythonalgorithm
user10509717
user10509717

Reputation:

Explain the bubble sort algorithm?

I'm trying to learn more about algorithms and i'm looking into the bubble sort algorithm. I found the script for it on github but I cant really understand it. I'm sorta new to python so can someone explain to me what's going on in this script.

from __future__ import print_function

def bubble_sort(arr):
  n = len(arr)
  # Traverse through all array elements
  for i in range(n):
    # Last i elements are already in place
      for j in range(0, n-i-1):
        # traverse the array from 0 to n-i-1
        # Swap if the element found is greater
        # than the next element
        if arr[j] > arr[j+1] :
              arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

if __name__ == '__main__':
    try:
        raw_input          # Python 2
    except NameError:
        raw_input = input  # Python 3
    user_input = raw_input('Enter numbers separated by a comma:').strip()
    unsorted = [int(item) for item in user_input.split(',')]
    print(*bubble_sort(unsorted), sep=',')

Upvotes: 1

Views: 2802

Answers (2)

karafar
karafar

Reputation: 516

from __future__ import print_function Here we are essentially bringing in code that was written by somebody else, so that we may use it.

def bubble_sort(arr): This is is a function definition. A function definition is preceded by the keyword def. Following that is the function's name. In this case it is called bubble_sort. What we have in the parenthesis are called parameters. A parameter is something we give to a function, so that the function may use it, e.g., multiply the parameter by a number, sort the list, or send some information to a server.

Since we are on the topic of functions, I would suggest looking up process abstraction.

arr Here I am referring to arr within the function's definition. It is short for array, which is a list type. In python we could define an array like so fruits = ["banana", "apple", "orange"]. Arrays are useful for grouping together like pieces of information, and in python I believe this are actually known as a list type. So, conceptually, it may be easier to imagine a list rather than the more esoteric array.

n = len(arr) We are literally assigning the length of the array into the variable n. This is probably shorthand for number of elements. len(arr) is a function that takes an array/list, and returns its length. Similarly, one could call print len(arr) or simply len(arr).

for j in range(0, n-i-1): This is a bit more complicated since it requires an understanding of the algorithm in play, i.e., bubblesort. I won't explain how bubblesort works since there is probably a ton of videos online, but I will explain the bit within the parenthesis.

(0, n-i-1) We want to make comparisons between our current element and the ones preceding it. The ones preceding our current element are greater than the current element. This means if we are at element i, then we have no need to compare elements from i to n, inclusive. We subtract i from n, which leaves us with elements 0 through i. We don't need to compare i to itself, so we subtract an additional 1. This is due to j cycling through the array, and being potentially the same as i.

if arr[j] > arr[j+1] : This is a conditional statement, also known as a branching statement, or an if-statement. The condition, arr[j] > arr[j+1], is true with the element at position j is greater than the one at j+1.

arr[j], arr[j+1] = arr[j+1], arr[j] I think this is shorthand for swapping. A simple swap is shown below.

temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp

return arr Returns the sorted array.

The last bit I am not familiar with since I don't use python much. Perhaps this could be some research for you.

Hopefully this helps.

Upvotes: 2

Luke
Luke

Reputation: 473

Visualize the array as a vertical list of numbers, with the first element (index 0) on the bottom, and the last element (index n-1) at the top. The idea of bubble sort is that numbers "bubble up" to the top, into the place where they belong.

For example, [2,3,1] would first look at 2 and 3, and not do anything because they're already in order. Then it would look at 3 and 1, swapping them since 3>1 and getting [2,1,3]. Then we repeat by looking at 2 and 1, swapping them since 2>1 to get [1,2,3], which is in order.

The idea is that "3" and then "2" bubbled up to the correct position.

Note that after the 3 bubbled up, we don't have to compare 2 and 3, because we know the last element is already higher than everything before it. In general, after i iterations of bubble sort, there's no need to compare the last i elements.

Upvotes: 2

Related Questions