Java Selection Sort

问题:

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;
       //int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array
        //Arrays.sort(sorted); // sorts unsorted array for compairison later on
        for( int i = 0; i < arr.length-1; i++) // comparing the first index value to the rest of the values in the array
        {
            int minIndex = i;

            for(int j = 1; j < arr.length-1; j++) // representing the next index value to the original and comparing it
            {
                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();
        }

回答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.