Saturday 22 August 2015

Selection Sort Java

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