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, 20232 yr by Phi for All
commercial links removed by moderator

General advice: have you tried using a debugger?

There are even Python online debuggers such as:

https://www.onlinegdb.com/online_python_debugger