0

If values equal to the pivot are also considered during quicksort can it be called a stable sort? Here is my implementation of quicksort:

def isOrdered(aList):
ordered = True
for i in range(len(aList)-1):
    if aList[i] > aList[i+1]:
        ordered = False
        break
return ordered

def partition(List,pivotIndex):
    pivot=List[pivotIndex]
    less=[]
    equal=[]
    greater=[]
    if pivotIndex<len(List):
        for i in List:
            if i<pivot:
                less.append(i)
            elif i==pivot:
                equal.append(i)
            else:
                greater.append(i)
    returnlist= [less,equal,greater]
    return returnlist

def quicksort(List,pivotIndex=0):
    sortedList = []
    if pivotIndex>=len(List):
        pivotIndex%=len(List)
    for i in partition(List,pivotIndex):
        for j in i:
            sortedList.append(j)
    pivotIndex+=1
    if isOrdered(sortedList):
        return sortedList
    else:
        return quicksort(sortedList,pivotIndex)

Is it possible to improve stability and maintain computational speed for quicksort at the same time?

3
  • Is this a homework question?
    – fpg1503
    Nov 16, 2016 at 19:07
  • 1
    There's no way to change the partitioning method to guarantee Quicksort's stability. See stackoverflow.com/questions/1278243/… and related questions (links on the right) for more information about why that is, and for suggestions how to change the algorithm to make it stable. Nov 16, 2016 at 19:14
  • @JimMischel "There's no way to change the partitioning method to guarantee Quicksort's stability." That's a very strong claim, and I don't see it supported by the link you gave, nor any links that I followed on the right (of this question, or that one). The fact that many variations of the partitioning method are unstable isn't evidence, of course. Do you have a more specific link or argument to back up your claim?
    – Don Hatch
    Feb 18, 2021 at 9:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.