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