SelectionSort variation not working

Question

I have to implement a Selection Sort in Java according to these parameters:

Implement a variation to the SelectionSort that locates both the smallest and largest elements while scanning the list and positions them at the beginning and the end of the list, respectively. On pass number one, elements x0,...,xn-1 are scanned; on pass number two, elements x1,...,xn-2 are scanned; and so on.

I am passing the method an array of size 32, and when I print the array it is not sorted. What's the matter with my code?

static void selectionSort() {
    scramble();
    int smallIndex = 0;  //index of smallest to test
    int largeIndex = array.length - 1;  //index of largest to test
    int small = 0;  //smallest
    int large;  //largest
    int smallLimit = 0;  //starts from here
    int largeLimit = array.length - 1;  //ends here
    int store;  //temp stored here
    int store2;

    for(int i = 0; i < array.length/2; i++) {  //TODO not working...
        small = array[smallLimit];
        large = array[largeLimit];
        for(int j = smallLimit; j <= largeLimit; j++) {
            if(array[j] < small) {
                smallIndex = j;
                small = array[j];
            }
            else if(array[j] > large) {
                largeIndex = j;
                large = array[j];
            }
        }
        store = array[smallLimit];
        store2 = array[smallIndex];
        array[smallLimit] = store2;
        array[smallIndex] = store;
        store = array[largeLimit];
        array[largeLimit] = array[largeIndex];
        array[largeIndex] = store;
        smallLimit++;
        largeLimit--;
    }
    print();    
}

Answer 1

Like @Joni, clearly pointed out, there is big caveat with swapping two elements twice during a traversal of the array. Since you have to implement the sorting algorithm in-place, you need to take into account the positions of the elements to be swapped as it happens in succession.

Another limiting case that you need to see is when there are just three elements left i.e. the last iteration of the for loop. This is how I would go about it:

    store = array[smallLimit];
    store2 = array[smallIndex];
    array[smallLimit] = small;
    array[smallIndex] = store;
    smallLimit++;
    //No problem with swapping the first two elements
    store = array[largeLimit];

    //However the first swap might cause the other elements to shift
    //So we do this check
    if((array[largeIndex] == large))
     {array[largeLimit] = array[largeIndex];
      array[largeIndex] = store;
      largeLimit--;
     }

    //Just a limiting case, where amongst the last three elements, first swap happens. 
    //The smallest element is in place, just take care of the other two elements.
    if(largeLimit - smallLimit == 1){
        if(array[largeLimit] != large){
            array[smallLimit] = array[largeLimit];
            array[largeLimit] = large;
            largeLimit--;
        }
    }

Working DEMO for the snippet mentioned above, building upon your code. Hope it gets you started in the right direction.

Answer 2

Think about the extreme cases: what happens when the largest or smallest item is found at smallLimit or largeLimit. When that happens you have two problems:

1. largeIndex and smallIndex are not set. They maintain their values from a previous iteration.
2. Swapping the smallest item to its correct place moves the largest item. The second swap moves the smallest item where the largest should go, and the largest ends up in a random location. Step through the code on paper or in a debugger if you find this hard to visualize.

These problems are easy to fix. You could have avoided the problem following a few guidelines:

• Use fewer moving parts. You can always get the value of small using smallIndex, if you just used smallIndex there would be no danger of different variables falling out of step.
• Declare the variables in the smallest possible scope. If smallIndex was declared in the loop body and not outside the compiler would have told you there's a chance it was not set before the swap.
• Destructive updates like the first swap here can always make a previous calculation obsolete. When you can't avoid this from happening, look for ways two updates can step on each other's toes.