Answer to Question #191627 in Java | JSP | JSF for Haider

Question

Write a function to sort array elements using Selection sort in Descending order .also Compute the best case and worst case time complexity of selection sort.

Answer 1

import java.util.Arrays;

public class Main {
    public static void selectionSort(int[] array) {
        int max;
        int tmp;
        for (int i = 0; i < array.length; i++) {
            max = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[max] < array[j]) {
                    max = j;
                }
            }
            tmp = array[i];
            array[i] = array[max];
            array[max] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 5, 2, 4, 8, 3, 5, 1, 7, 0, 8};
        System.out.println(Arrays.toString(array));
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }
}

The best and worst time complexity will have complexity O(n^2) since in both cases the number of iterations will be equal to the sum of 1 + 2 + 3 ... (n-3) + (n-2) + (n-1), which is an arithmetic progression that equals ((1 + (n - 1)) / 2) * (n - 1) = (n^2 - n) / 2 = O(n^2).