Selection Big O

Homework Part 1

Selection Sort

public class SelectionSortDescending {
    public static void selectionSortDescending(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i; // Assume current index holds max value
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIndex]) { // Find max in remaining array
                    maxIndex = j;
                }
            }
            // Swap max element with first element of unsorted part
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {29, 10, 14, 37, 13};
        System.out.println("Original Array:");
        printArray(array);

        selectionSortDescending(array);

        System.out.println("Sorted in Descending Order:");
        printArray(array);
    }
}
SelectionSortDescending.main(null);

Original Array:
29 10 14 37 13 
Sorted in Descending Order:
37 29 14 13 10 

Insertion Sort

public class InsertionSortAscending {
    public static void insertionSortAscending(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Shift elements that are greater than key to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // Insert key at correct position
        }
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};
        System.out.println("Original Array:");
        printArray(array);

        insertionSortAscending(array);

        System.out.println("Sorted in Ascending Order:");
        printArray(array);
    }
}
InsertionSortAscending.main(null);

Original Array:
1 2 5 4 3 6 7 8 9 10 
Sorted in Ascending Order:
1 2 3 4 5 6 7 8 9 10 

Part 2 Time Complexity Exercise

public class SortingTimeComparison {
    public static void selectionSortDescending(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void insertionSortAscending(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void measureSortingTime(int[] arr, boolean isSelectionSort) {
        int[] copy = arr.clone(); // Clone to avoid modifying original array
        long startTime = System.nanoTime(); // Start time

        if (isSelectionSort) {
            selectionSortDescending(copy);
        } else {
            insertionSortAscending(copy);
        }

        long endTime = System.nanoTime(); // End time
        long duration = endTime - startTime; // Compute time taken
        System.out.println((isSelectionSort ? "Selection Sort" : "Insertion Sort") +
                           " took " + duration + " nanoseconds.");
    }

    public static void main(String[] args) {
        int[] arrayA = {29, 10, 14, 37, 13};
        int[] arrayB = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};

        System.out.println("Sorting Array A:");
        measureSortingTime(arrayA, true);  // Selection Sort
        measureSortingTime(arrayA, false); // Insertion Sort

        System.out.println("\nSorting Array B:");
        measureSortingTime(arrayB, true);  // Selection Sort
        measureSortingTime(arrayB, false); // Insertion Sort
    }
}
SortingTimeComparison.main(null);

Sorting Array A:
Selection Sort took 1333 nanoseconds.
Insertion Sort took 1000 nanoseconds.

Sorting Array B:
Selection Sort took 2333 nanoseconds.
Insertion Sort took 1042 nanoseconds.

Which algorithm performed better for Array A? Why?

Selection Sort will likely perform better for Array A. This is because it makes fewer swaps and is designed for smaller unsorted portions. Insertion Sort requires more shifts, especially since the array is randomly ordered.

Which algorithm performed better for Array B? Why?

Insertion Sort will perform better for Array B. The array is nearly sorted, so Insertion Sort can insert elements into their correct positions with fewer operations. Selection Sort, on the other hand, makes unnecessary comparisons even when elements are already sorted.

When is it best to use each sorting algorithm?

Selection Sort is ideal for small datasets or cases where memory swaps are more expensive. Insertion Sort is best used when the array is partially sorted or when working with smaller datasets where the number of comparisons will be minimal.

Time Complexity Analysis

Algorithm	Best Case	Worst Case	Average Case
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)

• Selection Sort has O(n²) time complexity in all cases because it always makes a fixed number of comparisons, regardless of the initial state of the array.
• Insertion Sort is O(n) in the best case when the array is already sorted, but has O(n²) in the worst and average cases, when the array is unordered or partially sorted.