CODEWITHSUNDEEP
pythonalgorithmquicksort
InspiredCoder
InspiredCoder

Reputation: 404

Having difficulty in implementing QuickSort

I have been trying to implement quicksort for like 2 days now (Looks like my programming skills are getting rusty). I do not know what I am doing wrong. I was about to give up so I thought I should consult the discussion forum.

here is the code that I am trying to implement in python. But it is not giving the desired result. Anyone can please point out what I am doing wrong?

def QuickSort(A,p,r):

if p < r:
    pivotIndex = Partition(A,p,r)
    QuickSort(A,p,pivotIndex-1)
    QuickSort(A,pivotIndex+1,r)
    return A
def Partition(A,p,r):

m = A[p]
i = p+1
for j in range( p+1 , r ):
    if A[j] < m:
        A[j] , A[i] = A[i] , A[j]
        i+=1
A[p], A[i-1] = A[i-1] , A[p]
return i-1

The output for test input is:

>>>QuickSort([9,8,7,6,5,4,3,2,1],0,9)
[1, 3, 5, 6, 7, 4, 8, 2, 9]

I will be very thankful if anyone help me in implementing this.

Regards

Upvotes: 2

Views: 404

Answers (4)

Ma3x
Ma3x

Reputation: 6549

It seems that you wanted to keep the pivot on the left side and skip it, but that didn't turn out well, so I just moved it to the end of the array and reduced the iteration index accordingly and then reversed the post-partition swap (to take into consideration the pivot movement).

def Partition(A,p,r):

  m = A[p]
  A[p], A[r] = A[r], A[p]
  i = p
  for j in range( p, r ):
    if A[j] < m:
        A[j] , A[i] = A[i] , A[j]
        i+=1
  A[r], A[i] = A[i] , A[r]
  return i

I think that you could do it with the pivot on the left side, but then you would have to change the loop direction I guess, but I am not sure.

EDIT: Sorry I forgot to add the call is then QuickSort([9,8,7,6,5,4,3,2,1],0,8), since the indices are inclusive now.

Upvotes: 0

InspiredCoder
InspiredCoder

Reputation: 404

I have figured out the answer. It appeared that I was passing one-less to the QuickSort method

def QuickSort(A,p,r):
    if r-p <= 1: return
    pivotIndex = Partition(A,p,r)
    QuickSort(A,p,pivotIndex)
    QuickSort(A,pivotIndex+1,r)
    return A
def Partition(A,p,r):

    m = A[p]
    i = p+1

    for j in range( p+1 , r ):
        if A[j] < m:
            A[j] , A[i] = A[i] , A[j]
        i= i + 1
    A[p], A[i-1] = A[i-1] , A[p]
    return i-1

It is the correct implementation

Upvotes: 1

amatellanes
amatellanes

Reputation: 3735

You can try this implementation in one line of code:

def QuickSort(list):
    return [] if list==[]  else QuickSort([x for x in list[1:] if x < list[0]]) + [list[0]] + QuickSort([x for x in list[1:] if x >= list[0]])

print QuickSort([9,8,7,6,5,4,3,2,1])

Upvotes: 1

user2357112
user2357112

Reputation: 280500

Slicing doesn't return a view of the original list; it makes a new list out of data from the old list. That means the recursive calls to QuickSort don't change the original list.

Upvotes: 2

Related Questions