Sorting Algorithm - Selection Sort

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.

The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.

Note: consider it in ascending order.

Time Complexity:  O(n^2)
Space Complexity: O(1) because the good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Sample Code Implementation in Java:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class SelectionSortApp
{

public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public void selectionSort(int arr[])
{
int min_idx;
int n=arr.length;

for(int i=0;i<n-1;i++)
{
min_idx=i;
for(int j=i+1; j<n;j++)
if(arr[j] <arr[min_idx])
min_idx=j;

int temp=arr[min_idx];
arr[min_idx]=arr[i];
arr[i]=temp;
}
}

public static void main(String[] args)
{
SelectionSortApp ob=new SelectionSortApp();
int arr[] = {64,25,12,22,11};
        ob.selectionSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
}
}

OutPut: Sorted array

11
12
22
25
64

Selection Sort java

Selection Sort:

The selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N^2) to O(N) .Unfortunately the number of comparisons remains O(N^2) .

Brief Description:

What involved in the selection sort is making a pass through all the players and picking the shortest one.This shortest player is then swapped with the player o the left end of the line,at position 0.now the left most player is sorted and wont need to be moved again.Notice in this algorithm the sorted players accumulate on the left,whereas in the bubble sort they accumulated on the right.

Selection Sort Workshop:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */

class ArraySel
{
  private long[] a;
  private int nElems;

  public ArraySel(int max)
  {
a=new long[max];
nElems=0;
  }

  public void insert(long value)
  {
 a[nElems]=value;
 nElems++;
  }

  public void display()
  {
 for(int j=0;j<nElems;j++)
 System.out.println(a[j] + " ");
 System.out.println(" ");
  }

  public void selectionSort()
  {
 int min,in,out;
 for(out=0;out<nElems;out++)
 {
 min=out;
 for(in=out+1;in<nElems;in++)
 {
 if(a[in] < a[min])
 min=in;
 swap(out,min);

 }
 }
  }

private void swap(int one, int two)
{
long temp=a[one];
a[one]=a[two];
a[two]=temp;

}


}

public class SelectionSortTest {

/**
*
*/
public SelectionSortTest() {
// TODO Auto-generated constructor stub
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub


ArraySel arr=new ArraySel(100);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);

arr.display(); // before sort

arr.selectionSort();

arr.display(); //after sort


}


}

Complexity of Selection Sort:

It performs the same number of comparisons as the bubble sort: N*(N-1)/2 .

So Selection sort runs in O(N^2) .