Program to implement Bubble Sort Algorithm

Write a Program to implement Bubble sort.
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.

Example 1:

Input: [64, 34, 25, 12, 22, 11, 90]

Output: [11, 12, 22, 25, 34, 64, 90]

Example 2:

Input: [5, 1, 4, 2, 8]

Output: [1, 2, 4, 5, 8]

Algorithm to implement Bubble sort:

Compare the first element to the second element.
If the first element is greater than the second element, they are swapped.
Move to the next element and repeat the process until the last element of the array.
After each pass, the next-to-last element is sorted.
Repeat the steps until the whole array is sorted.

C++ Program to implement Bubble sort

cpp

#include<iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    int i, j;
    bool swapped;
    for (i = 0; i < n-1; i++) {
        swapped = false;
        // Last i elements are already in place
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        // If no two elements were swapped by inner loop, then break
        if (swapped == false)
            break;
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i=0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Java Program to implement Bubble sort

java

public class BubbleSort {
    void bubbleSort(int arr[]) {
        int n = arr.length;
        int temp = 0;
        for(int i=0; i < n; i++){
            for(int j=1; j < (n-i); j++){
                if(arr[j-1] > arr[j]){
                    //swap elements
                    temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    void printArray(int arr[]) {
        for(int i=0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BubbleSort ob = new BubbleSort();
        int arr[] = {5, 1, 4, 2, 8};
        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }
}

Python Program to implement Bubble sort

python

def bubbleSort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n-1):
        # Last elements are already in place
        for j in range(0, n-i-1):
            # Traverse the array from 0 to 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]

# Function to print an array
def printArray(arr):
    for i in range(len(arr)):
        print("%d" % arr[i], end=" ")
    print()

# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("Sorted array is:")
printArray(arr)

Time Complexity of Bubble sort:

Worst and Average Case Time Complexity: O(n^2). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

Auxiliary Space:

O(1).

Boundary Cases:

Bubble sort takes minimum time (Order of n) when elements are already sorted.

Related Articles