How to Implement Bubble Sort Algorithm in Python and C?

Bubble sort is a simple sorting algorithm that repeatedly iterates through a list, compares adjacent elements, and swaps them if they are in the wrong order. It is called bubble sort because the larger values “bubble” to the top of the list are like a bubble rising to the surface of a glass of water. This process is repeated until the list is sorted.

Introduction

Sorting Techniques are used to sort a sequence of numbers stored in an array or any other data type. The main objective of this is to sort a sequence of integers in the least amount of time which can be referred to as time complexity and the program should occupy less space which can be referred to as Space Complexity.

Definition

Bubble Sort can be defined as continuously sorting the adjacent elements of an array until the desired result, which is a sorted array, can be obtained.

Algorithm

1. Start.
2. Declare an array.
3. Take input elements and store them in the array.
4. If element i is greater than the i+1 element, swap them.
5. Else, Continue.
6. Repeat the above step till a sorted array is obtained.
7. Print the final array.
8. Stop.

Explanation

Consider the elements 9,5,2,1,4,6,4. Since adjacent elements 9 and 5 are not following the algorithm, we swap them, now the array becomes 5,9,2,1,4,6,4.

We follow the same steps till the end of one iteration, Where the array becomes 5,2,1,9,4,6,4,9.

By repeating the above steps till w iterations, we get the final sorted array 1,2,4,4,5,6,9.

Applications of bubble sorting

• Bubble sorting comes in handy in Competitive Programming due to its Time Complexity.
• It is faster than other conventional methods.
• It is simpler to execute since we must compare the adjacent elements.
• Compared to other algorithms, It works best for optimal conditions.

Implementation in Python

def bs(karr, n):
    for w in range(1, n):
        for e in range(n-1):
            if karr[e] > karr[e+1]:
                karr[e], karr[e+1] = karr[e+1], karr[e]
    return karr

#defining the Main Method
if __name__ == '__main__':
    karr = [9, 5, 2, 1, 4, 6, 4]
    n = len(karr)
    print("Before using bubble sorting")
    print(karr)
    karr = bs(karr, n)
    print("After bubble sorting")
    print(karr)
Code language: Python (python)

Click Here to run the code by yourself.

OUTPUT

Before using bubble sorting
[9, 5, 2, 1, 4, 6, 4]
After bubble sorting
[1, 2, 4, 4, 5, 6, 9]Code language: Python (python)

Implementation in C

#include <stdio.h>
#include <stdbool.h>

void bs(int karr[], int q) {
    for(int w = 1; w < q; w++) {
        bool checker = false;
        for(int e = 0; e < q - w; e++) {
            if(karr[e] > karr[e + 1]) {
                int temp = karr[e];
                karr[e] = karr[e + 1];
                karr[e + 1] = temp;
                checker = true;
            }
        }
        if(checker == false) {
            break;
        }
    }
}

int main() {
    int karr[] = {9, 5, 2, 1, 4, 6, 4};
    int q = sizeof(karr) / sizeof(karr[0]);
    bs(karr, q);
    for(int w = 0; w < q; w++) {
        printf("%d ", karr[w]);
    }
    return 0;
}
Code language: C/AL (cal)

Click Here to run the code by yourself.

OUTPUT

1 2 4 4 5 6 9Code language: C/AL (cal)

Optimized Bubble Sort in Python

def bs(ele):
  for w in range(len(ele)):
    checker = False
    for e in range(0, len(ele) - w - 1):
        if ele[e] > ele[e + 1]:
            temper= ele[e]
            ele[e] = ele[e+1]
            ele[e+1] = temper
            checker = True

    if not checker:
      break

ele = [9, 5, 2, 1, 4, 6, 4]

bs(ele)

print(ele)
Code language: Python (python)

Click Here to run the code by yourself.

OUTPUT

[1, 2, 4, 4, 5, 6, 9]Code language: Python (python)

Optimized Bubble Sort in C

#include<stdio.h>

void bs(int ele[], int size) {
  for (int w = 0; w < size - 1; w++) {  
    int checker = 0;
    for (int g = 0;g < size - w - 1; ++g) {
      if (ele[g] > ele[g + 1]) {
        int temper = ele[g];
        ele[g] = ele[g + 1];
        ele[g + 1] = temper;
        checker = 1;
      }
    }
    if (checker != 0) {
      break;
    }
  }
}

void outputer(int ele[], int size) {
  for (int w = 0; w < size; w++) {
    printf("%d  ", ele[w]);
  }
}

int main() {
  int ele[] = {9, 5, 2, 1, 4, 6, 4};
  int size = sizeof(ele) / sizeof(ele[0]);
  bs(ele, size);
  outputer(ele, size);
}
Code language: C/AL (cal)

Click Here to run the code by yourself.

OUTPUT

1 2 4 4 5 6 9Code language: C/AL (cal)

Time Complexity of Bubble Sort

Time Complexity can be calculated as the amount of time the program takes to run certain cases, which can be classified as Best, Average, and Worst Cases.

Consider the size of the array as w.

Best Case Complexity

The Best Case Complexity of bubble sort is O(w).

Average Case Complexity 

The Average Case Complexity of bubble sort is O(w^2).

Worst Case Complexity 

The Worst Case Complexity of bubble sort is O(w^2).

Space Complexity of Bubble Sort

Space Complexity is the total amount of space used by a particular problem.

The Space Complexity of Bubble Sort is O(1) or constant.

Stability

The bubble Sort Algorithm is said to be a Stable Algorithm since it preserves the order by only swaps the if the next element is less than the present element.

Conclusion

In this article, We have briefly discussed the bubble sort algorithm and its implementation in Python and C language. We have also discussed the Time and Space Complexity and Stability of the sorting algorithm.

Frequently Asked Questions to Resolve (FAQs)

How is a bubble sort algorithm implemented in C?

To implement the bubble sort algorithm in C, you would use a nested for loop, with the outer loop iterating through the array and the inner loop comparing adjacent elements and swapping them if they are out of order. You would also need to include a variable to keep track of whether any swaps were made during each pass, and use this variable to determine when the sorting is complete.

How is a bubble sort algorithm implemented?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

How can you implement a bubble sort in Python?

To implement the bubble sort algorithm in Python, you would use a nested for loop, with the outer loop iterating through the array and the inner loop comparing adjacent elements and swapping them if they are out of order. You would also need to include a variable to keep track of whether any swaps were made during each pass, and use this variable to determine when the sorting is complete.

What is bubble sort and can you explain it with an example? 

The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list as the sort is executed.

Here’s an example of how bubble sort would work for a list of integers [2, 1, 3]. The algorithm compares the first two elements (2 and 1) and sees that they are out of order, so it swaps them. The list is now [1, 2, 3]. The algorithm performs one more pass through the list but doesn’t find any more swaps to make, so it knows that the list is now sorted.