Bubble Sort

Bubble sort is one of the easiest sorting algorithms available, it is also known as Sinking Sort and Exchange Sort.

Bubble sort doesn't require creating another array hence also known as in-place sorting algorithm.

In every step or pass, Bubble Sort Compares Adjacent elements.
With each pass, the largest element will be moved to the end and the unsorted array size will be reduced.

The algorithm is simple

1. The outer loop will run up to the number of elements in the array times.
2. The inner loop will run -1 time of the outer loop
3. with each iteration, it will compare if the current element is greater than its next. yes yes, then swap the elements.

package org.wesome.dsalgo;

public class BubbleSort {
    public static int[] bubbleSort(int[] ints) {
        int temp;
        for (int i = 0; i < ints.length; i++) {
            System.out.print( i + " pass, ");
            for (int j = 1; j < ints.length - i; j++) {
                System.out.println("comparing " + ints[j - 1] + " and " + ints[j]);
                if (ints[j - 1] > ints[j]) {
                    System.out.println(ints[j - 1] + " is greater then " + ints[j] + " , so swap there place");
                    temp = ints[j];
                    ints[j] = ints[j - 1];
                    ints[j - 1] = temp;
                }
            }
        }
        return ints;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class BubbleSortTest {

    @Test
    void bubbleSort1() {
        int[] bubbleSort = BubbleSort.bubbleSort(new int[]{6, 5, 4, 3, 2, 1});
        Assertions.assertArrayEquals(new int[]{1, 2, 3, 4, 5, 6}, bubbleSort);
    }

    @Test
    void bubbleSort2() {
        int[] bubbleSort = BubbleSort.bubbleSort(new int[]{-1, -2, -4, -5, -3, -6});
        Assertions.assertArrayEquals(new int[]{-6, -5, -4, -3, -2, -1}, bubbleSort);
    }
}

plugins {
    id 'java'
}

group 'org.example'
version '1.0-SNAPSHOT'

repositories {
    mavenCentral()
}

dependencies {
    testImplementation('org.junit.jupiter:junit-jupiter:5.6.2')
}

test {
    useJUnitPlatform()
}

Space Complexity
Since Bubble sort doesn't require a new array creation hence space complexity is constant ie O(1)

Time Complexity
The best case is when all the elements are already sorted then O(n)
worst case when none of the elements is sorted then O(n)2
 

Already sorted Array

let's consider a scenario where the array is already sorted. then as per the algorithm, the inner loop will check if the current element is greater than its previous, but since the entire array is already sorted, there will not be any swapping.

package org.wesome.dsalgo;

public class BubbleSort {
    public static int[] bubbleSort(int[] ints) {
        int temp;
        boolean swap;
        for (int i = 0; i < ints.length; i++) {
            swap = false;
            System.out.print(i + " pass, ");
            for (int j = 1; j < ints.length - i; j++) {
                System.out.println("comparing " + ints[j - 1] + " and " + ints[j]);
                if (ints[j - 1] > ints[j]) {
                    System.out.println(ints[j - 1] + " is greater then " + ints[j] + " , so swap there place");
                    temp = ints[j];
                    ints[j] = ints[j - 1];
                    ints[j - 1] = temp;
                    swap = true;
                }
            }
            if (!swap) {
                System.out.println("for i = " + i + " swap value is " + swap + " it means there was no swapping for this pass, so rest of the elements are already sorted, hence breaking this loop");
            }
        }
        return ints;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class BubbleSortTest {

    @Test
    void bubbleSort1() {
        int[] bubbleSort = BubbleSort.bubbleSort(new int[]{6, 5, 4, 3, 2, 1});
        Assertions.assertArrayEquals(new int[]{1, 2, 3, 4, 5, 6}, bubbleSort);
    }

    @Test
    void bubbleSort2() {
        int[] bubbleSort = BubbleSort.bubbleSort(new int[]{-1, -2, -3, -4, -5, -6});
        Assertions.assertArrayEquals(new int[]{-6, -5, -4, -3, -2, -1}, bubbleSort);
    }

    @Test
    void bubbleSort3() {
        int[] bubbleSort = BubbleSort.bubbleSort(new int[]{1, 2, 3, 4, 5, 6});
        Assertions.assertArrayEquals(new int[]{1, 2, 4, 5, 3, 6}, bubbleSort);
    }
}

plugins {
    id 'java'
}

group 'org.example'
version '1.0-SNAPSHOT'

repositories {
    mavenCentral()
}

dependencies {
    testImplementation('org.junit.jupiter:junit-jupiter:5.6.2')
}

test {
    useJUnitPlatform()
}