Может ли быстрая сортировка быть стабильной?
Если во время быстрой сортировки учитываются также значения, равные центральной точке, можно ли это назвать устойчивой сортировкой? Вот моя реализация быстрой сортировки:
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)
Можно ли улучшить стабильность и одновременно поддерживать скорость вычислений для быстрой сортировки?