Bubble Sort

Description

Given an array the Bubble sort will sort them in the increasing order, it repeatedly compares adjacent items. If the item on the left is greater, it swaps it with the right item. Basically the greater items are shifted towards the right direction.
Furthermore, the second iteration is stopped because the last items are sorted already we wont go though them again.

However, Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is only useful for small data sets. Worst case and average case time complexity is in the big o notation represantation is O(n^2)

Code

In the below snipped there are two variants of Bubble sort is given, the optimized solution exceeds shorter than the non-optimized version.

public class BubbleSort {
    public static void main(String[] args) {
        int[] items = new int[]{3, 2, 5, 1};
        int[] items2 = new int[]{3, 2, 5, 1};
        bubbleSort(items);
        bubbleSortOptimized(items2);
        printValues(items);
        printValues(items2);
    }

    private static void printValues(int[] items) {
        System.out.println("\nprinting the sorted items");
        for (int i : items) {
            System.out.println(i);
        }
    }

    private static void bubbleSort(int[] items) {
        final int arrLen = items.length;
        for (int i = 0; i < arrLen; i++) {
            final int nestedMax = arrLen - 1 - i;
            for (int j = 0; j < nestedMax; j++) {
                int curr = items[j];
                int next = items[j + 1];
                if (curr > next) {
                    System.out.println("swapping " + curr + " with " + next);
                    int temp = curr;
                    items[j] = next;
                    items[j + 1] = temp;
                }
            }
        }
    }

    private static void bubbleSortOptimized(int[] items) {
        int i = 0;
        int arrLen = items.length;
        boolean swapped = true;
        while (i < arrLen - 1 && swapped) {
            swapped = false;
            for (int j = 1; j < arrLen - i; j++) {
                if (items[j - 1] > items[j]) {
                    System.out.println("swapping " + items[j - 1] + " with " +  items[j]);
                    int temp = items[j - 1];
                    items[j - 1] = items[j];
                    items[j] = temp;
                    swapped = true;
                }
            }
            if (!swapped)
                break;
            i++;
        }
    }
}

 

Console Output

swapping 3 with 2
swapping 5 with 1
swapping 3 with 1
swapping 2 with 1
swapping 3 with 2
swapping 5 with 1
swapping 3 with 1
swapping 2 with 1

printing the sorted items
1
2
3
5

printing the sorted items
1
2
3
5

 

Leave a Reply

Your email address will not be published. Required fields are marked *