Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. It is named because the smaller elements “bubble” to the top of the list as the algorithm progresses.
Here’s a step-by-step explanation of the Bubble Sort algorithm with an example:
1. Start at the beginning of the list.
2. Compare the first two elements. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements and repeat step 2.
4. Continue this process until you reach the end of the list. After the first pass, the largest element will have “bubbled” to the end of the list.
5. Repeat the above steps for the remaining elements, excluding the last element (which is already in its correct position).
6. Continue these passes until no more swaps are needed. This indicates that the list is sorted.
1. Start at the beginning of the list.
2. Compare the first two elements. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements and repeat step 2.
4. Continue this process until you reach the end of the list. After the first pass, the largest element will have “bubbled” to the end of the list.
5. Repeat the above steps for the remaining elements, excluding the last element (which is already in its correct position).
6. Continue these passes until no more swaps are needed. This indicates that the list is sorted.
begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort
Example 1:
Let’s say we have an unsorted list of numbers:
[5, 3, 1, 4, 2]
First Pass: Compare 5 and 3. Swap them because 5 > 3.
The list becomes [3, 5, 1, 4, 2]
Compare 5 and 1. Swap them because 5 > 1.
The list becomes [3, 1, 5, 4, 2]
Compare 5 and 4. Swap them because 5 > 4. The list becomes [3, 1, 4, 5, 2]
Compare 5 and 2. Swap them because 5 > 2. The list becomes [3, 1, 4, 2, 5]
The largest element (5) is now at the end of the list.
Second Pass:
Compare 3 and 1. Swap them because 3 > 1. The list becomes [1, 3, 4, 2, 5]
Compare 3 and 4. Do not swap; the list remains the same.
Compare 4 and 2. Swap them because 4 > 2. The list becomes [1, 3, 2, 4, 5]
The second largest element (4) is now in its correct position.
Third Pass:
Compare 1 and 3. Do not swap; the list remains the same.
Compare 3 and 2. Swap them because 3 > 2. The list becomes [1, 2, 3, 4, 5].
The third largest element (3) is now in its correct position.
Fourth Pass:
Compare 1 and 2. Swap them because 2 > 1.
The list becomes [1, 2, 3, 4, 5].
The fourth largest element (2) is now in its correct position.
Fifth Pass:
No swaps are needed in this pass. The list is already sorted.
Let’s say we have an unsorted list of numbers:
[5, 3, 1, 4, 2]
First Pass:
The list becomes [3, 5, 1, 4, 2]
The list becomes [3, 1, 5, 4, 2]
The largest element (5) is now at the end of the list.
Second Pass:
The second largest element (4) is now in its correct position.
Third Pass:
The third largest element (3) is now in its correct position.
Fourth Pass:
The list becomes [1, 2, 3, 4, 5].
The fourth largest element (2) is now in its correct position.
Fifth Pass:
No swaps are needed in this pass. The list is already sorted.
Various Sorting Algorithm
- Bubble sort
- Modified Bubble Sort
- Selection sort
- Insertion sort
- Quick sort
- Merge sort
- Heap sort
Bubble Sort
n=7
0 1 2 3 4 5 6
25 37 81 19 44 50 62
25 37 19 44 50 62 81
25 19 37 44 50 62
19 25 37 44 50
19 25 37 44
19 25 37 44 50 62 81(0,1)(1,2)(4,3)(3,4)(4,5)(5,6)
(0,1)(1,2)(4,3)(3,4)(4,5)
(0,1)(1,2)(2,3)(4,5)
(0,1)(1,2)(2,3)
(0,1)(1,2)
(0,1)
Modified Bubble Sort
flag=0
if (a[i]>a[i+1])
{
//swap
flag=1;
}
