Question

Analyzing Selection Sort Algorithm

The selection sort algorithm works by first finding the smallest value in a list and swapping the first value with it, then finding the second smallest value and swapping the second value with it, continuing until all the values are in order. Implement this algorithm, then determine its growth function, and hence the order of the algorithm. Find how many swaps are made.

Use Java Code to create algorithm

Answer 1

import java.util.Scanner;

public class Sort {
   public static int swapCount = 0;
   public static void swap(int arr[] ,int i,int j) {
       int temp=arr[i];
       arr[i] = arr[j];
       arr[j] =temp;
   }
  
   public static void selectionSort(int a[]){
       int min;
       int n = a.length;
       for(int i=0;i<n-1;i++){
           min=i;
           for(int j=i+1;j<n;j++)if(a[j]<a[min])min=j;
           if(min!=i){
               swapCount++;
               swap(a , i,min);
           }
       }
   }
  
   public static void main(String args[]) {
       int n;
       Scanner scan = new Scanner(System.in);
       System.out.print("Enter size of array: ");
       n = scan.nextInt();
       int arr[] = new int[n];
       System.out.print("Enter elements in array: ");
       for(int i=0;i<n;i++) {
           arr[i] = scan.nextInt();
       }
       selectionSort(arr);
       System.out.println("Number of swaps "+ swapCount);
       scan.close();
   }
  
   /* when i=0 , inner for Loop runs (1 to n-1) n-1 times
   * when i=1 , inner for Loop runs (2 to n-1) n-2 times
   * when i=2 , inner for Loop runs (3 to n-1) n-3 times and so on...........
   * Total run = (n-1) + (n-2) + (n-3) + ..............+ 2 + 1
   * T(n) = n*(n-1)/2
   * T(n) = O(n^2)
   * /
}