Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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
like image 251
Elen Avatar asked May 01 '16 22:05

Elen


People also ask

What is 3 way partitioning for Quicksort?

3 way quick sort basically partitions the array in 3 parts. First part is lesser than the pivot , Second part is equal to pivot and third part is greater than pivot.It is linear-time partition algorithm.

Is 3 way quicksort stable?

No, 3-way quick sort is also not stable. For instance, if arr[i]>pivot and arr[j]<pivot , then these values will be swapped, and the next comparison will be with arr[i+1] and arr[j-1] .

How is an Quicksort algorithm implemented?

The key process in quickSort is a partition(). The target of partitions is, given an array and an element x of an array as the pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.

Is quick sort difficult to implement?

2.3 Quicksort. Quicksort is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and is substantially faster than any other sorting method in typical applications.


2 Answers

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
like image 103
nino_701 Avatar answered Oct 08 '22 20:10

nino_701


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)
like image 26
gnicholas Avatar answered Oct 08 '22 22:10

gnicholas