Algorithm

The Bubble Sort algorithm works by repeatedly stepping through the list of elements to be sorted, comparing each pair of adjacent items, and swapping 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. Here's a step-by-step explanation of the algorithm:

1. Start from the first element (index 0) and compare it with the next element (index 1).

• If the first element is greater than the second element, swap them.
• If the first element is smaller or equal to the second element, do nothing.
2. Move to the next pair of elements (index 1 and index 2) and repeat the comparison and swapping process.

• Continue this process until you reach the end of the list.
3. After the first pass, the largest element will have "bubbled up" to the end of the list.

• The last element is now in its correct sorted position.
4. Repeat the process for the remaining elements (excluding the last one).

• On each pass, the next largest element will be placed in its correct position.
5. Continue these passes until no more swaps are needed.

• If, after a pass, no swaps were made, it means the list is fully sorted, and the algorithm can stop.

Here's a simple example of the Bubble Sort algorithm in action:

Initial list: [5, 3, 8, 4, 2]

1. Pass 1:

• Compare 5 and 3, swap them → [3, 5, 8, 4, 2]
• Compare 5 and 8, do nothing
• Compare 8 and 4, swap them → [3, 5, 4, 8, 2]
• Compare 8 and 2, swap them → [3, 5, 4, 2, 8]
2. Pass 2:

• Compare 3 and 5, do nothing
• Compare 5 and 4, swap them → [3, 4, 5, 2, 8]
• Compare 5 and 2, swap them → [3, 4, 2, 5, 8]
3. Pass 3:

• Compare 3 and 4, do nothing
• Compare 4 and 2, swap them → [3, 2, 4, 5, 8]
4. Pass 4:

• Compare 3 and 2, swap them → [2, 3, 4, 5, 8]

After Pass 4, no more swaps are needed, and the list [2, 3, 4, 5, 8] is sorted.

Keep in mind that Bubble Sort is not the most efficient sorting algorithm for large datasets, and it has a time complexity of O(n^2). Other more efficient algorithms like QuickSort or MergeSort are often preferred in practice.

Code Examples

#1 Optimized Bubble Sort in Python

```Code - Python Programming```

``````def optimized_bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Set a flag to optimize by checking if any swapping occurs in the inner loop
swapped = False

# Last i elements are already sorted, so no need to check them
for j in range(0, n-i-1):
# Swap if the element found is greater than the next element
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True

# If no swapping occurred in the inner loop, the array is already sorted
if not swapped:
break

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
optimized_bubble_sort(my_list)

print("Sorted array:", my_list)
``````
Copy The Code &

#2 Optimized Bubble Sort in Java

```Code - Java Programming```

``````public class BubbleSort {
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};

System.out.println("Original Array:");
printArray(array);

// Apply the optimized bubble sort
bubbleSort(array);

System.out.println("\nSorted Array:");
printArray(array);
}

static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;

for (int i = 0; i  <  n - 1; i++) {
swapped = false;

for (int j = 0; j  <  n - i - 1; j++) {
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 two elements were swapped in the inner loop, the array is already sorted
if (!swapped) {
break;
}
}
}

static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}
``````
Copy The Code &

#3 Optimized Bubble Sort in C

```Code - C Programming```

``````#include <stdio.h>

void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void optimizedBubbleSort(int arr[], int n) {
int i, j;
int swapped;

for (i = 0; i  <  n-1; i++) {
swapped = 0; // Flag to check if any swapping occurred in this pass

for (j = 0; j  <  n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
swapped = 1; // Set the flag to indicate swapping occurred
}
}

// If no two elements were swapped by inner loop, the array is sorted
if (swapped == 0) {
break;
}
}
}

void printArray(int arr[], int size) {
int i;
for (i = 0; i  <  size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);

printf("Original array: \n");
printArray(arr, n);

optimizedBubbleSort(arr, n);

printf("Sorted array: \n");
printArray(arr, n);

return 0;
}
``````
Copy The Code &

#4 Optimized Bubble Sort in C++

```Code - C++ Programming```

``start coding...``
Copy The Code &