Python quicksort only sorting first half

Question

I'm taking Princeton's algorithms-divide-conquer course - 3rd week, and trying to implement the quicksort.

Here's my current implementation with some tests ready to run:

import unittest

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[0]
    xLeft, xRight = partition(x)
    print(xLeft, xRight)
    quicksort(xLeft)
    quicksort(xRight)
    return x


def partition(x):
    j = 0
    print('partition', x)
    for i in range(0, len(x)):
        if x[i] < x[0]:
            n = x[j + 1]
            x[j + 1] = x[i]
            x[i] = n
            j += 1

    p = x[0]
    x[0] = x[j]
    x[j] = p
    return x[:j + 1], x[j + 1:]


class Test(unittest.TestCase):
    def test_partition_pivot_first(self):
        arrays = [
            [3, 1, 2, 5],
            [3, 8, 2, 5, 1, 4, 7, 6],
            [10, 100, 3, 4, 2, 101]
        ]

        expected = [
            [[2, 1, 3], [5]],
            [[1, 2, 3], [5, 8, 4, 7, 6]],
            [[2, 3, 4, 10], [100, 101]]
        ]

        for i in range(0, len(arrays)):
            xLeft, xRight = partition(arrays[i])
            self.assertEqual(xLeft, expected[i][0])
            self.assertEqual(xRight, expected[i][1])

    def test_quicksort(self):
        arrays = [
            [1, 2, 3, 4, 5, 6],
            [3, 5, 6, 10, 2, 4]
        ]

        expected = [
            [1, 2, 3, 4, 5, 6],
            [1, 2, 3, 4, 6, 10]
        ]

        for i in range(0, len(arrays)):
            arr = arrays[i]
            quicksort(arr)
            self.assertEqual(arr, expected[i])


if __name__ == "__main__":
    unittest.main()

so for array = [3, 5, 6, 10, 2, 4] I get [2, 3, 6, 10, 5, 4] as a result... I can't figure what's wrong with my code. It partitions just fine, but the results are off...

Can anyone chip in? :) Thank you!

LiorA · Accepted Answer · 2017-04-15 13:55:53Z

1

it's actually so minor problem that you'd be laughing the problem resides with quicksort function the correct one is:

def quicksort(x):
 if len(x) <= 1:
    return x

 pivot = x[0]
 xLeft, xRight = partition(x)
 print(xLeft, xRight)
 quicksort(xLeft)
 quicksort(xRight)
 x=xLeft+xRight #this one!
 return x

what happens is python created a new object out of these xleft and xright they were never an in place-sort

so this is one solution(which is not in place) the other one is to pass the list,the start_index,end_index and do it in place

well done fella! edit: and actually if you'd print xleft and xright you'd see it performed perfectly:)

answered Apr 15, 2017 at 13:55

LiorA

4413 silver badges13 bronze badges

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

2 Comments

Ric Over a year ago

I now understand what's going on! Thank you very much for taking the time to help me! :-)

LiorA Over a year ago

glad I could! and keep up implementing algorithms!

Collectives™ on Stack Overflow

Python quicksort only sorting first half

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related