Selection Sort

Selection Sort:

It is a sorting technique. It improves bubble sort by making
only one exchange for every pass through the list of elements. First selection
sort looks for the largest value when it through the pass and after completing
the pass, after that it place in a proper location.

Time complexity of Selection sort: O(n²)

Average Performance: O(n²)

Worst case Performance: O(n²)

Best case performance: O(n²)

Worst Case Space complexity: O(n) total, O(1) auxiliary.

Example on Selection Sort:

52, 45, 789, 46, 89 [Initial Array of elements]

45, 52, 789, 46, 89 [After the first pass, First sub list
{45}]

45, 46, 52, 789, 89 [After the second pass, Second sub list
{45, 46}]

45, 46, 52, 89, 789 [After the third pass, Third sub list
{45, 46, 52}]

45, 46, 52, 89, 789 [After the fourth pass, Fourth sub list
{45, 46, 52, 89}]

45, 46, 52, 89, 789 [After the fifth pass or Last pass, sub
list {45, 46, 52, 89, 789}]

Algorithm for Selection Sort:

Start

Construct a single dimensional array

Fill the array with elements.

Using the selection sort technique bring the smallest number
to the first unsorted position of the array.

Repeat the last step till the entire array is sorted.

Print the sorted array

Stop.

Program for selection Sort in java:

public class SelectionSort {
    public static void selectionSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) 
        { 
            int index = i; 
            for (int j = i + 1; j < arr.length; j++){ 
                if (arr[j] < arr[index]){ 
                    index = j;//searching for lowest index 
                } 
            } 
            int smallerNumber = arr[index];  
            arr[index] = arr[i]; 
            arr[i] = smallerNumber; 
        } 
    } 
      
    public static void main(String a[]){  
        int[] arr1 = {9,14,3,2,43,11,58,22}; 
        System.out.println("Before Selection Sort"); 
        for(int i:arr1){ 
            System.out.print(i+" "); 
        } 
        System.out.println(); 
         
        selectionSort(arr1);//sorting array using selection sort 
        
        System.out.println("After Selection Sort"); 
        for(int i:arr1){ 
            System.out.print(i+" "); 
        } 
    } 
}
 

Output of the above program:

Before Selection Sort
9 14 3 2 43 11 58 22
After Selection Sort
2 3 9 11 14 22 43 58