Selection Sort

Description

* In selection sort
 1. In first iteration, find minimum element and swap with first position
 2. In second iteration, find second minimum element and swap with second position
 3. Do this n-1 times to sort the array

* Time Complexity: O(n2)

-> Selection sort is generally used for sorting files with very large
    objects (records) and small keys.
-> It is simple and easy to implement.
-> It can be used for small data sets.

C/C++

/* C program of selection sort */
//Save it as SelectionSort.c

#include<stdio.h>
int main()
{
    int i,n;

    printf("Enter the size of array : ");
    scanf("%d",&n);

    int arr[n];

    printf("\nEnter element : ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    
    
    //Calling function to sort array
    
    selectionSort(arr,n);

    
    //Finally printing the sorted array
    
    printf("\nThe Sorted array is : ");
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

void selectionSort(int arr[], int n){

    int i, j, minIndex;

    for(i=0;i<n-1;i++){
        
        minIndex = i;

        for(j=(i+1);j<n;j++){
            
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        swap(&arr[i],&arr[minIndex]);
    }
}


//Function to swap number
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
Input:
Enter the size of array : 7

Enter element : 23
56
54
83
29
5
63

Output:
The Sorted array is : 5 23 29 54 56 63 83

Java

/* Java program of selection sort */
//Save it as SelectionSort.java

import java.io.*;
import java.util.Scanner;

public class SelectionSort {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        int i,n;
        
        System.out.println("Enter the size of array : ");
        n = scanner.nextInt();
        
        int arr[] = new int[n];
        
        System.out.println("Enter element : ");
        for(i=0;i<n;i++)
        {
            arr[i] = scanner.nextInt();
        }
        
        
        //Calling function to sort array        
        selectionSort(arr,n);
        
        System.out.println("\nThe Sorted array is : ");
        for(i=0;i<n;i++)
        {
            System.out.print(arr[i]+ " ");
        }
    }

    private static void selectionSort(int[] arr, int n) {
        
        int i, j, minIndex;
        
        for(i=0;i<n-1;i++) {
            minIndex = i;
            
            for(j=(i+1);j<n;j++) {
                if(arr[j]<arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            int temp = arr[i];
            arr[i]  = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
Input:
Enter the size of array : 
5
Enter element : 
23
45
62
82
6

Output
The Sorted array is : 
6 23 45 62 82

Related programs

1) Bubble Sort
2) Insertion Sort
3) Program of Merge Sort
4) Quick Sort
Share Me

Leave a Reply