🔒 Whats wrong with my quick select?

[primal shadow]

    def kthSmallest(arr: list[int], left: int, right: int, k: int) -> int:
      if left == right:
        return left

      pivot = arr[right]
      index = left
      for i in range(left, right):
        if arr[i] < pivot:
          arr[index], arr[i] = arr[i], arr[index]
          index += 1
      arr[index], arr[right] = arr[right], arr[index]

      if index != k:
        # Finds whether the pivot element is in the subarray arr[index, k] where all the elements in it are just as same as arr[index].
        diff = 1 if index < k else -1
        for i in range(index + diff, k + 1, diff):
          if arr[i] != arr[index]:
            index = i
            break
        else:
          

      if index == k:
        return arr[index]

      if index > k:
        return kthSmallest(arr, left, index - 1, k)
      return kthSmallest(arr, index + 1, right, k)

In this code, the quick select algorithm is not working properly
I don't know where's the problem
At 3rd or 4th recursion/iteration, the pivot which is chosen at that iteration is not swapped to it's final sorted position in that array, especially for the below test case.

[[141,105,69,273,681,105,933,417,309],[921,657,945,717,885,57,453,921,897],[681,345,657,177,897,609,465,801,429],[681,993,741,885,105,981,477,249,921],[369,885,945,537,45,861,381,345,417],[849,849,477,513,297,609,561,177,801],[561,417,129,585,621,561,261,153,501],[249,777,969,249,357,393,93,321,573],[525,813,381,909,825,297,681,345,813]]

I checked it against a sorted array, and it fails to put the pivot in it's sorted position around 3rd or 4th iteration as mentioned. Why?

[grizzled citrus]

@primal shadow

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[valid plinth]

      if left == right:
        return left

🤔

that returns the index right, not the element at this index?

[primal shadow]

oops

yeah

changed that

but still, the test case is not satisfying

[hardy oar]

indents look messed up, can you fix it?

otherwise this part doesn't make too much sense

      if index != k:
        diff = 1 if index < k else -1
        for i in range(index + diff, k + 1, diff):
          if arr[i] != arr[index]:
            index = i
            break
        else:   # <--- what happened here
          

      if index == k:
        return arr[index]

      if index > k:
        return kthSmallest(arr, left, index - 1, k)
      return kthSmallest(arr, index + 1, right, k)

beyond that, k never changing in any of the recursive calls seems wrong

  return kthSmallest(arr, left, index - 1, k)
return kthSmallest(arr, index + 1, right, k)

[grizzled citrus]

Python help channel closed for inactivity

This help channel has been closed. Feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.