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
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.
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] .
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.
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.
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
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With