For each
iteration, insertion sort removes one element from the input data, finds the
location it belongs within the sorted list, and inserts it there.
Following
video explains it clearly.
For example,
For the
input 20, 5, 14, 19, 8, 17
Iteration 1: 5, 20, 14, 19, 8, 17 (Fix position of element 5)
Iteration 2: 5, 14, 20, 19, 8, 17 (Fix position of element 14)
Iteration 3: 5, 14, 19, 20, 8, 17 (Fix position of element 19)
Iteration 4: 5, 8, 14, 19, 20, 17 (Fix position of element 8)
Iteration 5: 5, 8, 14, 17, 19, 20 (Fix position of element 17)
Following is
the generic program for insertion sort.
public class InsertionSort<T extends Comparable<T>> { /** * If flag is true, then elements are sorted in ascending order, else * descending order */ public void sort(T[] arr, boolean flag) { if (flag == true) sortAscending(arr); else sortDescending(arr); } private void sortDescending(T[] arr) { for (int i = 1; i < arr.length; i++) { T temp = arr[i]; int j; for (j = i - 1; j >= 0; j--) { if (temp.compareTo(arr[j]) > 0) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = temp; } } private void sortAscending(T[] arr) { for (int i = 1; i < arr.length; i++) { T temp = arr[i]; int j; for (j = i - 1; j >= 0; j--) { if (temp.compareTo(arr[j]) < 0) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = temp; } } }
Following is
the junit test case for above program.
import static org.junit.Assert.*; import java.util.Arrays; import org.junit.Test; public class InsertionSortTest { @Test public void test1() { InsertionSort<Integer> obj1 = new InsertionSort<>(); Integer arr1[] = { 5, 46, 25, 13, 12 }; Integer arr2[] = { 5, 46 }; obj1.sort(arr1, true); assertTrue(Arrays.equals(arr1, new Integer[] { 5, 12, 13, 25, 46 })); obj1.sort(arr1, false); assertTrue(Arrays.equals(arr1, new Integer[] { 46, 25, 13, 12, 5 })); obj1.sort(arr2, true); assertTrue(Arrays.equals(arr2, new Integer[] { 5, 46 })); obj1.sort(arr2, false); assertTrue(Arrays.equals(arr2, new Integer[] { 46, 5 })); } }
No comments:
Post a Comment