12/7/2023

Bubble Sort
 Bubble Sort is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in the
Bubble Sort wrong order.

 This algorithm is not suitable for large data sets as its

average and worst-case time complexity is quite high.

Dr. Sumit Srivastava

Dept. of CSE, BIT Mesra Ranchi
Email:- sumit@bitmesra.ac.in

Sumit Srivastava @ BIT Mesra Sumit Srivastava @ BIT Mesra

1 2

Bubble Sort Algorithm How does Bubble Sort Work?

 In Bubble Sort algorithm,  Let us understand the working of bubble sort with the help
of the following illustration:
• traverse from left and compare adjacent elements and the
higher one is placed at right side. Input: arr[] = {6, 3, 0, 5}

• In this way, the largest element is moved to the rightmost

end at first.

• This process is then continued to find the second largest

and place it and so on until the data is sorted.

Sumit Srivastava @ BIT Mesra Sumit Srivastava @ BIT Mesra

3 4
 12/7/2023

How does Bubble Sort Work? How does Bubble Sort Work?
 Second Pass: Place the second largest element at correct
 First Pass: The largest element is placed in its correct position.
position, i.e., the end of the array.

Sumit Srivastava @ BIT Mesra Sumit Srivastava @ BIT Mesra

5 6

How does Bubble Sort Work? How does Bubble Sort Work?
 Third Pass: Place the remaining two elements at their correct
positions.  Total no. of passes: n-1

 Total no. of comparisons: n*(n-1)/2

Sumit Srivastava @ BIT Mesra Sumit Srivastava @ BIT Mesra

7 8
 12/7/2023

Bubble Sort Function Bubble Sort Program

void bubble_sort(int arr[], int n) {
#include <stdio.h> int main() {
int i, j; int arr[] = {64, 34, 25, 12, 22, 11, 90};
for (i = 0; i < n - 1; i++) { void bubble_sort(int arr[], int n) { int n = sizeof(arr) / sizeof(arr[0]);
for (j = 0; j < n - i - 1; j++) { int i, j; bubble_sort(arr, n);
if (arr[j] > arr[j + 1]) { for (i = 0; i < n - 1; i++) { printf("Sorted array: ");
int temp = arr[j]; for (j = 0; j < n - i - 1; j++) { for (int i = 0; i < n; i++) {
arr[j] = arr[j + 1]; if (arr[j] > arr[j + 1]) { printf("%d ", arr[i]);
arr[j + 1] = temp; int temp = arr[j]; }
} } } } arr[j] = arr[j + 1]; return 0;
arr[j + 1] = temp; }
}
The function has two loops. The outer loop runs from the first element to the second-last element of the
array. The inner loop runs from the first element to the second-last element of the unsorted part of the array. }
The condition of the inner loop is n - i - 1 because the last i elements of the array are already sorted. }
}
In each iteration of the inner loop, we compare adjacent elements. If the left element is greater than the
right element, we swap them. After the inner loop completes, the largest element is guaranteed to be at the
end of the unsorted part of the array.

Sumit Srivastava @ BIT Sumit Srivastava @ BIT Mesra

Mesra

9 10

Bubble Sort Bubble Sort

Usage:
Characteristics:  Bubble sort is useful for educational purposes and small data sets.

 Bubble sort is a simple sorting algorithm.  It is not suitable for large data sets because of its time complexity.
Advantages:
 It works by repeatedly swapping adjacent elements if they are in
 Bubble sort is easy to understand and implement.
the wrong order.
 It requires minimal additional memory space to perform the
 The algorithm sorts the array in ascending or descending order. sorting.
Disadvantages:
 It has a time complexity of O(n2) in the worst case, where n is the  It is not efficient for large data sets because of its time
size of the array. complexity.
 It has poor performance compared to other sorting algorithms,
such as quicksort and mergesort.
Sumit Srivastava @ BIT Mesra Sumit Srivastava @ BIT Mesra

11 12