CODEWITHSUNDEEP
pythonquicksort
Elen
Elen

Reputation: 151

Implementing 3-way quicksort

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

Upvotes: 6

Views: 9898

Answers (3)

Kim Hoan Pham
Kim Hoan Pham

Reputation: 11

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

Upvotes: 1

nino_701
nino_701

Reputation: 692

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

Upvotes: 15

gnicholas
gnicholas

Reputation: 2077

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)

Upvotes: 10

Related Questions