Преимущества Quichesort

Я создал эту программу для задания, в котором от нас требовалось создать реализацию Quichesort. Это гибридный алгоритм сортировки, который использует быструю сортировку до тех пор, пока не достигнет определенной глубины рекурсии (log2 (N), где N - длина списка), а затем переключается на Heapsort, чтобы избежать превышения максимальной глубины рекурсии.

При тестировании моей реализации я обнаружил, что, хотя в целом она работает лучше, чем обычная быстрая сортировка, Heapsort неизменно превосходит обе. Может ли кто-нибудь объяснить, почему Heapsort работает лучше и при каких обстоятельствах Quichesort будет лучше, чем Quicksort и Heapsort?

Обратите внимание, что по какой-то причине в задании алгоритм упоминается как «Quipsort».

Изменить: по всей видимости, Quichesort фактически идентичен Introsort.

Я также заметил, что из-за логической ошибки в моей функции medianOf3() она возвращала неправильное значение для определенных входов. Вот улучшенная версия функции:

def medianOf3(lst):
    """
    From a lst of unordered data, find and return the the median value from
    the first, middle and last values.
    """

    first, last = lst[0], lst[-1]
    if len(lst) <= 2:
        return min(first, last)
    middle = lst[(len(lst) - 1) // 2]
    return sorted((first, middle, last))[1]

Объясняет ли это относительно низкую производительность алгоритма?

Код для Quichesort:

import heapSort             # heapSort
import math                 # log2 (for quicksort depth limit)

def medianOf3(lst):
    """
    From a lst of unordered data, find and return the the median value from
    the first, middle and last values.
    """

    first, last = lst[0], lst[-1]
    if len(lst) <= 2:
        return min(first, last)
    median = lst[len(lst) // 2]
    return max(min(first, median), min(median, last))

def partition(pivot, lst):
   """
   partition: pivot (element in lst) * List(lst) -> 
        tuple(List(less), List(same, List(more))).  
   Where:
        List(Less) has values less than the pivot
        List(same) has pivot value/s, and
        List(more) has values greater than the pivot

   e.g. partition(5, [11,4,7,2,5,9,3]) == [4,2,3], [5], [11,7,9]
   """

   less, same, more = [], [], []
   for val in lst:
      if val < pivot:
         less.append(val)
      elif val > pivot:
         more.append(val)
      else:
         same.append(val)
   return less, same, more

def quipSortRec(lst, limit):
    """
    A non in-place, depth limited quickSort, using median-of-3 pivot.
    Once the limit drops to 0, it uses heapSort instead.
    """

    if lst == []:
        return []

    if limit == 0:
        return heapSort.heapSort(lst)

    limit -= 1
    pivot = medianOf3(lst)
    less, same, more = partition(pivot, lst)
    return quipSortRec(less, limit) + same + quipSortRec(more, limit)

def quipSort(lst):
    """
    The main routine called to do the sort.  It should call the
    recursive routine with the correct values in order to perform
    the sort
    """

    depthLim = int(math.log2(len(lst)))
    return quipSortRec(lst, depthLim)

Код для Heapsort:

import heapq    # mkHeap (for adding/removing from heap)

def heapSort(lst):
    """
    heapSort(List(Orderable)) -> List(Ordered)
        performs a heapsort on 'lst' returning a new sorted list
    Postcondition: the argument lst is not modified
    """

    heap = list(lst)
    heapq.heapify(heap)
    result = []
    while len(heap) > 0:
        result.append(heapq.heappop(heap))
    return result