Studyon Minte9.com
Algorithms (Codingbat)




Insert Sort



Sort an integer array without using API methods

	%java
		package testexample;

		import java.util.*;
		import org.junit.Assert.*;
		import junit.framework.*;

		public class Testexample extends TestCase {

		    public static void main(String[] args) {
			
			assertTrue( Arrays.equals( new int[]{0,1,2,3,4}, insertSortOne(new int[]{1,2,3,4,0}) ) );
                            // almost sort array

			assertTrue( Arrays.equals( new int[]{0,1,2,3,4}, insertSortAll(new int[]{3,2,1,4,0}) ) );
		    }

		    public static int[] insertSortOne(int[] nums) {

			int i = nums.length - 1;
			int curr = nums[i]; // 0
			while(i>0 && nums[i-1] > curr) {
			    nums[i] = nums[i-1];
			    nums[i-1] = curr;
			    i--;
			    
			    // System.out.println(Arrays.toString(nums));
			    /*  
				[1, 2, 3, 4, 0]
				[1, 2, 3, 0, 4]
				[1, 2, 0, 3, 4]
				[1, 0, 2, 3, 4]
				[0, 1, 2, 3, 4]
			    */
			}

			return nums;
		    }
		    
		    public static int[] insertSortAll(int[] nums) {
			
			for (int j=1; j<nums.length; j++) {
			    int i = j;
			    int curr = nums[i];
			    while(i>0 && nums[i-1] > curr) {
				nums[i] = nums[i-1];
				nums[i-1] = curr;
				i--;
			    }
			    
			    // System.out.println(Arrays.toString(nums));
			    /*  
				[3, 2, 1, 4, 0]
				[2, 3, 1, 4, 0] - sort first 2 elements
				[1, 2, 3, 4, 0] - sort first 3 elements
				[1, 2, 3, 4, 0]
				[0, 1, 2, 3, 4]
			    */
			}

			return nums;
		    }
		}


* Poor performance (1125 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 start = 0;
			long end = 0;
			
			start = System.currentTimeMillis();
			insertSort(nums);
			end = System.currentTimeMillis();
			
			System.out.println(end - start); // 1125
			
			start = System.currentTimeMillis();
			Arrays.sort(nums);
			end = System.currentTimeMillis();
			
			System.out.println(end - start); // 16
			
			
		    }
		    
		    public static int[] insertSort(int[] nums) {
			
			for (int j=1; j<nums.length; j++) {
			    int i = j;
			    int curr = nums[i];
			    while(i>0 && nums[i-1] > curr) {
				nums[i] = nums[i-1];
				nums[i-1] = curr;
				i--;
			    }
			}

			return nums;
		    }
		}


http://studyon.minte9.com/article/useraccount/show/id/555