Showing posts with label Bubble Sort. Show all posts
Showing posts with label Bubble Sort. Show all posts

Monday, May 16, 2016

Bubble Sort in Java

Bubble sort code in Java:
package com.kpatil.sort;

public class BubbleSort {
 public static void sort(int[] list) {
  int n = list.length;
  boolean swapped = true;
  while (swapped) {
   swapped = false;
   for (int i = 1; i < n; i++) {
    if (list[i - 1] > list[i]) {
     int temp = list[i - 1];
     list[i - 1] = list[i];
     list[i] = temp;
     swapped = true;
    }
   }
   n = n - 1;
  }
 }
}
JUnit Test Cases:
package com.kpatil.test;

import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;
import com.kpatil.sort.BubbleSort;

public class BubbleSortTest {

 @Test
 public void test1() {
  int[] array = { 5, 2, 89, 0, 10, 3, 20, 1 };
  int[] sorted = { 0, 1, 2, 3, 5, 10, 20, 89 };
  BubbleSort.sort(array);
  assertEquals(true, Arrays.equals(array, sorted));
 }

 @Test
 public void test2() {
  int SIZE = 1000;
  int[] list = new int[SIZE];
  int[] expectedList = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   int rand = (int) (Math.random() * SIZE);
   list[i] = rand;
   expectedList[i] = rand;
  }
  BubbleSort.sort(list);
  Arrays.sort(expectedList);
  assertEquals(true, Arrays.equals(list, expectedList));
  
  for (int i = 0; i < SIZE; i++) {
   System.out.print(list[i] + " ");
  }
  System.out.println();
 }

}

Tuesday, October 27, 2015

Optimized Bubble Sort in Java

Bubble sort is a simplest sorting algorithm which is used as a traditional method to introduce sorting concept to the students of computer science. Though it is not very efficient algorithm, it illustrates the sorting methodology very well.

Here is a bubble sort algorithm with "two optimizations" (think!!) :



















Could you find out the optimizations used in above java code?
Best case running time for this algorithm in O(n) and worst case running time is O(n^2).