Why selection best case is not O(n)

Question

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?

Answer 1

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.