Selection sort implementation, I am stuck at calculating time complexity for number of swaps

Question

static int count = 0;
for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
            swap(arr, i, j);
            count++;
        }
    }
}

Is this the correct implementation for selection sort? I am not getting O(n-1) complexity for swaps with this implementation.

Answer 1

Is this the correct implementation for selection sort?

It depends, logically what you are doing is correct. It sort using "find the max/min value in the array". But, in Selection Sort, usually you didn't need more than one swap in one iteration. You just save the max/min value in the array, then at the end you swap it with the i-th element

I am not getting O(n-1) complexity for swaps

did you mean n-1 times of swap? yes, it happen because you swap every times find a larger value not only on the largest value. You can try to rewrite your code like this:

static int count=0;
static int maximum=0;
for(int i=0;i<arr.length-1;i++){
    maximum = i;
    for(int j=i+1;j<arr.length;j++){
        if(arr[j] > arr[maximum]){
            maximum = j;
        }
    }
    swap(arr[maximum],arr[i]);
    count++;
}

Also, if you want to exact n-1 times swap, your iteration for i should changed too.