Sorting

Bubble sort

Pinterest LinkedIn Tumblr

Bubble sort is a simple sorting algorithm. It compares each item from the array and swap with an adjacent item if they are not in order. The main advantage of bubble sort is an easy implementation. Bubble sort has poor performance and should be avoided in case of a large number of elements in the array.

Write a program to take the un-sorted array and sort the array using bubble sort.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class BubbleSort {
         
         public static void bubbleSort(int[] unsorted){
              
             for(int i = 0; i < unsorted.length-1; i++){
                 for(int j = 1;j < unsorted.length; j++){
                     if(unsorted[j-1] > unsorted[j]){
                         int temp = unsorted[j];
                         unsorted[j] = unsorted[j-1];
                         unsorted[j-1]=temp;
                     }
                 }
             }
         }
 
        public static void main(String[] args) {
            int[]arr = {34,56,23,45,67,3};
            System.out.println("Unsorted array before sorting: " + Arrays.toString(arr));
            bubbleSort(arr);
            System.out.println("Sorted array After Bubble Sort sorting: " + Arrays.toString(arr));
        }
 
    }

Output

Unsorted array before sorting: [34, 56, 23, 45, 67, 3]
Sorted array After Bubble Sort sorting: [3, 23, 34, 45, 56, 67]

Algorithm Explanation

Take unsorted array as input.
Compare each pair of adjacent elements from the beginning of an array.
If they are in reversed order, swap them. Otherwise, keep the same order.
Repeat the above steps till complete all the elements from the array.
Return the sorted array.

Time Complexity

Best CaseAverage CaseWorst Case
O(n)O(n^2)O(n^2)

Reference

  1. http://en.wikipedia.org/wiki/Bubble_sort
  2. https://study.cs50.net/bubble_sort
  3. http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html

Write A Comment