Bubble Sort algorithm in C and bubble sort program in c

What is Sorting(Bubble Sort in C) - Definition

Often in the real world, we are alleged to arrange data during a particular order. as an example, during our college days, we are told to face within the queue supported our heights. Another example is that the attendance register at school/college which contains our names arranged in alphabetical order.

Bubble Sort algorithm in C and bubble sort program in c

These data arrangements give easier access to data for future use forex. finding "Drake" in an attendance register of 100 students. The arrangement of knowledge during a particular order is named as sorting of the info by that order. 2 of the foremost commonly used orders are:

 Ascending order for Bubble Sort in C algorithm:

 while sorting the info in ascending order, we attempt to arrange the info during a way such each element is in how “smaller than” its successor. This “smaller one” relation is an ordered relation over the set from which the info is taken. As an easy example, the numbers 1, 2, 3, 4, 5 are sorted in ascending order. Here, the “smaller than” relation looks like < operator. and seen as, 1 < 2 < 3 < 4 < 5

Check also :- Data structure in Hindi 

Descending order Bubble Sort algorithm in C:

 descending order is the exact opposite of ascending order. Given a knowledge that's sorted in ascending order, reverse it and you'll get the info in descending order.

Due to the similar nature of the two orders, we frequently drop the particular order and that we say - we would like to sort the info. This generally means we would like the info to be sorted in ascending order. Before we get into the small print of the algorithm, allow us to understand the matter statement.

Problem statement for bubble sort in c

We are given an array (or a list) of knowledge. We also are given how to “order” the weather present within the data. Now, we are asked to arrange the info as per the given order. As an example, we are given an array of integers: [5, 1, 4, 2, 3]. We are given the “order” as “smaller than”. 

So, we are asked to rearrange the weather of this array in such how that every element is smaller than its successor. Basically, we'd like to seek out how to sort this array in order that the ultimate array obtained is [1, 2, 3, 4, 5]. 

There are several techniques/algorithms to realize this ordered output array. One such well-known technique that we'll discuss during this blog is named Bubble Sort.

Bubble Sort Algorithm in C - Introduction

Bubble Sort in C may be an algorithm where we repeatedly iterate through the array and swap adjacent elements that are unordered. We repeat these steps until the array is sorted.

As an example, for the array mentioned above - [5, 1, 4, 2, 3] we will see that 5 shouldn't get on the left of 1 then, we swap them to get: [1, 5, 4, 2, 3]. Next, we see that 5 should again not get on the left of 4. We swap 5 and 4 to urge [1, 4, 5, 2, 3]. We repeat this for five and a couple of and subsequently for five and three to urge [1, 4, 2, 3, 5].

As are often seen - after one “pass” over the array, the most important element (5 during this case) has reached its correct position - extreme right. allow us to attempt to repeat this process.

(1, 4) is correct. However, (4, 2) is an incorrect order. Therefore, we swap 4 and a couple of to urge [1, 2, 4, 3, 5]. Now again, (4, 3) is wrong so we do another swap and obtain [1, 2, 3, 4, 5].

As are often seen, the array is sorted!

this is the way how's bubble sort in C programming works.

#include  <stdio.h>
  
void swap(int *tp, int *qp) 
{ 
    int temp = *tp; 
    *tp = *qp; 
    *qp = temp; 
} 
  //function for bubble sort algorithm
void bubbleSort(int arr[], int n) 
{ 
   int k, l; 
   for (k = 0; k < n-1; k++)       
     
       for (l = 0; l < n-k-1; l++)  
           if (arr[l] > arr[l+1]) 
              swap(&arr[j], &arr[l+1]); 
} 
  

void printArray(int arr[], int size) 
{ 
    int k; 
    for (k=0; k < size; k++) 
        printf("%d ", arr[k]); 
    printf("\n"); 
} 
  
int main() 
{ 
    int arr[] = {1, 2, 4, 3, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
} 

Bubble Sort in C - Explanation

In the first “pass” through the array, the most important element will always get swapped until it's placed to the acute right. this is often because this largest element will always break the specified order. So, at the top of the primary pass, the most important element will always reach its correct position.

Now that the most important element has reached its correct position (for instance, 5 reached the last position), we will simply ignore it and consider the remainder of the array ([1, 4, 2, 3] within the above case).

 Here, the most important element within the remainder of the array (which is 4) is going to be nothing but the second largest element within the array. By the above recursive argument, this second largest array will then reach the last position within the remaining array ([1, 2, 3, 4]). this is often nothing but a recursive argument on the remaining array.

This continues until for n iterations where n = number of elements within the array. Finally, the array gets sorted.

Bubble sorting program in C

We loop n times - once for every element of the array. once I = 0, with the j loop, the most important element of the array reaches its correct position. once I = 1, with the j loop, the second largest element of the array reaches its correct position. So on then forth.

Conclusion for Bubble sort in c

Bubble sort in c may be a fairly simple algorithm. It forms a stimulating example of how simple computations are often wont to perform more complex tasks. However, there's one issue with the algorithm - it's relatively slower compared to other sorting algorithms. to know that, allow us to take a glance at the loops involved - there are 2 loops:

 First, the outer loop of variable i that goes from i = 0 to i = n - 1.
 for every iteration of the outer i loop, the inner loop of variable j goes from j = 0 to j = n - i - 2.

We can consolidate the amount of iterations to ascertain that:

 once I = 0, the inner j loop goes from j = 0 to j = n - 2
 once I = 1, the inner j loop goes from j = 0 to j = n - 3
 once I = 2, the inner j loop goes from j = 0 to j = n - 4
 once I = n - 2, the inner j loop goes from j = 0 to j = 0

We can sum this up to ascertain that the entire iterations are (n - 2) + (n - 3) + (n - 4) … + 1 + 0 = (n - 2) * (n - 3) / 2 = (n2 - 5n + 6) / 2 = n2/2 - 2.5n + 3As are often seen, this term is proportional to n2 (the largest power of n is n2).

 Mathematically, this is often stated as - bubble sort algorithm is of O(n2) complexity. This isn’t the simplest because when n is large (say n = 106), n2 is large (n2 = 1012). Therefore, it'll take tons of iterations for the algorithm to finish. 

this is often undesirable. There are some better algorithms like merge sort in C, etc that take O(nlog2n) iterations. logn is far smaller than n. As an example, when n = 230 (which is approximately 109), log2n is simply 30). 

Nevertheless, bubble sort is a stimulating algorithm and maybe a good way for beginners to know how sorting works.