Explain the logic of bubble sort
Answers
Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you don't need to swap the element. Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. This completes the first step of bubble sort.
Consider following example to clear the concept :
Suppose the array elements are : 5,6,1,3 and we have to arrange in ascending order.
Step 1: The first and the second array element are compared. Here as first element is smaller than second, elements will not be swapped. Next , the second and third element will be checked.Here second is larger than third and hence they will be swapped. This continues till all array elements are checked.
(5,6,1,3) -> (5,6,1,3)
(5,6,1,3) - > (5,1,6,3)
(5,1,6,3) -> (5,1,3,6)
The step 1 is completed and the largest element of the array gets placed at its position.
Step 2: Now the elements are (5,1,3,6). We again start comparing the first and second element and if the first number is greater than second we swap the elements. You need to take care here that you don’t consider the last element(i.e 6 in this case) because it is now already placed correctly at its location.
(5,1,3,6) -> (1,5,3,6)
(1,5,3,6) -> (1,3,5,6)
Here 5 is now properly placed at its location before 6. Here we don’t compare 5 and 6.
Step 3: Now we again repeat the same procedure as above, but this time we will not compare the last two elements.
(1,3,5,6) - > (1,3,5,6)
As 1 is smaller than 3 elements are not swapped and also we don’t have to check 5 and 6 . Thus we have checked all the array elements and have got the resultant array in ascending order using bubble sort.
RESULTANT ARRAY: (1,3,5,6)
You can refer following C code :
#include<stdio.h>
void main()
{
int array[50],i,n,step,temp;
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("%d. Enter element: ",i+1);
scanf("%d",&array[i]);
}
for(step=0;step<n-1;step++)
{
for(i=0;i<n-step-1;i++)
{
if(array[i]>array[i+1]) /* To sort in descending order, change > to < in this line. */
{
temp=array[i];
array[i]=array[i+1];
array[i+1]=temp;
}
}
}
printf("In ascending order: ");
for(i=0;i<n;i++)
printf("%d ",array[i]);
}
OUTPUT:
Enter the number of elements to be sorted: 6
1. Enter element: 14
2. Enter element: 25
3. Enter element: 8
4. Enter element: 11
5. Enter element: 3
6. Enter element: 1
In ascending order: 1 3 8 11 14 25