# Bubble Sort Algorithm – APalgorithm

5 August 2023

In this tutorial we are going to discuss the bubble sort algorithm. The working procedure of the bubble sort algorithm and how to solve our problems using this. In this brief introduction, we’ll explore how Bubble Sort works, its basic steps, and why it continues to be a fundamental concept in the world of programming.

In simple words, Bubble Sort is a way of arranging a list of items in order from smallest to largest. It works by comparing neighboring items and swapping them if they are in the wrong order. The process is repeated until the entire list is sorted. It’s called “Bubble Sort” because smaller items “bubble” to the top, while larger items “sink” to the bottom. Though easy to understand, Bubble Sort is not very efficient for large lists, but it’s a good starting point for learning about sorting algorithms.

## How does Bubble Sort Works?

Let us understand the working procedure of bubble sort algorithm with the help of the following illustration:

We have a given an array, as you can see in this image. Now, the concept of bubble sort says it sorts arrays in the form of increasing order. If we see the output of the given array, it would be like [2,4,7,9,11,17]. So here are many passes followed in this process and then we see this sorted array.

To sort the array [7, 11, 9, 2, 17, 4], we can use the Bubble Sort algorithm as an example. Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire array is sorted. Here are the steps and passes to sort the given array.

#### First Pass

Compare 7 and 11 – First, we compare 7 and 11. There are 11, which is greater than 7. So there are no swaps in the value and the result would be like [7, 11, 9, 2, 17, 4].

Compare 11 and 9 – In 11 and 9. 11  is greater than 9. So there are swaps in the value and the result would be like  [7, 9, 11, 2, 17, 4].

Compare 11 and 2 – Similarly, in 11 and 2. 11  is greater than 2. So there are swaps in the value and the result would be like  [7, 9, 2, 11, 17, 4].

Compare 17 and 4 – In 17 and 4. 17 is greater than 4. So, Swap in value and result is [7, 9, 2, 11, 4, 17].

#### Second Pass

Compare 7 and 9 – No swap [7, 9, 2, 11, 4, 17]

Compare 9 and 2 – Swap [7, 2, 9, 11, 4, 17]

Compare 9 and 11 – No Swap [7, 2, 9, 11, 4, 17]

Compare 11 and 4 – Swap [7, 2, 9, 4, 11, 17]

#### Third Pass

Compare 7 and 2 – Swap [2, 7, 9, 4, 11, 17].

Compare 7 and 9 – No swap [2, 7, 9, 4, 11, 17]

Compare 9 and 4 – Swap [2, 7, 4, 9, 11, 17]

#### Fourth Pass

Compare 2 and 7 – No Swap [2, 7, 4, 9, 11, 17]

Compare 7 and 4 – Swap [2, 4, 7, 9, 11, 17]

#### Fifth Pass

In this pass we have our sorted array – [2, 4, 7, 9, 11, 17].

Yay! Congrats You sorted your array in ascending order using the Bubble Sort algorithm.

Note that Bubble Sort is not the most efficient sorting algorithm for large datasets, but it’s a straightforward example to demonstrate the sorting process. Other sorting algorithms like Merge Sort or Quick Sort are more efficient for larger datasets.

## Python Program using Bubble Sort Algorithm

Here’s a Python program that implements the Bubble Sort algorithm to sort an array:

```def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Set this flag to True at the beginning of each pass
# If no swaps occur during the pass, the array is already sorted, and we can break out early
swapped = False

# Last i elements are already in place, so we don't need to check them
for j in range(0, n-i-1):
# Compare adjacent elements and swap them if they are in the wrong order
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True

# If no swaps occurred in this pass, the array is sorted, and we can break the loop
if not swapped:
break

# Example usage:
if __name__ == "__main__":
arr = [7, 11, 9, 2, 17, 4]
print("Original Array:", arr)

bubble_sort(arr)
print("Sorted Array:", arr)```

Output

```Original Array: [7, 11, 9, 2, 17, 4]
Sorted Array: [2, 4, 7, 9, 11, 17]```

## JavaScript Program Example

Here’s an example of an JavaScript Program which using the bubble sort algorithm to sort an array:

```function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Set this flag to true at the beginning of each pass
// If no swaps occur during the pass, the array is already sorted, and we can break out early
let swapped = false;

// Last i elements are already in place, so we don't need to check them
for (let j = 0; j < n - i - 1; j++) {
// Compare adjacent elements and swap them if they are in the wrong order
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}

// If no swaps occurred in this pass, the array is sorted, and we can break the loop
if (!swapped) {
break;
}
}
}

// Example usage:
const arr = [7, 11, 9, 2, 17, 4];
console.log("Original Array:", arr);

bubbleSort(arr);
console.log("Sorted Array:", arr);```

Output

`Sorted Array: [2, 4, 7, 9, 11, 17]`

The bubbleSort() function implements the Bubble Sort algorithm to sort the given array. The outer loop iterates n-1 times, where n is the number of elements in the array. The inner loop iterates through the unsorted part of the array and swaps adjacent elements if they are in the wrong order. The swapped variable helps optimize the algorithm by breaking the loop early if no swaps occur in a pass, indicating that the array is already sorted.

## C Program Example

Here’s a C program that implements the Bubble Sort algorithm to sort an array of integers in ascending order:

```#include <stdio.h>

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Set this flag to true at the beginning of each pass
// If no swaps occur during the pass, the array is already sorted, and we can break out early
int swapped = 0;

// Last i elements are already in place, so we don't need to check them
for (int j = 0; j < n - i - 1; j++) {
// Compare adjacent elements and swap them if they are in the wrong order
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}

// If no swaps occurred in this pass, the array is sorted, and we can break the loop
if (!swapped) {
break;
}
}
}

int main() {
int arr[] = {7, 11, 9, 2, 17, 4};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

bubbleSort(arr, n);

printf("Sorted Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}```

Output

`Sorted Array: 2 4 7 9 11 17`

The `bubbleSort()` function implements the Bubble Sort algorithm to sort the given array. The outer loop iterates `n - 1` times, where `n` is the number of elements in the array. The inner loop iterates through the unsorted part of the array and swaps adjacent elements if they are in the wrong order. The `swapped` variable helps optimize the algorithm by breaking the loop early if no swaps occur in a pass, indicating that the array is already sorted.

## Java Program Example

Here is an example of java program using the bubble sort algorithm :

```public class BubbleSort {

public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Set this flag to true at the beginning of each pass
// If no swaps occur during the pass, the array is already sorted, and we can break out early
boolean swapped = false;

// Last i elements are already in place, so we don't need to check them
for (int j = 0; j < n - i - 1; j++) {
// Compare adjacent elements and swap them if they are in the wrong order
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

// If no swaps occurred in this pass, the array is sorted, and we can break the loop
if (!swapped) {
break;
}
}
}

public static void main(String[] args) {
int[] arr = {7, 11, 9, 2, 17, 4};

System.out.print("Original Array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();

bubbleSort(arr);

System.out.print("Sorted Array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}```

Output

```Original Array: 7 11 9 2 17 4
Sorted Array: 2 4 7 9 11 17```