Selection Sort

one swap per iteration

Selection sort main, har pass pe array ka sabse chhota element dhundho aur usko unsorted part ke starting element ke sath swap kar do, yeh process repeat hoti rehti hai jab tak array sorted na ho jaye.

Selection Sort is a comparison-based sorting algorithm.

It sorts an array by repeatedly selecting the smallest (or largest)* element from the unsorted portion and swapping it with the first unsorted element.

alt text

Steps

First we find the smallest element and swap it with the first element. This way we get the smallest element at its correct position.
Then we find the smallest among remaining elements (or second smallest) and move it to its correct position by swapping.
We keep doing this until we get all elements moved to correct position.

code:

public class main {    
    public static void main (String arg[]){
        int arr[] = {1,2,3,4,5,6};
        for (int i=0; i<arr.length-i; i++){
            int smallest = i;
            for ( int j = i + 1; j < arr.length; j++){
                if (arr[smallest]>arr[j]){
                    smallest = j;
                }
            }
           int temp = arr[smallest];
           arr[smallest]  = arr[i];
           arr [i]=temp;
           }
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

user input

import java.util.Scanner;

public class Main {
    public static void main(String arg[]) {
        Scanner scanner = new Scanner(System.in);

        // Ask the user for the number of elements
        System.out.print("Enter the number of elements in the array: ");
        int n = scanner.nextInt();
        
        // Create an array of size n
        int arr[] = new int[n];

        // Get user input for the array elements
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        // Selection sort implementation
        for (int i = 0; i < arr.length - 1; i++) {
            int smallest = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[smallest] > arr[j]) {
                    smallest = j;
                }
            }
            // Swap the found smallest element with the first element
            int temp = arr[smallest];
            arr[smallest] = arr[i];
            arr[i] = temp;
        }

        // Print the sorted array
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        // Close the scanner
        scanner.close();
    }
}

Time and space complexity

alt text