Selection Sort but just one switch each iteration-CodePudding

I have written a Selection Sort Algorithm which consists of two for loops. As of now, the inner loop may swap numbers several times before incrementing the outer loop. However, my goal now is to have the inner loop swap numbers exactly once and then go back to the outer for loop and repeat this until the array is sorted. I already tried it with a break statement, but then it doesn't sort the whole thing correctly.

    private static void selectionSort(int[] array) {        //Array wird sortiert
        
        for(int i = 0; i < array.length - 1; i  ) {
            
            for(int a = i   1; a < array.length; a  ) {
                
                if(array[i] > array[a]) {
                    
                    int temporaer = array[i];
                    array[i] = array[a];
                    array[a] = temporaer;
                    break;
                    
                }
                
            }
                    
        }
        
    }

Can you guys help me?

CodePudding user response：

Selection sort is supposed to work by finding the ith smallest element on the ith iteration of the outer loop, and then swapping that element into position i. After the outer loop finishes iteration i, the whole array should be sorted from position 0 to i. The inner loop is there to find that ith smallest element by iterating over the whole unsorted portion of the array and finding the smallest element therein. So altogether it should look something like this:

    private static void selectionSort(int[] array) {        //Array wird sortiert
        
        for(int i = 0; i < array.length - 1; i  ) {
            // das Minimum finden
            int min = array[i];
            int minIdx = i;
            for(int a = i   1; a < array.length; a  ) {
                if(array[a] < min) {
                    min = array[a];
                    minIdx = a;  
                }   
            }
            // Austauschen
            int temp = array[i];
            array[i] = min;
            array[minIdx] = temp;          
        } 
    }

Without the break statement, you were effectively still getting the smallest element into position i, you just don't have to perform so many swaps to do so. Just use local variables to track what the min is/where you found it, and make one swap at the end.