2
\$\begingroup\$

I'm currently doing an algorithms course and implemented this version of the quicksort algorithm. I would like to know if it is an efficient implementation. I've seen a couple others where there is a partition function that partitions the list is that a superior method to what I did?

def quickSort(aList):
    first = []
    second = []
    size = len(aList)
    if size ==0:
        return []
    elif size == 1:
        return aList
    elif size ==2:
        if(aList[1]<aList[0]):
            return list([aList[1],aList[0]])
        else:
            return aList
    else:
        key = aList[0]
        for i in range(1,size):
            if aList[i]<key:
                first.append(aList[i])
            else:
                second.append(aList[i])
        first.append(key)
    return quickSort(first) + quickSort(second)
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

You've implemented a very basic version of the Quicksort algorithm, where you choose the first element as pivot element.

The running time of the quicksort algorithm is however very dependent on the quality of the pivot element. (The pivot should try to split the problem in equal problems). Making it fixed isn't really useful.

For example: say you want to run quicksort on an already sorted list. If you keep using the first element as pivot element, you will end up with a quadratic running time.

A 'solution' is to use random pivot elements, where in each recursive call you choose the pivot randomly (each element has an equal chance). You can find more on this approach online. But the idea is to end up with an average running time of \$O(n*log(n))\$

In addition you implement it by creating 2 new lists and merging them together. Quicksort normally has the advantage that everything can happen in-place, which is a great advantage memory wise.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You're right I should have thought this through a bit more thanks for the response. \$\endgroup\$ Mar 22, 2015 at 11:06
0
\$\begingroup\$

a) You've implemented a basic version of partition() function in your code.

partition(Array, start, end, pivot_index)

b) partition should - switch between the given pivot Array[pivot_index] and the first element Array[start]. - then, partition should run your "append" code, only with cleverly swapping elements so that there is no need for more than a single element of extra memory.

Here is some pseudocode that includes the use of a factory that takes care of picking the right pivot once it is given information about the array.

Partition(A, l, r, pivot_factory)
    """
    Array A, l Left boundary, r Right boundary
    Input: A[l:r]
    """
    p = pivot_factory.get_pivot(A,start,end)
    i = l+1
    for j=l+1 to r:
        if A[j] < p:    # if A[j] > p, do nothing
            swap A[j] and A[i]
            i += 1
    swap A[l] and A[i-1]


QuickSort(array A, length n)
    If n=1 return
    p = ChoosePivot(A,n)
    Partition A around p
    Recursively sort 1st part
    Recursively sort 2nd part

Your version just gives p the first item on the array as pivot - which is expected to give mediocre results as far as runtime is concerned.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.