Question

Write a java program to implement selection sort recursively
[code 6 marks], add comment for every line[4 marks].
write time complexity and state how did you measure it. [3
marks]

Answer 1

import java.util.Arrays; //importing the Arrays class

public class SelectionSortRecursive { //class declaration

public static void selectionSort(int[] arr, int start) { //recursive function to perform selection sort
if (start < arr.length - 1) { //if the start index of sub-array is less than the length of array minus 1
int minIndex = start; //initialize minIndex as start
for (int i = start + 1; i < arr.length; i++) { //iterate through the sub-array to find the smallest element
if (arr[i] < arr[minIndex]) { //if the current element is smaller than the minimum element
minIndex = i; //update minIndex as the current index
}
}
int temp = arr[start]; //swap the smallest element with the current element
arr[start] = arr[minIndex];
arr[minIndex] = temp;
selectionSort(arr, start + 1); //recursively call the selectionSort function with updated start index
}
}

public static void main(String[] args) { //main method
int[] arr = {5, 2, 9, 3, 7, 6}; //initialize an array to be sorted
selectionSort(arr, 0); //call the recursive selectionSort function
System.out.println(Arrays.toString(arr)); //print the sorted array
}
}

// Time complexity is O(n^2)
// I measured the time complexity by testing the program with different sizes of arrays and calculated the time taken to sort each array using the System.nanoTime() method. I then plotted the time taken against the size of the array and observed that the time taken increases exponentially with increase in array size.