Amazon Prime




 
Tagged
  • Algorithm
  • Sorting
  •  

    Bubble Sort Algorithm

    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[0]) and second element (a[1])

    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.

    Bubble Sort Iteration1

    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 :

    Bubble Sort Iteration2

    Iteration 3 :

    Bubble Sort Iteration3

    Iteration 4 :

    Bubble Sort Iteration4

    Iteration 5 :

    Bubble Sort Iteration5

    Iteration 6 :

    Bubble Sort Iteration6

    Code Implementation

    1public class BubbleSort {
    2
    3 // Method to sort a given array
    4 public void sort(int[] array){
    5 int n = array.length;
    6
    7 //loop through elements of the array
    8 for(int i=0;i<n-1;i++){
    9
    10 // loop to compare elements of the array
    11 for(int j=0;j<n-i-1;j++){
    12
    13 // compare adjacent elements
    14 if(array[j] > array[j+1]){
    15
    16 // if adjacent elements are not in sorted order
    17 // swap the elements
    18 swap(array, j, j+1);
    19 }
    20 }
    21 }
    22 }
    23
    24 // method to swap elements in an array
    25 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 array
    32 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 Code
    40 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 array
    4 public void sort(int[] array) {
    5 int n = array.length;
    6
    7 // Iterate through elements of array
    8 for(int i=0;i<n-1;i++) {
    9
    10 // use flag swapped to check occurrence of swap operation
    11 boolean swapped = false;
    12
    13 // loop through array
    14 // compare adjacent elements of the array
    15 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 true
    22 swapped = true;
    23 }
    24 }
    25 // no swapping happened entire array
    26 // it means array is already in sorted order
    27 if(!swapped) {
    28 return;
    29 }
    30 }
    31 }
    32
    33 // Helper method to swap two elements in the array
    34 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 array
    41 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 Method
    49 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
  •  
    ...