CODEWITHSUNDEEP
pythonalgorithmsorting
Matt
Matt

Reputation: 161

Bucket sort faster than Quicksort

I've made a program in Python that sorts a randomly created list containing 5000 numbers with different algorithms and compares times.
Quicksort is generally slower than Bucket sort, why?
I thought Quicksort is faster.

Here is my program:

Quicksort

def quicksort(seq):
    wall = 0
    pivot = seq[-1]
    for index, num in enumerate(seq):
        if num < pivot:
            seq[wall], seq[index] = seq[index], seq[wall]
            wall += 1
    seq[wall], seq[-1] = seq[-1], seq[wall]
    left = seq[:wall]
    if len(left) > 0:
        left = quicksort(left)
    right = seq[(wall + 1):]
    if len(right) > 0:
        right = quicksort(right)
    return left + [pivot] + right

Bucket sort

def bucket_sort(seq):
    biggest = 0
    for number in seq:
        if number > biggest:
            biggest = number
    buckets = []
    buckets.append([]) * (biggest / 10 + 1)
    for number in seq:
        buckets[number / 10].append(number)
    for index, bucket in enumerate(buckets):
        #Using quicksort to sort individual buckets
        buckets[index] = quicksort(bucket)
    new_list = [number for number in bucket for bucket in buckets]
    return new_list

Upvotes: 3

Views: 9225

Answers (3)

Rakesh Kumar
Rakesh Kumar

Reputation: 5

https://stackoverflow.com/posts/25690572/revisions

As the code is given here for quicksort, It uses two new lists. i.e., lo & hi

The Speciality of QuickSort is not using new MemorySpace

So the answered code is a good solution but it does break the Logical Difference b/w Quick & Merge Sort

(The code is the modified version, taken from the Source given below)

def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
    if first<last:
        splitpoint = partition(alist,first,last)
        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
    pivotvalue = alist[first]
    leftmark,rightmark = first+1,last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            done = True
        else:
            alist[first],alist[rightmark] = alist[rightmark],alist[first]

    alist[first],alist[rightmark] = alist[rightmark],alist[first]
    return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

Source: https://runestone.academy/runestone/static/pythonds/SortSearch/TheQuickSort.html

Upvotes: 0

Kasravnd
Kasravnd

Reputation: 107287

As you know Quick Sort is a good choice when you have to sort a lot of elements. When you are working with smaller collections, Bucket Sort may be a better choice.

Quicksort is an example of a divide-and-conquer algorithm that does its main work before the recursive calls, in dividing its data (using partition). and in this case your algorithm is not pythonic and is not a real quick sort algorithm !

so I suggest to use this algorithm instead of that:

def quicksort(seq):
    if len(seq) <= 1: 
        return seq
    lo, pi, hi = partition(seq)
    return quicksort(lo) + [pi] + quicksort(hi)

def partition(seq):
    pi, seq = seq[0], seq[1:]
    lo = [x for x in seq if x <= pi]
    hi = [x for x in seq if x > pi]
    return lo, pi, hi

Upvotes: 3

Chrispresso
Chrispresso

Reputation: 4071

Alright. Starting off, try not to name variables that already have key names, for instance, list. list is already built in for python and will override what used to be considered list.

Bucket sort:
Let's say that we have a list [29, 25, 3, 49, 9, 37, 21, 43]. With bucket sort, it will group some of these values into buckets as seen below.

buckets

The buckets in this case group values [0,9], [10-19], [20-29], [30-39] and [40-49]. Once the buckets are created a sorting algorithm is then used on each bucket, this algorithm can be anything including bucket sort again. Generally in bucket sort the algorithm will look at the most significant bit and compare that to the most significant bit of another value, if they match it will trickle down bit by bit until it is clear which is larger. This type of sorting can also work on characters, lists, etc.

Quick example of most significant bit (MSB) comparison: 3 vs. 9
3 in binary is 0011 9 in binary is 1001
Starting at the left most bit in this case we see a 0 for 3 and 1 for 9, therefore 9 is bigger.
After each bucket is sorted you will end up with this:
sorted buckets

Another example of Bucket sort can be found here: Bucket Sort

Quicksort:
With quicksort you start by picking a pivot element.
After that you reorder the array so that any element with a value less than the pivot comes before the pivot and any element with a value larger than the pivot comes after the pivot.
This is then done recursively to the list of elements that had the smaller values and to the list with the larger values. This concept is pretty straight forward, but picking a good pivot can also be a challenge if you're not familiar with algorithms.

Now...why is bucket sort faster?
Because of the recursion and pivot point involved with quicksort you are generally confined to O(n*log(n))

Since the sorting algorithm of the buckets in bucket sort is MSB, the time complexity of that sorting algorithm is O(n+k).

Now, if you chose a slower sorting algorithm to sort the buckets in bucket sort, you could have quicksort be faster.

I know this is a very high level overview and may be a bit confusing, but hopefully it's enough to help you understand why bucket sort is faster than quicksort but also how quicksort could be faster than bucket sort.

Upvotes: 2

Related Questions