Selection
sort algorithm sorts an array by repeatedly finding the minimum element (considering
ascending order) from unsorted part and putting it at the beginning.
Following
video explains it clearly.
For example,
for elements {15, 6, 3, 199, 20, 2}
Iteration 1: {2, 6, 3, 199, 20, 15} (2 is placed at first)
Iteration 2: {2, 3, 6, 199, 20, 15} (3 is placed after 2)
Iteration 3: No change
Iteration 4: {2, 3, 6, 15, 20, 199} (15 is placed after 6)
Iteration 5: No change
Itertion 6: No Change
Following is
the complete application for selection sort.
import java.util.Objects; public class SelectionSort<T extends Comparable<T>> { private T[] arr; /** * If flag is true, then elements are sorted in ascending order, else * descending order */ public void sort(T[] arr, boolean flag) { Objects.nonNull(arr); this.arr = arr; if (flag == true) sortAscending(); else sortDescending(); } private void sortDescending() { int length = arr.length - 1; for (int i = 0; i < arr.length; i++) { int index = findMinimumIndex(0, length); swap(index, length); length--; } } private void sortAscending() { int length = arr.length - 1; for (int i = 0; i < arr.length; i++) { int index = findMinimumIndex(i, length); swap(index, i); } } /** * Return index of minimum element */ private int findMinimumIndex(int from, int to) { T min = arr[from]; int index = from; for (int i = from + 1; i <= to; i++) { if (arr[i].compareTo(min) < 0) { min = arr[i]; index = i; } } return index; } private void swap(int i, int j) { T temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
Following is
the junit test case for above program.
import static org.junit.Assert.assertTrue; import java.util.Arrays; import org.junit.Test; public class SelectionSortTest { @Test public void test1() { SelectionSort<Integer> obj1 = new SelectionSort<>(); 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