Implementing 3-way quicksort

Question

I'm a new to algorithms and I'm confused as to where are the errors in my code that I'm writing as an assignment. I'm trying to implement a quicksort algorithm in Python 3 that deals with equal values in the array.

Here's a quicksort function (a stands for the array):

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

And here's my partition function:

def partition3(a, l, r):
    x, j, t = a[l], l, r
    for i in range(l + 1, r + 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]
            t -=1
        else:
            j +=1
    a[l], a[j] = a[j], a[l]
    return j, t

Xl

I would recommend replacing "3-way" with "stable" in the title, or removing it entirely. All sorts are fundamentally less, equal, greater. Some sorting algorithms maintain element order when elements are equal, which are called "stable" sort implementations. 3-way makes me think of 3-way diffing or sorting 3 separate lists in a more efficient implementation than concatenating the 3 lists into one list and sorting that. – Siffre

@IceArdor: I'm pretty sure Elen is referring to 3-way partitioning (the "Dutch national flag problem"). From Wikipedia: "In particular, variants of the quicksort algorithm that must be robust to repeated elements need a three-way partitioning function that groups items less than a given key (red), equal to the key (white) and greater than the key (blue)." – Pl

Answer 1

You should rectify your partition function:

Here is a working example :

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

Acuate

Thank you so very much! I screwed partitioning alright, now I see it clearly. – Xl

Answer 2

Here is a dead simple quicksort implementation in python. While it is still nlogn there are a bunch of performance optimizations that can be made. For example the partitioning into less,equal,greater can be made in a single pass instead of 3 passes of the array.

def qsort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[0]
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return qsort(less) + equal + qsort(greater)

To make that partition happen in one pass of the array, make a helper function like follows:

def partition(arr, pivot):
    less, equal, greater = [], [], []
    for val in arr:
        if val  < pivot: less.append(val)
        if val == pivot: equal.append(val)
        if val  > pivot: greater.append(val)
    return less, equal, greater

def qsort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[0]
    less, equal, greater = partition(arr, pivot)
    return qsort(less) + equal + qsort(greater)

Recha

While your code is a readable implementation of the quick sort algorithm, its not an in-place sort and it returns a new list not the original one. – Acuate

You're entirely right! And after implementing the (simpler and more elegant) case of returning a new list the case of mutating the original list can be accomplished easier. If you come from a functional programming background though, mutating lists is ugly and should only be done when the performance optimization is necessary. – Recha

Thank you very much @Recha for a really apprehensive and fine-looking solution (that is a bit beyond me at the time)! However, I do need to stay within the function that was provided for me, that's why I was asking to help me find errors. – Xl

What @Recha is trying to say here is you can't understand a more complicated solution without understanding the simpler solution first. Once you understand the immutable implementation, it will be easier to figure out what's wrong with the in-place (mutable) implementation. – Siffre

Answer 3

Another implementation with for loop

def partition3(a, l, r):
    x = a[l]
    m1 = l
    m2 = l
    i = m1
    for i in range(l + 1, r + 1):
        if a[i] < x:
            a[i], a[m1] = a[m1], a[i]
            a[i], a[m2+1] = a[m2+1], a[i]
            m1 += 1
            m2 += 1
        elif a[i] == x:
            a[i], a[m2+1] = a[m2+1], a[i]
            m2 += 1
    return m1, m2

Pavla