Bubble Sort in Data Structures

• Python
• Java
• C++

 # Bubble sort in Python
 def bubbleSort(array):
   # loop to access each array element
   for i in range(len(array)):
     # loop to compare array elements
     for j in range(0, len(array) - i - 1):
       # compare two adjacent elements
       # change > to < to sort in descending order
       if array[j] > array[j + 1]:
         # swapping elements if elements
         # are not in the intended order
         temp = array[j]
         array[j] = array[j+1]
         array[j+1] = temp
 data = [ -122, 46, 0, 28, -79]
 bubbleSort(data)
 print('Sorted Array in Ascending Order:')
 print(data)

 // Bubble sort in Java
 import java.util.Arrays;
 class Main {
   // perform the bubble sort
   static void bubbleSort(int array[]) {
     int size = array.length;
     // loop to access each array element
     for (int i = 0; i < size - 1; i++)
       // loop to compare array elements
       for (int j = 0; j < size - i - 1; j++)
         // compare two adjacent elements
         // change > to < to sort in descending order
         if (array[j] > array[j + 1]) {
           // swapping occurs if elements
           // are not in the intended order
           int temp = array[j];
           array[j] = array[j + 1];
           array[j + 1] = temp;
         }
   }
   public static void main(String args[]) {
     int[] data = { -122, 46, 0, 28, -79 };
     // call method using class name
     Main.bubbleSort(data);
     System.out.println("Sorted Array in Ascending Order:");
     System.out.println(Arrays.toString(data));
   }
 }

 // Bubble sort in C++
 #include <iostream>
 using namespace std;
 // perform bubble sort
 void bubbleSort(int array[], int size) {
   // loop to access each array element
   for (int step = 0; step < size; ++step) {
     // loop to compare array elements
     for (int i = 0; i < size - step; ++i) {
       // compare two adjacent elements
       // change > to < to sort in descending order
       if (array[i] > array[i + 1]) {
         // swapping elements if elements
         // are not in the intended order
         int temp = array[i];
         array[i] = array[i + 1];
         array[i + 1] = temp;
       }
     }
   }
 }
 // print array
 void printArray(int array[], int size) {
   for (int i = 0; i < size; ++i) {
     cout << " " << array[i];
   }
   cout << "\n";
 }
 int main() {
   int data[] = {-122, 46, 0, 28, -79};
   // find array's length
   int size = sizeof(data) / sizeof(data[0]);
   bubbleSort(data, size);
   cout << "Sorted Array in Ascending Order:\n"; 
   printArray(data, size);
 }

Output

 Sorted Array in Ascending Order:
[-79, -122, 0, 28, 46]

Bubble sort complexity

Bubble sort is a simple comparison-based sorting algorithm that compares adjacent pairs of elements and swaps them if they are in the wrong order. It repeats this process until the array is sorted. There are two types of complexity in the bubble sort algorithm, which are

The time complexity of bubble sort- Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. The time complexity of bubble sort depends on the number of comparisons and swaps it performs. In the worst case, where the input array is in reverse order, bubble sort makes n*(n-1)/2 comparisons and swaps, where n is the number of elements in the array. Therefore, the time complexity of bubble sort is O(n^2), where "O" stands for Big O notation, which is used to describe the upper bound of the running time of an algorithm. Bubble sort is not an efficient algorithm for large datasets, as its time complexity is quadratic. However, it can be useful for small datasets or for educational purposes, as it is easy to understand and implement

The space complexity of bubble sort- The space complexity of bubble sort is O(1), which means that the algorithm sorts the input array in place, without using any additional memory or data structures other than the input array itself. Bubble sort works by comparing adjacent elements in the array and swapping them if they are in the wrong order. The algorithm continues to iterate through the array until no more swaps are needed, indicating that the array is sorted. Because bubble sort only requires a constant amount of additional memory to store temporary variables used in the swapping process, its space complexity is O(1).

Optimized Bubble Sort

There are a few Optimized Bubble Sort that can improve its performance, those are

• Optimized Swapping: In the standard implementation of Bubble Sort, adjacent elements are swapped regardless of whether they are in the correct order or not. This means that the algorithm may perform unnecessary swaps. An optimization is to keep track of whether a swap has been made during an iteration. If no swaps were made, then the list is already sorted, and the algorithm can terminate. This optimization can significantly reduce the number of iterations required.
• Early Termination: Bubble Sort iterates over the entire list multiple times, even if the list is already sorted. An optimization is to add a check after each iteration to see if any swaps were made. If no swaps were made, then the list is already sorted, and the algorithm can terminate early.
• Adaptive Bubble Sort: This optimization takes advantage of the fact that the largest element in the list will "bubble" to the end in each pass. After the first iteration, the algorithm only needs to iterate up to the last swapped index, as elements beyond that index are already sorted.
• Combining with other sorting algorithms: Combining Bubble Sort with another algorithm can improve its performance. For example, the cocktail shaker sort is a variation of Bubble Sort that sorts in both directions. This approach reduces the number of iterations required to sort the list.

Optimized Bubble Sort Algorithm

 bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

 # Optimized Bubble sort in Python
 def bubbleSort(array):
   # loop through each element of array
   for i in range(len(array)):
     # keep track of swapping
     swapped = False
     # loop to compare array elements
     for j in range(0, len(array) - i - 1):
       # compare two adjacent elements
       # change > to < to sort in descending order
       if array[j] > array[j + 1]:
         # swapping occurs if elements
         # are not in the intended order
         temp = array[j]
         array[j] = array[j+1]
         array[j+1] = temp
         swapped = True
     # no swapping means the array is already sorted
     # so no need for further comparison
     if not swapped:
       break
 data = [-122, 46, 0, 28, -79]
 bubbleSort(data)
 print('Sorted Array in Ascending Order:')
 print(data)

 // Optimized Bubble sort in Java
 import java.util.Arrays;
 class Main {
   // perform the bubble sort
   static void bubbleSort(int array[]) {
     int size = array.length;
     // loop to access each array element
     for (int i = 0; i < (size-1); i++) {
       // check if swapping occurs
       boolean swapped = false;
       // loop to compare adjacent elements
       for (int j = 0; j < (size-i-1); j++) {
         // compare two array elements
         // change > to < to sort in descending order
         if (array[j] > array[j + 1]) {
           // swapping occurs if elements
           // are not in the intended order
           int temp = array[j];
           array[j] = array[j + 1];
           array[j + 1] = temp;
           swapped = true;
         }
       }
       // no swapping means the array is already sorted
       // so no need for further comparison
       if (!swapped)
         break;
     }
   }
   public static void main(String args[]) {
     int[] data = { -122, 46, 0, 28, -79 };
     // call method using the class name
     Main.bubbleSort(data);
     System.out.println("Sorted Array in Ascending Order:");
     System.out.println(Arrays.toString(data));
   }
 }

 // Optimized bubble sort in C++
 #include <iostream>
 using namespace std;
 // perform bubble sort
 void bubbleSort(int array[], int size) {
   // loop to access each array element
   for (int step = 0; step < (size-1); ++step) {
     // check if swapping occurs
     int swapped = 0;
     // loop to compare two elements
     for (int i = 0; i < (size-step-1); ++i) {
       // compare two array elements
       // change > to < to sort in descending order
       if (array[i] > array[i + 1]) {
         // swapping occurs if elements
         // are not in intended order 
         int temp = array[i];
         array[i] = array[i + 1];
         array[i + 1] = temp;
         swapped = 1;
       }
     }
     // no swapping means the array is already sorted
     // so no need of further comparison
     if (swapped == 0)
       break;
   }
 }
 // print an array
 void printArray(int array[], int size) {
   for (int i = 0; i < size; ++i) {
     cout << " " << array[i];
   }
   cout << "\n";
 }
 int main() {
   int data[] = {-122, 46, 0, 28, -79};
   // find the array's length
   int size = sizeof(data) / sizeof(data[0]);
   bubbleSort(data, size);
   cout << "Sorted Array in Ascending Order:\n";
   printArray(data, size);
 }

Output

 Sorted Array in Ascending Order:
 -122, -79, 0, 28, 46

Summary

In conclusion, the bubble sort algorithm is an effective tool to help organize data. It is relatively easy to learn and can be adapted for more powerful sorting with greater complexity. With the proper analysis and application, it can quickly produce useful results with the right dataset. The use of the bubble sort algorithm in combination with other algorithms is a great way to maximize productivity and efficiency. For those looking to master one of the fundamental sorting techniques, this should absolutely be something that you take into account as you continue learning computer science concepts. As always, feel free to reach out if you have any questions or suggestions regarding this article.