Bubble Sort algorithm, which is one of the simplest sorting algorithms. Sorting means arranging a list of items in a particular order, such as ascending or descending order. Bubble Sort is a method to sort a list of numbers or elements in an increasing order.
Here’s how the algorithm works:
1. You start from the first element of the list.
2. Compare it with the next element.
3. If the first element is greater than the second, swap them. If not, leave them as they are.
4. Move to the next pair of elements and repeat this process until the entire list is sorted.
The reason it’s called “Bubble Sort” is because after several passes through the list, larger elements bubble up to the end, and smaller elements "sink" to the beginning.
Example:
Let’s say we have the following list of numbers that we want to sort in ascending order : [5, 3, 8, 4, 2]
• In the first pass, 5 will compare with 3 and swap, then it compares with 8 and no swap happens, then 8 with 4 (swap), and finally 8 with 2 (swap). After the first pass, the largest number (8) "bubbles" to the end.
• You repeat the process for the remaining unsorted numbers, and eventually, the list will be sorted.
Time Complexity:
The time complexity of Bubble Sort is O(n²), where n is the number of elements in the list. This is because for each element, you might have to compare it with every other element, which results in quadratic time complexity.
Notes:
Bubble Sort Algorithm
Introduction: Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing adjacent items, and swapping them if they are in the wrong order. This process is repeated until the list is sorted.
Steps of the Bubble Sort Algorithm:
1. Start at the first element of the list.
2. Compare the current element with the next element.
• If the current element is greater than the next element, swap them.
• If the current element is less than or equal to the next element, move to the next pair.
3. Continue this process for all elements in the list. After the first pass, the largest element will have "bubbled" up to the end of the list.
4. Repeat the process for the remaining unsorted elements. With each pass, the number of comparisons decreases because the largest elements are gradually moved to their correct position at the end of the list.
5. The algorithm terminates when a complete pass is made without any swaps, indicating that the list is sorted.
Example:
Let’s consider the array [5, 3, 8, 4, 2] that we want to sort in ascending order using Bubble Sort.
First pass:
• Compare 5 and 3: Swap them → [3, 5, 8, 4, 2]
• Compare 5 and 8: No swap → [3, 5, 8, 4, 2]
• Compare 8 and 4: Swap them → [3, 5, 4, 8, 2]
• Compare 8 and 2: Swap them → [3, 5, 4, 2, 8]
Now, 8 is at its correct position.
Second pass:
• Compare 3 and 5: No swap → [3, 5, 4, 2, 8]
• Compare 5 and 4: Swap them → [3, 4, 5, 2, 8]
• Compare 5 and 2: Swap them → [3, 4, 2, 5, 8]
Now, 5 is at its correct position.
Third pass:
• Compare 3 and 4: No swap → [3, 4, 2, 5, 8]
• Compare 4 and 2: Swap them → [3, 2, 4, 5, 8]
Now, 4 is at its correct position.
Fourth pass:
• Compare 3 and 2: Swap them → [2, 3, 4, 5, 8]
Now, the list is sorted.
Pseudocode:
BubbleSort(arr):
n = length of arr
for i = 0 to n-1:
for j = 0 to n-i-2:
if arr[j] > arr[j+1]:
swap(arr[j], arr[j+1])
Time Complexity:
• Worst case: O(n²) — This occurs when the list is sorted in reverse order and the algorithm needs to perform the maximum number of comparisons and swaps.
• Best case: O(n) — This happens when the list is already sorted, and only one pass is needed to confirm it is sorted.
• Average case: O(n²) — In most cases, Bubble Sort performs at its worst case time complexity.