I would like to find the best, average, worst-case complexities of below code.

Its a variant of selection sort. In each pass both min and max is calculated and placed at proper position

def double_selection_sort(arr):
    n = len(arr)
    for i in range(int(n/2)):
        _min, _max = i, n-i-1
        for j in range(i+1, n-i-1):
            if arr[_min] > arr[j]:
                _min = j
            if arr[_max] < arr[j]:
                _max = j
        arr[i], arr[_min] = arr[_min], arr[i]
        arr[n-i-1], arr[_max] = arr[_max], arr[n-i-1]

I think its in the order of O(nlogn).

Thanks in Advance

  • 1
    $\begingroup$ Why you think its O(nlogn)? Where is the log coming from? $\endgroup$ – lox Jun 28 '19 at 13:06
  • $\begingroup$ Wild guess. I don't know $\endgroup$ – Lijo Jose Jun 28 '19 at 13:52

This variant decreases number of main loop passes by factor of 2, but in return loop body uses twice workload.
Since the change is minor, you can simply read complexity from basic selection sort.

The selection sort has this property that number of swaps is at most $n$, finding element to its proper place, so it takes $\mathcal O(n)$ swaps in the worst case. There is no mechanism to ignore swaps or detect sortedness, two loops are passing through every element, so we can simply infer that best case is equal worst case and equal average case.
Two nested loops with arithmetic progression (array elements to be viewed decrease by one each step) $\sum_{i=1}^{n-1}i = \frac{1}{2}(n^2-n)$ are now decreased, giving $\frac{1}{4}(n^2-n)$, so still $\mathcal O(n^2)$ for all cases.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.