Bubble sort program in Python
In this post, you will learn how to write a bubble sort program using the Python programming language.
Bubble sort is a very simple sorting technique in which each element is compared with every other element in the list. This is also called sinking sort. It continuously compares the element with the adjacent item and swaps it if the element is in the wrong order. If the element at the lower index is greater than the element at the higher index, then the two elements are interchanged as the element is placed before the bigger one.
This process will continue working till the largest element moves to the highest index position.
Bubble Sort Example
Suppose we have the following array.
A[] = {10, 43, 23, 56, 16}
These are the bubble sorting techniques.
Pass 1
Compare A[0] and A[1], since A[0] < A[1] then no interchange.
Compare A[1] and A[2], since A[1] > A[2] then interchange.
Compare A[2] and A[3], since A[2] < A[3] then no interchange.
Compare A[3] and A[4], since A[3] > A[4] then interchange.
Pass 2
Compare A[0] and A[1], since A[0] < A[1] then no interchange.
Compare A[1] and A[2], since A[1] < A[2] then no interchange.
Compare A[2] and A[3], since A[2] > A[3] then interchange.
Compare A[3] and A[4], since A[3] < A[4] then no interchange.
Bubble Sorting Algorithm
STEP 1: Repeat Step 2 For 1=0 to N-1
STEP 2: Repeat for J = 0 to N - I
STEP 3: IF A[J] > A[J+1]
SWAP A[J] and A[J+1]
[END of INNER LOOP]
[END of OUTER LOOP]
STEP 4: EXIT
Complexity of Bubble sort
Suppose n is the number of element in an array.
f(n) = (n-1)+(n-2)+(n-3)+.....+3+2+1
f(n) = n(n-1)/2
f(n) = n2/2 + O(n)
= O(n2)
Bubble sort program in Python using a temp variable
In the given example, we create a function bubble_sort that takes an array as an argument. Inside this function, we create a loop with a loop variable i to the length of the array. Next, we create an inner loop with a loop variable j that counts from 0 up to (len(array) - i - 1). Then, we use the if statement to check if the value on the left-hand side is greater than the one on the immediate right side. If the current element is greater than the next element of the array, swap them. If the current element is less than the next element, move to the next element.
# Bubble sort in Python
def bubble_sort(array):
# Outer loop for traverse the entire array
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
if array[j] > array[j + 1]:
# swapping elements
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-12, 34, 55, 33,-22, -13, 56, 35]
bubble_sort(data)
print('Sorted array in ascending order:')
print(data)
Output of the above code:
Sorted array in ascending order:
[-22, -13, -12, 33, 34, 35, 55, 56]
Bubble sort program in Python without using a temp variable
In the given Python program, we create a function bubble_sort that takes a list as an argument. Inside this function, we use nested loops and an if statement to swap the elements without using the temp variable.
def bubble_sort(x_list):
# Outer loop for traverse the entire list
for i in range(0,len(x_list)-1):
for j in range(len(x_list)-1):
if(x_list[j]>x_list[j+1]):
x_list[j],x_list[j+1] = x_list[j+1], x_list[j]
return x_list
# Printing unsorted list
x_list = [77, 3, 9, 22, 52, 84]
print("The unsorted list: ", x_list)
# Calling the function
print("The sorted list: ", bubble_sort(x_list))
Output of the above code:
The unsorted list: [77, 3, 9, 22, 52, 84]
The sorted list: [3, 9, 22, 52, 77, 84]
Related Articles
Convert Python list to numpy arrayConvert string to list Python
Python program to list even and odd numbers of a list
Python loop through list
Sort list in descending order Python
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Python for loop index
Convert List to Dataframe Python
numpy random choice
Dictionary inside list python
Check if list is empty Python
Python raise keyword
Python program to get the largest number from a list
Python program to map two lists into a dictionary