A simple solution to the sorting problem is the bubble sort algorithm, which rearranges the values by iterating over the list multiple times, causing larger values to bubble to the top or end of the list. To illustrate how the bubble sort algorithm works, suppose we have four Pool Balls that we want to order from smallest to largest face value. We start by laying the balls on a table as shown here:
The algorithm requires multiple passes over the balls, with each pass starting at the first ball and ending one ball earlier than on the previous iteration. During each pass, the ball in the first and second positions are compared. If the first is larger than the second, the two balls are swapped.
Next, the balls in positions two and three are compared. If the first one is larger than the second, they are swapped. Otherwise, we leave them as they were.
This process continues for each successive pair of balls until the ball with the
largest face value is positioned at the end.
The next two passes over the balls are illustrated below. In the second pass the ball with the second largest face value is positioned in the next-to-last position.
In the third and final pass, the first two balls will be positioned correctly.
The efficiency of the bubble sort algorithm only depends on the number of keys in the array and is independent of the specific values and the initial arrangement of those values. To determine the efficiency, we must determine the total number of iterations performed by the inner loop for a sequence containing n values.
The outer loop is executed n − 1 times since the algorithm makes n − 1 passes over the sequence. The number of iterations for the inner loop is not fixed, but depends on the current iteration of the outer loop.
On the first pass over the sequence, the inner loop executes n − 1 times; on the second pass, n − 2 times; on the third, n − 3 times, and so on until it executes once on the last pass.
# Bubble sort in Python def bubbleSort(array): # loop to access each array element for i in range(len(array)): # loop to compare array elements for j in range(0, len(array) - i - 1): # compare two adjacent elements # change > to < to sort in descending order if array[j] > array[j + 1]: # swapping elements if elements # are not in the intended order temp = array[j] array[j] = array[j+1] array[j+1] = temp data = [-2, 45, 0, 11, -9] bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
Thats it for today guys! Makes sure to comment .
Happy Coding Mates 🙂