Search code examples
javaselection-sort

Trouble with creating a Selection Sorter counting swaps and comparisons


I am having trouble trying to figure out how many swaps and comparisons for an int array using a Selection Sort in Java. I am confused on where in the loops the swap and comparisons count. Any guidance would be greatly appreciated.

    public class IntSelectionSorter {

public static int count = 0;
public static int count2 = 0;

public static void selectionSort(int[] array)
{
    int startScan;
    int index;
    int minIndex;
    int minValue;

    for (startScan = 0; startScan < (array.length - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];

        for (index = startScan + 1; index < array.length; index++)
        {
            count2++;
            if (array[index] < minValue)
            {
                minValue = array[index];
                count++;
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        count++;
        array[startScan] = minValue;
        count++;
    }
}

}


Solution

  • count2 seems to be right. count should be changed as follows:

    for (startScan = 0; startScan < (array.length - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];
    
        for (index = startScan + 1; index < array.length; index++)
        {
            count2++;
            if (array[index] < minValue)
            {
                minValue = array[index];
                // count++; delete this
                minIndex = index;
            }
        }
        if (minIndex != startScan) {
            array[minIndex] = array[startScan];
            count++;
            array[startScan] = minValue;
        }
    }
    

    basically, increment count only when there's is a need to swap, i.e. when there's another number in the array after startScan which is smaller than the value at startScan.