Python

Bubble sort python

Sorting is the process of arranging the values in order present in the form of lists. Different types of sorting discriminate because of their usage techniques and approaches like quick sort, selection sort, merge sort, bubble sort, etc. This tutorial is related to the bubble sort.

Bubble sort

This is the arranging of elements of an array that deals with using the simplest sorting algorithm applied by swapping the adjacent elements repeatedly if the order is wrong.

Bubble sort working

To sort the values in ascending order, then the first iteration includes the process of comparing and swapping. The first index value and the second one are compared. If the condition is fulfilled, swapping occurs and is repeated till the end.

Algorithm / pseudo code for bubble sort

function(array)
  for i  rightvalue
      swap leftvalue and rightvalue
end function

Example 1

The bubble sort mechanism is applied to the python programming language by using the function named bubble sort. The syntax for the function is that a keyword ‘def’ is used along with the function’s name. In the function parameter, we have passed an array that is to be sorted by the function. So now we will see the complete functionality or say that the core of the whole sorting process is defined in the function’s body. Firstly we will declare the length of the array to a variable through an assignment operator by using the len() built-in function.

# n = len(arr)

For accessing any element in an array, we always use a FOR loop in any programming language. Just like that, Python also utilizes the “for” loop in the sorting process to make it feasible for the user. So the array will be traversed by using a for a loop.

# For I in range (n – 1):

Here “i” is the variable representing the index number in the array having the array of a fixed size minus one. As ‘n’ represents the size of the array, so (n-1) represents traversing of the loop to the position of the size minus one so that we can iterate the loop one time again after a single iteration.

As described above, the two closest adjacent indexes are compared for the bubble sort. By using the above loop, we will access one index. Say the first one, to access the next index; we further need a loop. This is the inner loop, and the above-mentioned is declared as an outer loop. This phenomenon resembles the two-dimensional array (2d). So let us declare the inner loop.

# for j in range (0, n-i-1):

The ‘j’ variable is like the ‘i’ of the outer loop, but this will represent the next value of the current value of index ‘i’, as we have applied the logic of ‘n-i-1’, so the loop will iterate till the position of subtracting the value of “i” from the size of the array along with ‘-1’ value, this will lead to the adjacent two indexes in the array.

We have accessed two values in the array, and it is time to compare them as we know that the comparison is made through the angular brackets. We need to use the ‘>’ bracket for the ascending sorting.

If arr[j] > arr[j + 1]:
arr[j], arr[j +1] = arr[j + 1], arr[j]

If the value at the left side that is accessed first is greater than the value on the right, accessed later, then both the values are swapped directly without using any involvement of third place. In the other case, move towards the next position. This was the main logic function of the bubble sort.

Jump outside the loops. After that, we declare the array and pass it to the function through a function call.

Bubblesort(arr).

After that, the sorted array will be printed. In the resultant console, the resultant value will be displayed.

You can see that the input array contains the random values, whereas, in the resultant array, all the elements are sorted in ascending order.

Example 2

The above example deals with continuing all possible comparisons even if the whole array is already sorted. This leads to the time extension of the execution throughout the array. So to make the execution time-limited, we will use a third variable. Here we use a Boolean variable to set the variable’s value as true if swapping occurs. Otherwise, it is considered false.

After each iteration, if no swapping occurs due to swapping, the value will be false. It refers to when all the elements in an array are already sorted, and there is no further requirement to sort them. This phenomenon is easily used and can reduce the execution time and benefit from optimizing bubble sort.

Inside the bubble sort function, the length has been declared a variable. An additional variable swapped is declared as false by default initially. But its value changes whenever the process of swapping takes place.

Swapped = false

Inside both the outer and the inner loop, the comparison between the values of specified indexes occurs; if the values need to be exchanged, then the swapped variable is turned into ‘true,’ and the values are swapped successfully.

But if no two values are swapped, when the values are already arranged, then no swapping occurs, so the swapped variable remains false. And then the break occurs. This check is attained through an if-statement.

If swapped == false

Break

This break will be responsible for stopping the loop from executing further. Like in this example, the break will occur at the index of 1,2 and 3.

After saving the file, the execution values can be seen through the console. You can see the resultant values that are arranged in ascending order.

Example 3

This example follows the same concept as explained in the second example by using the same swapped Boolean with the use of another variable at the time of swapping the values. This is a temp value. This is a template that stores the values temporarily.

The same above example is used here. Only consider the swapping procedure here. The first index value is saved in the variable ‘temp’ inside the loops. And that space is filled with the value next to it in the array to which the previous value is compared. And that next value is now replaced with the value present in the temp. This is called indirect assigning of values, and it uses more steps than the direct assignment of values.

The swapped variable will be declared as true in the swapping case. Execute the code to see the results.

Conclusion

The article ‘bubble sort’ contains a brief introduction to the sorting methodology through the algorithm. A detailed process of bubble sort with a step-by-step approach is discussed. The Spyder tool is recommended for the implementation of Python-related programs. Each elementary example depicts the use of bubble sort in Python language.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.