CODEWITHSUNDEEP
algorithmsortingtime-complexityselection-sort
nguyenbkcse
nguyenbkcse

Reputation: 559

Why selection best case is not O(n)

I have read many topics which people usually say that Selection sort's complexity in best case is still O(n^2). But I coundn't be convinced by those ideas. For instance, I want to sort the array in ascending order. And this is my algorithm in Java code:

void selectionSort(int[] arr) {
    int min, temp;
    int length = arr.length;
    for (int i = 0; i <= length - 1; i++) {
        //System.out.println(i);
        min = i;
        for (int j = i+1; j < length ; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        } else {
            break;
        }
    }
}

I believe this is O(n) in best case, which is the input arrray is already sorted. One additional thing I added here to the algorithm is to check if (min == i) and break the loop. What do you think? Am I wrong?

Upvotes: 0

Views: 211

Answers (2)

user1196549
user1196549

Reputation:

SelectionSort clearly has an O(N²) time complexity as the loops must be executed in full. The number of comparisons is the triangular number T(N-1) in all cases, while the number of swaps is linear (in the standard version).

Avoiding a swap for an element already in place is probably a bad idea because it is effective with very low probability and executed for nothing in most cases. (Not counting that the break... breaks the algorithm.)

Upvotes: 2

another_CS_guy
another_CS_guy

Reputation: 682

Both loops in selection sort will fully run n times. Lets take example of [1,2,3,4,5]

Outer loop will run 5 times, for each value of array. Then inner loop will check that whether this is minimum value in rest of the array or not.

outer value = 1   -> Inner value 2,3,4,5
outer value = 2   -> Inner value 3,4,5
outer value = 3   -> Inner value 4,5
outer value = 4   -> Inner value 5
outer value = 5   -> Inner value none

Also, in your code, this check is incorrect

 else {
            break;
      }

say array is [1,3,2]. In first outer loop, min ==i, and it will break and wont even move to next values.

Upvotes: 0

Related Questions