Getting Quick Sort in Python right in simplest way (translating from Java)

Question

I am reviewing sorting algorithms and tried to write Quick Sort algorithm. The simplest implementation that I found is written in Java and I have run it to confirm that it works. However, when I tried to rewrite it in Python, it seems to be off in some way. I have spent a few hours trying to debug this as to why it doesn't work, but it is quite difficult to debug because it's recursion based algorithm... If someone could tell me what's wrong with my implementation below, that would be very helpful. Thank you!

def partition(arr, start, end):
    piv = (start + end)//2
    pivotVal = arr[piv]

    left = start
    right = end

    while left <= right:
        if arr[left] < pivotVal:
            left += 1

        if arr[right] > pivotVal:
            right -= 1

        if left <= right:
            temp = arr[left]
            arr[left] = arr[right]
            arr[right] = temp
            left += 1
            right -= 1

    return left

def quickSort(arr, left, right):
    piv = partition(arr, left, right)

    if left < (piv - 1):
        quickSort(arr, left, piv - 1)

    if piv < right:
        quickSort(arr, piv, right)

myList = [54,26,93,17,77,31,44,55,20] # this doesn't get sorted quite right
quicksort(myList, 0, len(myList)-1)
print(myList)

EmmaZhao · Accepted Answer · 2015-11-17 06:32:00Z

1

Try:

    while left <= right:
        while arr[left] < pivotVal:
            left += 1

        while arr[right] > pivotVal:
            right -= 1

        if left <= right:
            temp = arr[left]
            arr[left] = arr[right]
            arr[right] = temp
            left += 1
            right -= 1

answered Nov 17, 2015 at 6:32

EmmaZhao

1117 bronze badges

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

1 Comment

user1330974 Over a year ago

Oh, I can't believe that's what I have been missing!! Thanks a lot!!! That's why it's good to not code for more than a few hours at one sitting. :D

Omkar · Accepted Answer · 2018-08-11 01:51:14Z

0

This might help u to understand,

def partition(arr,left,right):
  i = (left - 1)
  pivot =arr[right]
  for j in range(left,right):
    if arr[j]<= pivot:
      i += 1
      arr[i],arr[j] = arr[j],arr[i]
  arr[i+1],arr[right]=arr[right],arr[i+1]
  return(i+1)

def quickSort(arr, left, right):
  if left < right:
    piv = partition(arr, left, right)
    quickSort(arr, left, piv - 1)
    quickSort(arr, piv+1, right)

arr = [54,26,93,17,77,31,44,55,20,67]
quickSort(arr, 0, len(arr)-1)
print(arr)

edited Aug 11, 2018 at 1:51

answered Aug 11, 2018 at 0:43

Omkar

1111 silver badge9 bronze badges

Collectives™ on Stack Overflow

Getting Quick Sort in Python right in simplest way (translating from Java)

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