Selection Sort

Homework Part 1

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[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = 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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

int[] arr1 = {1, 2, 11, 1, 12};
int[] arr2 = {1, 2, 11, 1, 12};
System.out.println("Original array 1: "+Arrays.toString(arr1));
selectionSortDescending(arr1);
System.out.println("Sorted array 1 (descending): "+Arrays.toString(arr1));
System.out.println("\nOriginal array 2: "+Arrays.toString(arr2));
insertionSortAscending(arr2);
System.out.println("Sorted array 2 (ascending): "+Arrays.toString(arr2));

Original array 1: [1, 2, 11, 1, 12]
Sorted array 1 (descending): [12, 11, 2, 1, 1]

Original array 2: [1, 2, 11, 1, 12]
Sorted array 2 (ascending): [1, 1, 2, 11, 12]

Homework Part 2

import java.util.Arrays;


public static long selectionSortDescending(int[] arr) {
    long startTime = System.nanoTime();
    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[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
    long endTime = System.nanoTime();
    return endTime - startTime;
}

public static long insertionSortAscending(int[] arr) {
    long startTime = System.nanoTime();
    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 = j - 1;
        }
        arr[j + 1] = key;
    }
    long endTime = System.nanoTime();
    return endTime - startTime;
}

int[] arrayA = {29, 10, 14, 37, 13};
int[] arrayB = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};
int[] sortedArrayASelection = arrayA.clone();
int[] sortedArrayAInsertion = arrayA.clone();
int[] sortedArrayBSelection = arrayB.clone();
int[] sortedArrayBInsertion = arrayB.clone();


long selectionTimeA = selectionSortDescending(sortedArrayASelection);
long insertionTimeA = insertionSortAscending(sortedArrayAInsertion);
long selectionTimeB = selectionSortDescending(sortedArrayBSelection);
long insertionTimeB = insertionSortAscending(sortedArrayBInsertion);

System.out.println("Original array A: " + Arrays.toString(arrayA));
System.out.println("Selection Sort Array A time: " + selectionTimeA + " nanoseconds");
System.out.println("Insertion Sort Array A time: " + insertionTimeA + " nanoseconds");
System.out.println("Sorted Array A (insertion): " + Arrays.toString(sortedArrayAInsertion));

System.out.println("\nOriginal array B: " + Arrays.toString(arrayB));
System.out.println("Selection Sort Array B time: " + selectionTimeB + " nanoseconds");
System.out.println("Insertion Sort Array B time: " + insertionTimeB + " nanoseconds");
System.out.println("Sorted Array B (insertion): " + Arrays.toString(sortedArrayBInsertion));
   

Original array A: [29, 10, 14, 37, 13]
Selection Sort Array A time: 917 nanoseconds
Insertion Sort Array A time: 750 nanoseconds
Sorted Array A (insertion): [10, 13, 14, 29, 37]

Original array B: [1, 2, 5, 4, 3, 6, 7, 8, 9, 10]
Selection Sort Array B time: 1875 nanoseconds
Insertion Sort Array B time: 833 nanoseconds
Sorted Array B (insertion): [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

For array A, which was a small, unsorted list, both selection and insertion sort took about the same time. There wasn’t a big diffrence becuase the array was so small, and the algorithims don’t have alot of overhead.However, insertion sort was normally a bit faster as it was a smaller array, which is better for inerstion sort. Array B, being mostly sorted, showed that insertion sort is much faster. This is becuase insertion sort is really good at sorting almost sorted lists.

Selection sort is best for small lists or when you don’t want to swap items alot, but it’s slow on nearly sorted lists. Insertion sort is good for small lists and almost sorted lists. It’s faster then selection sort on small lists, and really fast on already sorted or nearly sorted lists.