Java Selection Sort

Question

I am having issues getting my sort to check every index. It skips the 3rd indices for j as in it goes i[0], j[2], to i[0], j[4] I don't know why it is doing that?. Also, I am having trouble with my numbers actually be swapped. Does anybody know where my error is?

static void selectionSort(int[] arr) {
    final long startTime = System.nanoTime(); // starts timer
    System.out.println("Selection Sort");
    //************** Code For Sorting *****************//
    //*************************************************//
    int counter = 0;
    int first = 0;
    int second = 0;
    
    // Copies unsorted array to new array
    //int[] sorted = Arrays.copyOf(arr, arr.length);
    
    // sorts unsorted array for comparison later on
    //Arrays.sort(sorted);
    
    // comparing the first index value to
    // the rest of the values in the array
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;

        // representing the next index value 
        // to the original and comparing it
        for (int j = 1; j < arr.length - 1; j++) {
            int nextIndex = j;

            if (arr[minIndex] < arr[nextIndex]) {
                System.out.println("i: " + i);
                System.out.println("j: " + j);
                System.out.println("Checking next index");
            }
            if (arr[minIndex] > arr[nextIndex]) {
                System.out.println("i: " + i);
                System.out.println("j: " + j);
                //counter = j; // getting array index
                first = arr[minIndex];
                second = arr[nextIndex];
                minIndex = second;
                arr[minIndex] = second;
                System.out.println("first:" + first);
                System.out.println("second:" + second);
                System.out.println("minIndex:" + minIndex);
                System.out.println("arr[minIndex]:" + arr[minIndex]);
                System.out.println("Possible lowest unsorted value");
            }
            //Swap here
            if (arr[arr.length - 1] == arr[j]) {
                arr[0] = second;
                arr[counter] = first;
                counter = 0;
                //minIndex= i+1;
            }
        }
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + ", ");
        }
        System.out.println();
    }
}

Answer 1

The first mistake you've made is within your nested for loop. the starting index (j) for the inner loop should always start at i + 1 (one place ahead of the indexer i) for each iteration of the outer for loop not j = 1 as you've done.

Second, by having the condition j < arr.length-1 you'll always exclude the last element within the array.

change this:

for(int j = 1; j < arr.length-1; j++)

to this:

for(int j = i + 1; j < arr.length; j++)

Moving on, there seems to be several problems with your algorithm including your swap functionality so, let's start again.

Selection sort is an in-place comparison-based algorithm in which the array is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire array.

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

with that in mind, now we can start the algorithm.

public static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length-1; i++){
        int minIndex = i;  // smallest element index
        for(int j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[i]){  // find smallest element
                if(arr[j] < arr[minIndex])
                minIndex = j; // update smallest element index
            }
        }

        if(i != minIndex){  // swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    // print the result
    Arrays.stream(arr).forEach(System.out::println); 
}

as a side note, Selection sort complexities are of Ο(N2), where N is the number of elements within the array.

Answer 2

The algorithm of the selection sort looks as follows:

public static void selectionSort(int[] arr) {
    // iterate over all subsets of the array
    // (0-last, 1-last, 2-last, 3-last, ...)
    for (int i = 0; i < arr.length; i++) {
        // assume the min is
        // the first element
        int min = arr[i];
        // index of the
        // min element
        int min_i = i;
        // check the elements
        // after i to find
        // the smallest
        for (int j = i + 1; j < arr.length; j++) {
            // if this element
            // is less, then it
            // is the new min
            if (arr[j] < min) {
                min = arr[j];
                min_i = j;
            }
        }
        // if min element is not
        // equal to the current
        // one, then swap them
        if (i != min_i) {
            int temp = arr[i];
            arr[i] = arr[min_i];
            arr[min_i] = temp;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {5, 34, 1, 15, 3, 8, 9, 2, 7, 6, 43, 4};
    selectionSort(arr);
    System.out.println(Arrays.toString(arr));
    // [1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 34, 43]
}