Back to list

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n^2) where n is the number of items.

Ready...Items: 8
49
87
62
10
20
21
26
87
Speed
Comp
0
Swaps
0
Array Controls

Time Complexity

Best
O(n)
Avg
O(n²)
Worst
O(n²)

Space Complexity

Auxiliary SpaceO(1)

Algorithm Details

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n^2) where n is the number of items.

How it works

  1. Traverse from left and compare adjacent elements and the higher one is placed at right side.
  2. In this way, the largest element is moved to the rightmost end at first.
  3. This process is then continued to find the second largest and place it and so on until the data is sorted.

Complexity

  • Time Complexity: O(n²)
  • Space Complexity: O(1)

Implementation

1def bubble_sort(arr):
2  n = len(arr)
3  for i in range(n):
4      swapped = False
5      for j in range(0, n-i-1):
6          if arr[j] > arr[j+1]:
7              arr[j], arr[j+1] = arr[j+1], arr[j]
8              swapped = True
9      if (swapped == False):
10          break
11          
12arr = [64, 34, 25, 12, 22, 11, 90]
13bubble_sort(arr)
14print("Sorted array is:", arr)