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]
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.
Sure! Here's a step-by-step guide on how to write a Java program to implement selection sort recursively:
```java
class SelectionSort {
// Function to swap elements in an array
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Recursive function to perform selection sort
public static void selectionSortRecursive(int[] arr, int n) {
// Base case: return when only one element is left
if (n <= 1) {
return;
}
// Find the minimum element in the remaining unsorted portion of the array
int min_idx = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[min_idx]) {
min_idx = i;
}
}
// Swap the minimum element with the first element
swap(arr, min_idx, 0);
// Recursively call selectionSortRecursive() for the remaining n-1 elements
selectionSortRecursive(arr, n - 1);
}
// Print the array
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// Main function to test the program
public static void main(String[] args) {
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
System.out.println("Original array:");
printArray(arr);
// Call the selectionSortRecursive() function
selectionSortRecursive(arr, arr.length);
System.out.println("Sorted array:");
printArray(arr);
}
}
```
Explanation of the code:
- We start by creating a class called "SelectionSort" to encapsulate the selection sort algorithm.
- The `swap` method is a helper function used to swap two elements in an array.
- The `selectionSortRecursive` method is the main recursive function that performs the selection sort algorithm.
- We first check for the base case, which is when there is only one element left in the array.
- We then find the minimum element in the remaining unsorted portion of the array using a simple linear scan.
- We swap the minimum element with the first element to ensure it is in its correct position.
- Finally, we recursively call the `selectionSortRecursive` method for the remaining n-1 elements.
- The `printArray` method is used to print the contents of the array.
- In the `main` method, we create an array with some random values and print the original and sorted arrays.
Time complexity:
The time complexity of the recursive implementation of selection sort is O(n^2). This is because in each recursive call, we find the minimum element in the remaining subarray, which requires a linear scan. Since there are n recursive calls and each call performs a linear scan, the overall time complexity is O(n^2).
To measure the time complexity, you can use a stopwatch or timer to measure the actual running time of the program for different input sizes. Then, by plotting the input size against the running time, you can observe the growth rate and verify that it matches the expected time complexity of O(n^2).