Working of the Bubble Sort
Lesson 2 of 11 in Coddy's Bubble Sort course.
Bubble sort is a simple sorting algorithm that iterates through the elements of a list, compares adjacent elements and swaps them if they are in the wrong order.
The pass through the list is repeated until the list is sorted.
An example-
We have to sort a list with 4 elements: [3,4,2,1]
First Pass:
Compares first two elements
[3,4,2,1] -> [3,4,2,1] (No change, as they are already sorted)
Compares next two elements
[3,4,2,1] -> [3,2,4,1] (Swaps the elements to make them in sorted order)
Compares next two elements
[3,2,4,1] -> [3,2,1,4] (Swaps the elements to make them in sorted order)
First Pass completed, what did you observe?
Is the list sorted -No, right?
So, we will have to repeat the process again.
Please observe that with the first pass, we have the maximum element at the end of the list. And this is what we will try to achieve through the subsequent passes.
Second Pass:
Compares first two elements
[3,2,1,4] -> [2,3,1,4] (Swaps the elements to make them in sorted order)
Compares next two elements
[2,3,1,4] -> [2,1,3,4] (Swaps the elements to make them in sorted order)
Compares next two elements
[2,1,3,4] -> [2,1,3,4] (No change, as they are already sorted)
After the second pass, notice that the last two elements are sorted.
Third Pass:
Compares first two elements
[2,1,3,4] -> [1,2,3,4] (Swaps the elements to make them in sorted order)
Notice that after this pass, we have got the required list.
So this is how BUBBLE SORT WORKS!
Now, let's understand algorithm for Bubble Sort in next lesson.
Happy learning!
Challenge
EasyCreate a function named swap_list that receives an array, size of the array and two indices. Function swaps the two indices elements and returns the new list.
For eg.
list=[1,2,3,4] (0-biased)
n=4 (Number of elements in the list)
i=1 j=3 (indices to swap)
[1,2,3,4] -> [1,4,3,2]
Return: list= [1,4,3,2]
Try it yourself
#include <stdio.h>
#include <stdlib.h>
int* swap_list(int* arr, int arr_size, int n, int i, int j, int* returnSize) {
// Write code here
*returnSize = n;
return arr;
}
All lessons in Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm