Finding both the minimum and maximum in a array with each pass in Selection Sort

775 views Asked by At

I am working on Java based Array sorting techniques and stumbled across an enhancement in Selection Sort

The documented approach of Selection Sort talks about finding the largest or smallest object in each pass

The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

I am wondering that its possible to find both the largest & smallest object in a single pass by checking both the conditions

public static void mySort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length - i; j++) {
            //This will make sure smallest element will come first
            if (arr[i] > arr[j]) {
                swap(arr, i, j);
            }
            // This will make sure largest element will come last
            if (arr[j] > arr[arr.length - 1 - i]) {
                swap(arr, arr.length - 1 - i, j);
             // This will ensure that if a smaller element existed at the ending position and got swapped , we are making sure that it doesn't get mixed
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }
}

Basically what we are doing here is we are sorting from both ends. This will save some time compared to traditional Selection Sort and Can you please provide your feedback on the approach and if anything similar already exists

More details @ my blog post

1

There are 1 answers

2
Peter Lawrey On BEST ANSWER

It is usually the number of comparisons which matters and the number of passes is less but the comparison is the same. Also selection sort is typically used in small sets for it's simplicity, for larger collections a sort with a lower time complexity would be used.

When would you use an optimised O(N^2) sort when you could use an O(N log N) sort? Only when N is small, and you want something simple to cover that. e.g. when I want to compare at most two elements, I use selection sort.