CODEWITHSUNDEEP
pythonsortingrecursionquicksort
sixpain
sixpain

Reputation: 354

QuickSort which correctly orders an array, but doesn't return it ordered

I'm implementing Quick Sort in Python and I have little problem with it. My function works perfectly recursively, but it doesn't return me the ordered array, and returns me just the original array.

In my code I have two versions of Quick Sort. quickSort_2 works correctly and orders the list. Instead quickSort_1 works exactly equal to quicksort_1 , but gives me back the original array.

Any idea on why this is happening?

import random
import list

def partition(A,p):
    pivot=A[p]
    sup=0
    inf=len(A)-1
    while sup!=inf:
        while A[sup]<pivot:
            sup+=1
        while A[inf]>pivot:
            inf-=1
        list.swap(inf,sup,A) #swap
        print A
    return sup

def quickSort_1(A):
    if len(A)<=1:
        return A
    r=random.choice(range(0,len(A)-1))
    print A
    m=partition(A,r)
    return quickSort_1(A[:m+1])+quickSort_2(A[m+1:])

def quickSort_2(A):
    if len(A)<=1:
        return A
    r=random.choice(range(0,len(A)-1))
    print A
    m=partition(A,r)
    quickSort_1(A[:m+1])
    quickSort_2(A[m+1:])
    return A

Upvotes: 1

Views: 123

Answers (1)

Dorian
Dorian

Reputation: 1488

You are returning the original array A in your second function.

What you should do is save the sorted array as your original array and return this value. Something like this:

A_new = quickSort_1(A[:m+1])+quickSort_2(A[m+1:])
return A_new

Since you are altering the array A in the scope of the function quickSort_1 or quickSort_2, there is no alteration of the original array A.

Upvotes: 1

Related Questions