Quicksort returning unsorted array

Question

I have two days trying to figure out why my quicksort function returns all but two elements sorted in correct order.

With the Input

quicksort([0,7,3,11,23,87,999,1023,12,713,5,6,9])

Outputs

[0, 6, 3, 5, 7, 9, 11, 12, 23, 87, 713, 999, 1023]

What do you think is wrong with the function?

def quicksort(array):
    #Base case
    if len(array) <= 1:
        return array
    #Choose pivot always at the left part and partition array around it
    Pivot = partition(array,0,len(array));
    #Add values for left and righ arrays
    left = array[:Pivot]
    right = array[Pivot+1:]
    #Add recursive calls
    left = quicksort(left)
    right = quicksort(right)
    #Append Pivot at the end of left array
    left.append(array[Pivot])
    return left+right

For matters of completion I'm adding the partition function but I'm almost sure the issue is not there.

def partition(array,left,right):
    #If pivot is not on leftmost, swap to make it leftmost
    Pivot = array[left]
    i = left+1
    for j in range(left+1,right):
        if array[j] < Pivot:
            #Swap array[j] and array[i]
            array[j], array[i] = array[i], array[j]
            i += 1;
    #Swap pivot and A[i-1]        
    array[left], array[i-1] = array[i-1], array[left]
    return left

Your current code also fails on sorting [3,1,2] if you wish to use a simpler example. — moreON
– moreON, Commented Jul 15, 2015 at 0:04

moreON · Accepted Answer · 2015-07-15 00:01:44Z

3

Your partition function always returns the left argument, as it was supplied without changing it. I think you intend to return the final position of the pivot element.

answered Jul 15, 2015 at 0:01

moreON

2,00919 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Juanvulcano Over a year ago

I love you, I thought I implemented the partition function perfect but I was wrong. Thanks!

Davide · Accepted Answer · 2015-07-15 16:44:45Z

Just for the sake of completion, making use of pythons comprehension lists, makes the code much simpler to implement and read.

def qs(l):
    if len(l) < 2:
        return l
    pivot = l.pop()
    left = [x for x in l if x < pivot]
    right = [x for x in l if x >= pivot]
    return qs(left) + [pivot] + qs(right)

It reads pretty much like the pseudo-code found in text books.

Lists of size 1 or 0 are sorted by definition
Choose a Pivot. In this case it's the last element
Create two partitions so that one has all the elements smaller than the pivot and the other has the elements greater then or equal to the pivot
Recursively call quicksort on both partitions and append the results with the pivot in the middle

Collectives™ on Stack Overflow

Quicksort returning unsorted array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related