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++;
}
}
}
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.