1. Sort a given set of n integer elements using Selection Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the brute force method works along with its time complexity analysis: worst case, average case and best case
import java.util.*;
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
Random rand = new Random();
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of elements:");
int n = scan.nextInt();
// Change the value of n as required
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = rand.nextInt(10000); // Generate random numbers between 0 and 99
}
System.out.println("Generated array: " + Arrays.toString(arr));
// Measure the time taken to sort
long startTime = System.nanoTime();
selectionSort(arr);
long endTime = System.nanoTime();
double timeTaken = (endTime - startTime) / 1e9;
System.out.println("Sorted array: " + Arrays.toString(arr));
System.out.println("Time taken to sort: " + timeTaken + " seconds");
}
}
NULL