I am trying to create my own program to do selection sort on an array of integers. I have come up with the following program, which works on some arrays, but not on others, such as this one. I have been trying to trace the problem, and I think it might have to do with where I am placing the min = num [x]; line. However, I am not sure where I should move it in order to fix the problem. Does anyone have any suggestions? Thank you.

p.s. I have provided some of my test cases and their results at the bottom.

        int [] num = {4, 9, 7, 6, 0, 1, 3, 5, 8, 2};

        int min = num [0];
        int temp;
        int index = 0;

        for (int x = 0; x < num.length; x   )
        {
            min = num [x];
            temp = num [x];
            for (int y = x   1; y < num.length; y   )
            {
                if (num [y] < min)
                {
                    min = num [y];
                    index = y;
                }
            }
            num [x] = min;
            num [index] = temp;
            min = num [x];
        }

Output Test Cases:

array: {4, 9, 7, 6, 0, 1, 3, 5, 8, 2}
result: [0, 1, 2, 3, 4, 4, 5, 7, 8, 8]

array: {7, 5, 8, 9, 1, 6, 3, 0, 2, 4}
result: [0, 1, 2, 3, 4, 5, 6, 7, 7, 8]

array: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
result: [0, 1, 2, 3, 4, 9, 6, 7, 8, 9]

CodePudding user response：

there is one big problem and multiple small ones, see comments:

int [] num = {4, 9, 7, 6, 0, 1, 3, 5, 8, 2};

int min = num [0]; // you don't need this variable and assignment here, you can declare it inside loop
int temp; // the same for this variable
int index = 0; // the same here

for (int x = 0; x < num.length; x   )
{
    min = num [x];
    temp = num [x];
    // here you need to re-initialize index variable to some value, otherwise it could be some garbage from previous iterations
    for (int y = x   1; y < num.length; y   )
    {
        if (num [y] < min)
        {
            min = num [y];
            index = y;
        }
    }
    num [x] = min;
    num [index] = temp;
    min = num [x]; // this assignment does not make sense as you're overwriting it next iteration
}

you can simplify code a little bit:

for (int x = 0; x < num.length; x  ) {
    int index = x;
    for (int y = x   1; y < num.length; y  )
        if (num[y] < num[index])
            index = y;
    int temp = num[x];
    num[x] = num[index];
    num[index] = temp;
}

CodePudding user response：

There are a few problems with the code you wrote:

• The outermost loop, the one with index x, should iterate from 0 to num.length - 1, since the innermost loop starts from x 1. If you iterated till num.length - 1 included, then, during the last iteration of the outermost loop, y would correspond to num.length, which is not an actual element and in fact the innermost loop won't even start. This would be a useless iteration.

• The if statement in the innermost loop needs only to save the index of the new smallest element among the ones left to sort (from x to num.length-1). You don't need to save also the value.

• Your swap section has a final extra assignment that does nothing useful. Furthermore, it would be better to keep all the assignments in one specific point of your code for better readability. Also, having three temp vars (min, temp and index) is more than what you actually need. You only need 2 temp vars (minIndex and temp) where the first one stores the index of the new smallest value found while the second one is used during the value swap between the x-th element and the one in position minIndex.

Here is the fixed code with the explanation of your errors and the algorithm logic.

public static void main(String[] args) {
    int[] num = {4, 9, 7, 6, 0, 1, 3, 5, 8, 2};

    int minIndex, temp;

    //Your outermost loop should iterate till num.length - 1, since the innermost loop looks for any smaller element after x.
    //The outermost loop is used to guarantee that at each iteration, the x-th element contains the smallest value among the ones left to sort.
    for (int x = 0; x < num.length - 1; x  ) {

        //Assuming the x-th element is the smallest among the ones left to sort (from x to num.lenght-1)
        minIndex = x;

        //Looking for a smaller element than the x-th after the x position
        for (int y = x   1; y < num.length; y  ) {

            //You only need to save the index of the new smallest element in minIndex.
            //Once you've completed the innermost loop, then you'll swap the x-th element with the element in position minIndex
            if (num[y] < num[minIndex]) {
                minIndex = y;
            }
        }

        //Swapping the x-th element with the minIndex-th element after the innermost loop has completed
        temp = num[x];
        num[x] = num[minIndex];
        num[minIndex] = temp;
    }

    System.out.println(Arrays.toString(num));
}