Studyon Minte9.com
Algorithms (Codingbat)




Bubble Sort



Sort an integer array without using API methods

       %java
		package testexample;
		import java.util.Arrays;
		import org.junit.Assert.*;
		import junit.framework.*;

		public class Testexample extends TestCase {

		    public static void main(String[] args) {
			
			assertTrue(Arrays.equals(new int[]{11,22,33,44}, arrSort(new int[]{44,33,22,11})));
		    }

		    public static int[] arrSort(int[] nums) {
			
			for (int i=0; i<nums.length-1; i++) {
			    
			    // i: 0,1,2,3
			    
			    for (int j=1; j<nums.length-i; j++) {
				
				// j: 1,2,3 / 1,2 / 1
						 
				if (nums[j-1] > nums[j]) {
				    
				    int tmp = nums[j];
				    
				    nums[j] = nums[j-1];
				    nums[j-1] = tmp;
				}

				System.out.println(i + " j:" + j);
			    } 

			    System.out.println(Arrays.toString(nums));  
			    
			    // 44 -> 33, 22, 11, 44
			    // 33 -> 22, 11, 33, 44
			    // 22 -> 11, 22, 33, 44
			}

			return nums;
		    }
		}



* Poor performance (1734 vs 16)

	%java
		package testexample;
		import java.util.*;
		import org.junit.Assert.*;
		import junit.framework.*;

		public class Testexample extends TestCase {

		    public static void main(String[] args) {

			int[] nums = new int[30000];
			for (int i=0; i<nums.length; i++) {
			    nums[nums.length - 1 - i] = i; 
			}
			
			long a = 0;
			long b = 0;
			
			a = System.currentTimeMillis();
			arrSortBubble(nums);
			b = System.currentTimeMillis();
			
			System.out.println(b-a);
				// 1734

			a = System.currentTimeMillis();
			Arrays.sort(nums);
			b = System.currentTimeMillis();
			
			System.out.println(b-a);
				// 16
		    }

		    public static int[] arrSortBubble(int[] nums) {
				
			for (int i=0; i<nums.length-1; i++) {
			    for (int j=1; j<nums.length-i; j++) {                
				if (nums[j-1] > nums[j]) {
				    int tmp = nums[j];
				    nums[j] = nums[j-1];
				    nums[j-1] = tmp;
				}
			    } 
			}
			return nums;
		    }
		}


http://java67.blogspot.sg/2012/12/bubble-sort-in-java-program-to-sort-integer-array-example.html