Lists, Bubble Sort and its Python Counterparts

     

This is a List.

    Lists, in almost every aspect of the world, refer to a set of numbers in whichever order in which ever amount of said numbers.

    Lists, concerning the computer science field by themselves are simply just a sequence of elements, however, these lists are not just confined to being numbers. They can be strings, integers, or even other custom elements. Another name to call these Lists would be to label them as arrays.

The main focus of this Blog is to document, explain and explore together the possibilities of Lists. Mainly, the sorting aspect of lists. Sorting is an essential part of Lists. Complementing this fact is the existence of built-in methods that provide the user with the ability to arrange said lists in any order of their choice. Now, there are several different types of ways to sort these lists which are more commonly referred to as algorithms:

1.  Merge Sort (Divides a List into half, sorts them and repeats)
   
2.  Bubble sort(Compares adjacent values, swaps and repeats)
3. Selection sort(Puts smallest at start and repeats)

The sorting algorithm that is going to be covered in this post is the Bubble Sort algorithm.

First, what even is Bubble sort?

    Bubble sort, in simple terms is an algorithm that arranges a numbered list into its ascending order through the use of comparisons.

    Lets say we have a list.

[8, 4, 9]

    What would the algorithm do to sort this into its ascending order? Well, first it would compare index 0 and index 1 which correspond to 4 and 8. These two numbers would then be compared and since 

8>4

The algorithm would swap the two indexes' places, resulting in

[4, 8, 9]

The swapped number, in this case, 8, is then compared with index 2, corresponding to 9.

[4, 8, 9]

But this time, upon comparing,

8<9

When this happens, the algorithm stops the comparison and leaves the list as it is. If there were to be another element in the list, the algorithm would move on to index 2 to compare with index 3 but since index 2 is the last position of the list, the algorithm has completed its task and has returned a ordered list in the ascending order. If the user would want a list in the descending order, they could make it so the algorithm only swaps if:

index(x)<index(x+1)

Converting this into python code nets this program(simplified):

My own Explanation of the code:

#1 A function is defined with the use of the keyword "def" followed by the function's name and its parameter. The parameter acts as sort of a temporary variable to store values in. In this case the valued stored in the variable would be in accordance with #11.

[1,4,5,2,8,9,6,7,3,4]

#2 The variable which I named 'Length' for convenience's sake is to be used as a reference point on where the program is. 1 is subtracted from the length of the list because on the last number of the list, the program would encounter it before any comparisons take place and -1 is used as a Stop sign to indicate there is not another number after the last number.

#3  By defining this variable, 'sorted' as False, it can be used to break the program out of its loop. If not for this variable, the program would continue to run indefinitely.

#4 Since the program requires an unspecified amount of loops to complete its task, a while loop is created. This is unlike the 'for _ in _()" loops that only perform a definite amount of iterations. By using 'while not sorted', the program is told as long as the Boolean value of the variable "sorted" remains False, the loop as to continue.

#5 Enabling the while loop mentioned above to break and only triggers if "list[x]>list[x+1]" is not true.

#6 Mentioned above, setting reference points for the program to inform it of its position in the list. Creating a for loop to start from 0 till the amount of elements in 'lists' - 1.

#7 This is where the comparisons will take place. Here, the program checks if a element in position x is greater then an element in position x+1 using a conditional statement. 

#8 When "list[x]>list[x+1]" is true, the variable 'sorted' is set back to False, which will make the while loop iterate one more time.

#9 This is where the program swaps the element at position x with the element at position x+1 (element at the left with element at the right) if "list[x]>list[x+1]" is true. The code from #6-#9 is iterated again but this time starting from the position to the right of position x.

    Lines 13-19 is to facilitate code to be able to take in a sequence of numbers in any order(Lists), and then prints out the Unsorted and Sorted versions when the user-defined bubble_sort function is invoked alongside the value that will be assigned to the temporary variable “list”. 

   The user is first asked to input how many numbers long the list that is going to be ordered should be. The type of input is restricted to being numbers (“int(input()”). Then a for loop is created that accepts in these numbers and stops once the limit (“n” , the maximum amount of elements the user wants in the string) has been reached. Upon an integer being inputed, the integer is appended (added) to the existing array variable, “lst”. This is one after every input of integers. The function “bubble_sort()” is then invoked with the parameter as lst, our user inputted list. 

    As output, the unsorted user-inputted list is printed out followed by the sorted version of said list after running the user defined function. 

Sources

https://ecomputernotes.com/python/bubble-sort-in-python

https://www.educba.com/bubble-sort-in-python/

https://www.youtube.com/watch?v=g_xesqdQqvA

https://linuxhint.com/bubble-sort-python/