14

I had to implement the QuickSort algorithm for a homework in a language of my choice and I chose Python.

During the lectures, we've been told that QuickSort is memory efficient because it works in-place; i.e., it has no additional copies of parts of the input array for recursions.

With this in mind, I tried to implement the QuickSort algorithm in Python, but shortly afterwards realized that in order to write an elegant piece of code I would have to pass parts of the array to the function itself while recursing. Since Python creates new lists each time I do this, I have tried using Python3 (because it supports the nonlocal keyword). The following is my commented code. 

def quicksort2(array):
# Create a local copy of array.
arr = array

    def sort(start, end):
        # Base case condition
        if not start < end:
            return

        # Make it known to the inner function that we will work on arr
        # from the outer definition
        nonlocal arr

        i = start + 1
        j = start + 1

        # Choosing the pivot as the first element of the working part
        # part of arr
        pivot = arr[start]

        # Start partitioning
        while j <= end:
            if arr[j] < pivot:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
                i += 1
            j += 1
        temp = arr[start]
        arr[start] = arr[i - 1]
        arr[i - 1] = temp
        # End partitioning

        # Finally recurse on both partitions
        sort(start + 0, i - 2)
        sort(i, end)
    sort(0, len(array) - 1)

Now, I'm not sure whether I did the job well or am I missing something. I have written a more Pythonic version of QuickSort but that surely doesn't work in-place because it keeps returning parts of the input array and concatenates them.

My question is, is this the way of doing it in Python? I have searched both Google and SO but haven't found a true in-place implementation of QuickSort, so I thought it'd be best to ask.

Esoteric Screen Name
  • 6,082
  • 4
  • 29
  • 38
Can Ibanoglu
  • 604
  • 1
  • 6
  • 10
  • 2
    Have you tried Python memory profiler which gives you line by line memory analysis. – Hemanth Jul 21 '13 at 14:48
  • Instead of writing an inner function and using `nonlocal` why don't you define the `quicksort` function like `def quicksort(array, start=0, end=None): if end is None: end = len(array) - 1 ...`? Also, it is standard practice to implement a `partition` function separately, thus quicksort's code becomes: `q = partition(array, start, end) quicksort(array, start, q-1) quicksort(array, q+1 end)` – Bakuriu Jul 21 '13 at 14:54
  • You can pass `array` recursively without copying it; you just can't slice it. Also, you don't need `nonlocal` because you're changing only the contents of the list bound to `arr`, not which list is bound. – David Eisenstat Jul 21 '13 at 14:54
  • 1
    Various: (1) `arr = array` doesn't make a local copy. That simply says `arr` is now a new name for `array`. `arr = array[:]` would make a shallow copy (not that `array` is a great name for a variable). (2) You don't need a `temp` variable for swapping: `arr[i], arr[j] = arr[j], arr[i]` will do the job. (3) As already mentioned above, you won't actually be creating extra copies if you pass `array` as an argument. – DSM Jul 21 '13 at 14:55
  • 1
    @DavidEisenstat, thank you very much for that insight, I was confused about variable scopes in functions. So basically, I can modify the contents of an object from an inner function definition but can't make assignments, right? To everyone, thank you very much for the clarifications. – Can Ibanoglu Jul 21 '13 at 15:08
  • @CanIbanoglu Yeah, that's right. The reason Python has `nonlocal` is because there's no other way to distinguish modifying the value of an outer variable versus creating a new variable that shadows the outer. – David Eisenstat Jul 21 '13 at 15:21
  • I don't think you have a bad implementation, other than what has been said in comments. It can be a valid choice to keep subroutines nested. Note that there is also codereview.SE for getting comments on code style in a particular language. The answers below, just giving some valid implementations, are less valuable than the comments on the question in my opinion. – Maxim Oct 31 '18 at 07:48

7 Answers7

17

Sure not the best way, plus this famous algorithm will have dozens of perfect implementations.. this is mine, quite easy to understand

def sub_partition(array, start, end, idx_pivot):

    'returns the position where the pivot winds up'

    if not (start <= idx_pivot <= end):
        raise ValueError('idx pivot must be between start and end')

    array[start], array[idx_pivot] = array[idx_pivot], array[start]
    pivot = array[start]
    i = start + 1
    j = start + 1

    while j <= end:
        if array[j] <= pivot:
            array[j], array[i] = array[i], array[j]
            i += 1
        j += 1

    array[start], array[i - 1] = array[i - 1], array[start]
    return i - 1

def quicksort(array, start=0, end=None):

    if end is None:
        end = len(array) - 1

    if end - start < 1:
        return

    idx_pivot = random.randint(start, end)
    i = sub_partition(array, start, end, idx_pivot)
    #print array, i, idx_pivot
    quicksort(array, start, i - 1)
    quicksort(array, i + 1, end)

Ok first a seperate function for the partition subroutine. It takes the array, the start and end point of interest, and the index of pivot. This functions should be clear

Quicksort then call the partition subroutine for the first time on the whole array; then call recursevely itself to sort everything up to the pivot and everything after.

ask if you dont understand something

Ant
  • 5,151
  • 2
  • 26
  • 43
  • 1
    Thank you very much for this piece of code, I can see how it is better than mine. I guess I did some pretty stupid stuff because I thought passing the array to the function during recursion would make copies of it. – Can Ibanoglu Jul 21 '13 at 15:11
  • you're welcome ;-) indeed, if you pass an array it will not make any copies of it :-) – Ant Jul 21 '13 at 15:13
  • Thank you for the in-place partitioning implementation :) – seismatica Oct 21 '17 at 05:46
2

I have started learning python lately and the following is my attempt at implementing quicksort using python. Hope it is helpful. Feedback is welcomed :) 

#!/usr/bin/python

Array = [ 3,7,2,8,1,6,8,9,6,9]

def partition(a, left, right):

    pivot = left + (right - left)/2
    a[left],a[pivot] = a[pivot], a[left] # swap
    pivot = left
    left += 1

    while right >= left :
        while left <= right and a[left] <= a[pivot] :
            left += 1
        while left <= right and a[right] > a[pivot] :
            right -= 1

        if left <= right:
            a[left] , a[right] = a[right], a[left] # swap
            left += 1
            right -= 1
        else:
            break

    a[pivot], a[right] = a[right] , a[pivot]

    return right


def quicksort(array , left,right):
    if left >= right:
        return  
    if right - left == 1:
        if array[right] < array[left]:
            array[right], array[left] = array[left] , array[right]
            return           

    pivot = partition(array, left, right)

    quicksort(array, left, pivot -1)
    quicksort(array, pivot+1,right)         

def main():
    quicksort(Array, 0 , len(Array) -1)   
    print Array 

main()
Maneesh18187
  • 63
  • 8
1

Here is another implementation: 

def quicksort(alist):
    if len(alist) <= 1:
        return alist
    return part(alist,0,len(alist)-1)

def part(alist,start,end):
    pivot = alist[end]  
    border = start
    if start < end:  
        for i in range(start,end+1):
            if alist[i] <= pivot:
                alist[border], alist[i] = alist[i], alist[border]
                if i != end:
                    border += 1
        part(alist,start,border-1)  
        part(alist,border+1,end)  
    return alist
EbrahimA
  • 59
  • 1
  • 1
  • 6
0

Here's what I came up with. The algorithm is in-place, looks nice and is recursive. 

# `a` is the subarray we're working on
# `p` is the start point in the subarray we're working on
# `r` is the index of the last element of the subarray we're working on

def part(a,p,r):
   k=a[r] #pivot 
   j,q=p,p
   if p<r: # if the length of the subarray is greater than 0
       for i in range(p,r+1):
           if a[i]<=k:
               t=a[q]
               a[q]=a[j]
               a[j]=t
               if i!=r:
                   q+=1
               j+=1
           else:
               j+=1
       part(a,p,q-1) # sort the subarray to the left of the pivot
       part(a,q+1,r) # sort the subarray to the right of the pivot  
   return a
def quicksort(a):
   if len(a)>1:
      return part(a,0,len(a)-1)
   else:
      return a
goodmove
  • 51
  • 5
0

Explanation: Pivot is always the last element in given array. In my approach I keep track of the 'border' between numbers smaller and bigger than pivot. Border is an index of first number in 'bigger' group. At the end of each iteration we swap number under 'border' with the pivot number.

And the code:

def qs(ar, start, end):
    if (end-start < 1):
        return
    if (end-start == 1):
        if(ar[start] > ar[end]):
            tmp = ar[start]
            ar[start] = ar[end]
            ar[end] = tmp
        return
    pivot = ar[end - 1]
    border_index = start
    i = start
    while(i <= end - 1):
        if (ar[i] < pivot):
            if i > border_index:
                tmp = ar[i]
                ar[i] = ar[border_index]
                ar[border_index] = tmp
            border_index += 1
        i+=1
    ar[end-1] = ar[border_index]
    ar[border_index] = pivot
    qs(ar, start, border_index)
    qs(ar, border_index + 1, end)

qs(ar, 0, n)
dianafa
  • 1
  • 2
0

An in place implementation with pivot as the right most element

def partition(array, begin, end):
    pivot = end
    while begin < pivot:
        if array[begin] > array[pivot]:
            if begin != pivot - 1:
                array[pivot], array[pivot - 1] = array[pivot - 1], array[pivot]
            array[begin], array[pivot] = array[pivot], array[begin]
            pivot-=1
        else:
            begin+=1
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    if begin < end:
        partition_index = partition(array, begin, end)
        quicksort(array, begin, (partition_index - 1))
        quicksort(array, (partition_index + 1), end)

Explanation - partition

1.Taking pivot as "end" - right most element
2.Bring pivot to its right position in sorted order.
3.Comparing element at begin with pivot element
    Loop breaks when all elements are checked indicated by [begin] overlapping [pivot]. begin==pivot
        If elem[begin] > elem[pivot]
            The element is greater than elem[pivot]. It is at a wrong place. It has to come after pivot
            Swap elements [pivot] and [pivot-1] if (pivot-1) != begin
            Swap elements [pivot] and [begin]
            Now the element at pivot is either in position [pivot-1] or at current [begin] position
            Either way pivot has moved one place to the left. So decrement pivot by 1
        Else
            element at begin is <= to pivot and to the left of pivot.
            So it is at an acceptable position
            Increment begin to check for next element

Explanation - quick sort

1.Choosing a pivot, placing it in correct position in array and getting its index using the method "partition()".
2.Dividing array into left side and right side of pivot using begin, end and partition_index
3.Calling quicksort on left and right side array of pivot

Nandu Dharmapalan
  • 406
  • 5
  • 13
-1
def quicksort(arr):
    lesser = []
    equal = []
    greater = []
    if len(arr)>1:
        pivot = arr[len(arr)-1]
        start = 0
        while start<len(arr):
            if arr[start] > pivot:
                greater.append(arr.pop(start)) 
            elif arr[start] < pivot:
                lesser.append(arr.pop(start))
            else:
                start = start + 1

        return (quicksort(lesser) + arr + quicksort(greater))

    else:
        return (arr)

print(quicksort([2,333,-22,0,54, 22, 37, 0.3, -2, 22]))
Abhik Maiti
  • 1
  • Explain how your answer is different from the currently accepted answer unless it's not going to be helpful. – Mehran Torki Oct 31 '18 at 07:45
  • This is inplace and more pythoinic. (As we are adding to greater and lesser by popping the current array) – Abhik Maiti Nov 06 '18 at 15:07
  • Explain it inside your answer. – Mehran Torki Nov 06 '18 at 17:40
  • 2
    This is not an in-place solution: you have created new lists `lesser`, `equal`, `greater` which are of type `list`, and you produce the fourth list when you concatenate three lists in return `statement`. Any inplace solution should work with the type which support \_\_getitem\_\_/\_\_setitem\_\_ without changing the type of the instance, for example. Your solution will turn it to the `list`. – dmitry_romanov Feb 13 '20 at 14:57