CODEWITHSUNDEEP
javasorting
tjg92
tjg92

Reputation: 197

Count the Number of Swaps in Selection Sort

I've read through all the discussions trying to find an answer but none of the answers have worked for me so I'm trying it this way. 

public static int SelectionSort(long[] num)
{
    int i, j, first;
    long temp;
    int swap = 0;
    int pass = 0;
    int count = 0;
    boolean Mini = false;

    for (i = num.length - 1; i > 0; i--)
    {
        for(int k = 0; k < num.length; k++)
        {
            System.out.println(" k = " + k
            + "   \t X[i] = " + num[k] + " swap count: " + swap);
        }
        System.out.println("");
        first = 0;   //initialize to subscript of first element
        for(j = 1; j <= i; j ++)   //locate smallest element between positions 1 and i.
        {
            if(num[j] < num[first])
            {
                first = j;
                //Mini = true;
            }
        }

        //if(Mini){
            //  swap++;
        //}
        temp = num[first];   //swap smallest found with element in position i.
        num[first] = num[i];
        num[i] = temp;
    }
    return swap;
}

Using a simple array as my test case:

long[] X = {1, 4, 3, 2, 5};

The number of swaps should only equate to 1 because it's swapping the first and last elements only. However, it isn't working. While I know my if condition doesn't work, I can't think of what would. I can't seem to work the logic that it increments a swap when items are actually swapped.

Upvotes: 0

Views: 8693

Answers (2)

Mureinik
Mureinik

Reputation: 311978

Why not increment the counter when you actually perform a swap?

//swap smallest found with element in position i.
swap++
temp = num[first];
num[first] = num[i];
num[i] = temp;

EDIT:
Good point in the comment. The current code still performs a superfluous swap if the array is sorted (i.e., first and i are the same):

if (first != i) { 
    swap++
    temp = num[first];
    num[first] = num[i];
    num[i] = temp;
}

Upvotes: 2

Preli
Preli

Reputation: 3031

With your implementation you will always have n swaps (where n is the number of elements in your array).

What I think you want is to only perform a swap when it actually makes a difference ... so when "first" and "i" have different values. Otherwise you switch the element with itself.

  if (first != i) {
    temp = num[first];
    num[first] = num[i];
    num[i] = temp; 
    swapp++;
  }

Upvotes: 1

Related Questions