 Tagged
• Algorithm
• Sorting
•

# Introduction

Bubble Sort is the easiest sorting algorithm in which adjacent elements are compared with each other and swapped if the elements are not in proper order. This process repeatedly scans the elements of the list and each iteration one element will be placed at the correct position starting with the first max element, second max element and so on.

# Algorithm

```1Step 0 : Initialize n to length of the array 2
3Step 1 : Initialize j to 0 and compare a[j] with a[j+1] 4         (Compare adjacent elements starting from 0th index) 5
6Step 2 : if a[j] > a[j+1] swap a[j] and a[j+1] 7
8Step 3 : repeat steps 1 and 2 until j reached end of the array 9         (By end of this one element will be placed at its correct order) 10
11Step 4 : continue from Step 1 n-1 times 12         (So that all elements will be in proper order) ```

# Example Explanation

Input array : a = [5, 3, 13, 2, 11, 4, 7]

Iteration 1 :

Step 1 : Initialize j = 0 & compare first element (a) and second element (a)

Step 2 : As a[j] > a[j+1] , swap a[j] and a[j+1]

Step 3 : Increment j and continue Step 2 until we reach the end of the array.

At the end of iteration 1, the max element will be placed at the last index of the array. We continue the same process n-1 times for the remaining unsorted array.

Iteration 2 :

Iteration 3 :

Iteration 4 :

Iteration 5 :

Iteration 6 :

# Code Implementation

```1public class BubbleSort {2
3    // Method to sort a given array4    public void sort(int[] array){5        int n = array.length;6
7        //loop through elements of the array8        for(int i=0;i<n-1;i++){9
10            // loop to compare elements of the array11            for(int j=0;j<n-i-1;j++){12
13                // compare adjacent elements14                if(array[j] > array[j+1]){15                    16                    // if adjacent elements are not in sorted order17                    // swap the elements18                    swap(array, j, j+1);19                }20            }21        }22    }23
24    // method to swap elements in an array25    private void swap(int[] array, int i, int j){26        int temp = array[i];27        array[i] = array[j];28        array[j] = temp;29    }30
31    // Helper method to print an array32    private void print(int[] array) {33        for(int i=0; i<array.length; i++) {34            System.out.print(array[i]+"\t");35        }36        System.out.println();37    }38
39    // Driver Code40    public static void main(String[] args){41        int[] a = {5, 3, 13, 2, 11, 4, 7};42        BubbleSort obj = new BubbleSort();43        obj.print(a);44        obj.sort(a);45        obj.print(a);46    }47
48}```

# Optimized Bubble Sort

## Observation

As per the explanation given for an example, if we notice at the end of iteration 3, the array is fully sorted, and during 4th iteration there are no swap operations performed, by using this observation we can stop further scans to optimize the bubble sort algorithm. Using this optimized technique we will achieve O(n) time complexity in the best case (Input array is already in sorted order).

## Implementation

```1public class BubbleSortOptimized {2
3    // Method to sort the given array4    public void sort(int[] array) {5        int n = array.length;6
7        // Iterate through elements of array8        for(int i=0;i<n-1;i++) {9
10            // use flag swapped to check occurrence of swap operation11            boolean swapped = false;12
13            // loop through array14            // compare adjacent elements of the array15            for(int j=0;j<n-i-1;j++) {16
17                if(array[j] > array[j+1]) {18
19                    swap(array, j, j + 1);20                    21                    // update swapped to true22                    swapped = true;23                }24            }25            // no swapping happened entire array26            // it means array is already in sorted order27            if(!swapped) {28               return;29            }30        }31    }32
33    // Helper method to swap two elements in the array34    private void swap(int[] array, int i, int j) {35        int temp = array[i];36        array[i] = array[j];37        array[j] = temp;38    }39
40    // Helper method to print an array41    private void print(int[] array) {42        for(int i=0; i<array.length; i++) {43            System.out.print(array[i]+"\t");44        }45        System.out.println();46    }47
48    // Driver Method49    public static void main(String[] args){50        int[] a = {5, 3, 13, 2, 11, 4, 7};51        BubbleSortOptimized obj = new BubbleSortOptimized();52        obj.print(a);53        obj.sort(a);54        obj.print(a);55    }56}```

# Complexity Analysis

Time Complexity :

• Best Case : O(n)
• Worst Case : O(n^2)

Space Complexity : O(1).

• Algorithm
• Sorting
•
...