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.
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.