Quick Sort algorithm

[WalidKhan]

I'm newbie to algorithms and also was working upon developing a Quick Sort algorithm with such a duplex partition to ensure that it works quickly even on sequences with many equal components. My approach was as follows:

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
    #use partition3
    m1,m2 = partition3(a, l, r)
    randomized_quick_sort(a, l, m1 - 1);
    randomized_quick_sort(a, m2 + 1, r);

def partition3(a, l, r):
    x, j, t = a[l], l, r
    for i in range(l + 1, t+1):
        if a[i] < x:
            j += 1
            a[i], a[j] = a[j], a[i]
        elif a[i]>x:
            a[i],a[t]=a[t],a[i]
            i-=1
            t-=1
    a[l], a[j] = a[j], a[l]
    return j,t

It doesn't provide properly sorted lists. after following through this article I discovered the right partition code implementation.

def partition3(a, l, r):
    x, j, t = a[l], l, r
    i = j
    while i <= t :
        if a[i] < x:
            a[j], a[i] = a[i], a[j]
            j += 1
        elif a[i] > x:
            a[t], a[i] = a[i], a[t]
            t -= 1
            i -= 1 # remain in the same i in this case
        i += 1
    return j,t

Could you please clarify why the wrong partition implementation failed? Thank you in advance.

Edited November 16, 2023 by Phi for All
commercial links removed by moderator

[Sensei]

General advice: have you tried using a debugger?

There are even Python online debuggers such as:

https://www.onlinegdb.com/online_python_debugger