Bubble Sort Algorithm
Bubble Sort : Overview
- Bubble sort is considered the simplest sorting algorithm.
- Bubble Sort is used to sort a given set of n elements provided in form of an array with n number of elements.
- Bubble Sort compares all the element one by one and sort them based on their values.
- It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.
- Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required.
Implementing Bubble Sort Algorithm
- Step 1: Starting with the first element(index = 0), compare the current element with the next element of the array.
- Step 2: If the current element is greater than the next element of the array, swap them.
- Step 3: If the current element is less than the next element, move to the next element.
- Step 4: Repeat Step 1.
Complexity Analysis of Bubble Sort Algorithm
In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,
(n-1) + (n-2) + (n-3) + (n-4) + (n-5) + ….. + 3 + 2 + 1
Sum = n(n-1)/2
i.e O(n2)
- Time complexity of Bubble Sort is O(n2).
- The main advantage of Bubble Sort is the simplicity of the algorithm.
- The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable.
- Also, the best case time complexity will be O(n), it is when the list is already sorted.
Following are the Time and Space complexity for the Bubble Sort algorithm.
- Worst Case Time Complexity [ Big-O ]: O(n2)
- Best Case Time Complexity [Big-omega]: O(n)
- Average Time Complexity [Big-theta]: O(n2)
- Space Complexity: O(1)
