Quick Select in O(1) using tail recursion

Question

I was doing a ZTM course there he said that Quick Select algo at worst case can be O(1) Space complexity using tail recursion as it only makes one recursive calls.

His Code was

const quickSelect = function (nums, left, right, indexToFind) {
  const partitionIndex = getPartition(nums, left, right);

  if (partitionIndex === indexToFind) {
    return nums[partitionIndex];
  } else if (indexToFind < partitionIndex) {
    return quickSelect(nums, left, partitionIndex - 1, indexToFind);
  } else {
    return quickSelect(nums, partitionIndex + 1, right, indexToFind);
  }
};

And here is the optimized version of Quick Sort from GFG article it looks like quickSelect and one recursive call each time. Code:

def quickSort(arr, low, high)
{
    while (low < high):
        ''' pi is partitioning index, arr[p] is now
           at right place '''
        pi = partition(arr, low, high);
 
        # If left part is smaller, then recur for left
        # part and handle right part iteratively
        if (pi - low < high - pi):
            quickSort(arr, low, pi - 1);
            low = pi + 1;
         
        # Else recur for right part
        else:
            quickSort(arr, pi + 1, high);
            high = pi - 1;
}

Why can't this be O(1) Space complexity then using Tail rec?

Answer 1

Iterative version of quick select using Lomuto partition scheme. I don't know if python optimization handles tail recursion.

def quickselect(a, k):
    lo = 0
    hi = len(a)-1
    while (lo < hi):
        p = a[hi];              # Lomuto partition
        i = lo;
        for j in range(lo, hi):
            if (a[j] < p):
                a[i],a[j] = a[j],a[i]
                i += 1
        a[i],a[hi] = a[hi],a[i]
        if (k == i):            # if pivot == kth element, return it
            return a[k]
        if (k < i):             # loop on partition with kth element
            hi = i - 1
        else:
            lo = i + 1
    return a[k]                 # sorted to kth elemement, return it

Iterative version of quick select using Hoare partition scheme, it has to loop until lo == hi, since the pivot and values equal to pivot can end up anywhere after a partition step. However, it is faster than Lomuto partition scheme (at least with Python).

def quickselect(a, k):
    lo = 0
    hi = len(a)-1
    while (lo < hi):
        p = a[(lo + hi) // 2]   # Hoare partition
        i = lo - 1
        j = hi + 1
        while(1):
            while(1):
                i += 1
                if(a[i] >= p):
                    break
            while(1):
                j -= 1
                if(a[j] <= p):
                    break
            if(i >= j):
                break
            a[i],a[j] = a[j],a[i]
        if (k <= j):            # loop on partition with kth element
            hi = j
        else:
            lo = j + 1
    return a[k]                 # sorted to kth elemement, return it