Getting recursion wrong in Quick Sort

Question

I have seen numerous cases of Quicksort implementation in Python related doubts here on stack, but could not find what I am looking for. My question is specific to the implementation below:

# Implementation of Quick-Sort algorithm in Python as taught in the course: Design and Analysis of Algorithms on Coursera

def QuickSort(array, length):
    if (length == 1 or length == 0):
        return

    numComparisons = 0
    numComparisons = numComparisons + length - 1

    print('array to be sorted is: ', array) 
    pivot = ChoosePivot(array,length)
    print('Pivot is: ', pivot)
    left    = 0
    right = length

    pivotIndex = Partition(array,left,right)

    print('array after partitioning step is: ', array)
    print('Pivot Index in the array is:', pivotIndex)

    QuickSort(array[:pivotIndex], pivotIndex)
    QuickSort(array[pivotIndex+1:], length-pivotIndex-1)
    print('Sorting is done! Final array is:', array)

    return numComparisons,array

def ChoosePivot(array,length):
    #For the first part of the question, choosing first element of array as pivot element
    return (array[0])

def Swap(array,elementLeft,elementRight):
    tmp = array[elementLeft]
    array[elementLeft] = array[elementRight]
    array[elementRight] = tmp
    return array

def Partition(array,left,right):
    pivot = array[left]
    i = left + 1
    j = left + 1    

    for j in range(right):
        if (array[j] < pivot):
            Swap(array,j,i)
            i = i + 1

    # send pivot to the correct position
    array = Swap(array,left,i-1)
    return (i-1)

array = [7,5,4,6,1,15,12]
numElements = len(array)  
numComp, array = QuickSort(array,numElements)
print('Total number of comparisons',numComp)
print(array)

So the idea is to use the first element of the array as a pivot element and carry out the partitioning on the basis of the pivot element. (Not explaining the algorithm here as I don't think it is of great importance here)

On running the above code I get the following output:

('array to be sorted is: ', [7, 5, 4, 6, 1, 15, 12])
('Pivot is: ', 7)
('array after partitioning step is: ', [1, 5, 4, 6, 7, 15, 12])
('Pivot Index in the array is:', 4)
('array to be sorted is: ', [1, 5, 4, 6])
('Pivot is: ', 1) 
('array after partitioning step is: ', [1, 5, 4, 6])
('Pivot Index in the array is:', 0)
('array to be sorted is: ', [5, 4, 6])
('Pivot is: ', 5)
--->('array after partitioning step is: ', [4, 5, 6])
--->('Pivot Index in the array is:', 1)
--->('Sorting is done! Final array is:', [4, 5, 6])
--->('Sorting is done! Final array is:', [1, 5, 4, 6])
('array to be sorted is: ', [15, 12])
('Pivot is: ', 15)
('array after partitioning step is: ', [12, 15])
('Pivot Index in the array is:', 1)
--->('Sorting is done! Final array is:', [12, 15])
--->('Sorting is done! Final array is:', [1, 5, 4, 6, 7, 15, 12])
('Total number of comparisons', 6)
[1, 5, 4, 6, 7, 15, 12]

So, I am not able to understand as to why there is a change in the positions of the elements back to the original one even after it shows that sorting has taken place (Look at the lines marked with '--->' in front).

I feel that it has to do with the way I am passing the arrays. Any help would be appreciated and If more details are required, let me know

@Andreas I was not aware of the things mentioned in the linked article. But it sounds fair. I will surely keep it in mind from next time before posting here — Abhishek Tyagi
– Abhishek Tyagi, Commented Jul 13, 2019 at 17:49

Shuki Avraham · Accepted Answer · 2019-07-13 18:28:50Z

1

Try to change:

array = Swap(array,left,i-1)

to:

Swap(array,left,i-1)

when you assign a value to the array inside a function, python creates a new array and you lose the reference to the original one

EDIT: I think the problem is the function call to QuickSort for the same reason, pass the array with start/end indexes instead of cutting it. another problem is in the partition function, you should add left to j.

this is the complete code:

def QuickSort(array, start, end, length):
    if (end - start <=1):
        return

    numComparisons = 0
    numComparisons = numComparisons + length - 1

    print('array to be sorted is: ', array[start:end]) 
    pivot = ChoosePivot(array[start:end],length)
    print('Pivot is: ', pivot)
    left    = start
    right = end

    pivotIndex = Partition(array,left,right)

    print('array after partitioning step is: ', array[start:end])
    print('Pivot Index in the array is:', pivotIndex)

    QuickSort(array,start, pivotIndex, pivotIndex)
    QuickSort(array, pivotIndex+1, end, length-pivotIndex-1)
    print('Sorting is done! Final array is:', array[start:end])

    return numComparisons,array

def ChoosePivot(array,length):
    #For the first part of the question, choosing first element of array as pivot element
    return (array[0])

def Swap(array,elementLeft,elementRight):
    tmp = array[elementLeft]
    array[elementLeft] = array[elementRight]
    array[elementRight] = tmp
    return array

def Partition(array,left,right):
    pivot = array[left]
    i = left + 1
    j = left + 1    

    for j in range(right):
        if (array[left+j] < pivot):
            Swap(array,left+j,i)
            i = i + 1

    # send pivot to the correct position
    Swap(array,left,i-1)
    return (i-1)

array = [7,5,4,6,1,15,12]
numElements = len(array)  
numComp, array = QuickSort(array,0,6,numElements)
print('Total number of comparisons',numComp)
print(array)

edited Jul 13, 2019 at 18:28

answered Jul 13, 2019 at 17:46

Shuki Avraham

1,0531 gold badge7 silver badges14 bronze badges

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

5 Comments

Abhishek Tyagi Over a year ago

It didn't work. I even tried using tuples instead of a 'temp' variable for sorting

Shuki Avraham Over a year ago

also, try to send the full array to QuickSort with start/end indexes instead of cutting it, so it will be passed by reference

Abhishek Tyagi Over a year ago

Ya, I have seen the above implementation and it works for me as well (I think I should have mentioned it in the question). But I am facing the problem specifically when I try and pass the slices of array to the quick sort function. I don't know what makes it behave differently in the later case

Shuki Avraham Over a year ago

when you pass a slice of a list, python pass it by value, it makes a copy of the slice. you modify the copy and print it, but the original doesn't change and you don't use the return value of the function

Abhishek Tyagi Over a year ago

Thanks @shuki. I have chosen your answer as the final one. It gave me a good insight into what I might be doing wrong.

rcgldr · Accepted Answer · 2019-07-13 19:28:35Z

1

Simplified single function version:

def quicksort(a, lo, hi):
    if(lo < hi):
        pivot = a[lo]
        i = lo+1
        for j in range(lo+1, hi+1):
            if a[j] < pivot:
                a[i],a[j] = a[j],a[i]
                i += 1
        i -= 1
        a[i],a[lo] = a[lo],a[i]
        quicksort(a, lo, i-1)
        quicksort(a, i+1, hi)

answered Jul 13, 2019 at 19:28

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Collectives™ on Stack Overflow

Getting recursion wrong in Quick Sort

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related