IntroSpective Sort Python (Quick + Heap + Insertion)

IntroSpective_sort.py

# Time Complexity O(n),O(n^2),O(n^2) | Space Complexity O(1) | stable
def insertSort(array, begin=0, end=None):
    if end == None:
        end = len(array) - 1
    for i in range(begin, end):
        j = i
        toChange = array[i]
        while (j != begin and array[j - 1] > toChange):
            array[j] = array[j - 1]
            j -= 1
        array[j] = toChange
    return array
  
# Time Complexity O(nlogn) | Space Complexity O(1) | not stable
def heapify(arr, n, i):  # Max Heap
    largest = i
    l = 2 * i + 1  # Left Node
    r = 2 * i + 2  # Right Node

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # root가 최대가 아니면
    # 최대 값과 바꾸고, 계속 heapify
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    for i in range(n // 2, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # Heapify root element
        heapify(arr, i, 0)
        
    return arr
  
# comparison보다 XOR을 속도면에서 선택함
def medianOf3(array, lowIdx, midIdx, highIdx):
    if ((array[lowIdx] > array[midIdx]) != (array[lowIdx] > array[highIdx])):
        return array[lowIdx]
    elif ((array[midIdx] > array[lowIdx]) != (array[midIdx] > array[highIdx])):
        return array[midIdx]
    else:
        return array[highIdx]


def getPartition(array, low, high, pivot):
    i = low
    j = high
    while True:
        while (array[i] < pivot):
            i += 1
        j -= 1
        while (pivot < array[j]):
            j -= 1
        if i >= j:
            return i
        array[i], array[j] = array[j], array[i]
        i += 1

        
# Time Complexity O(nlogn) | Space Complexity O(logn) | not stable
def introSort(array):
    maxDepth = 2 * (len(array).bit_length() - 1) # 2* (log2(length) - 1)
    sizeThreshold = 16
    return introSortHelper(array, 0, len(array), sizeThreshold, maxDepth)


def introSortHelper(array, start, end, sizeThreshold, depthLimit):
    # if size > 16: heap sort or quick sort
    while(end - start > sizeThreshold):
        if (depthLimit == 0):
            return heapSort(array)
        depthLimit -= 1

        median = medianOf3(array, start, start +
                           ((end - start) // 2) + 1, end - 1)
        p = getPartition(array, start, end, median)
        introSortHelper(array, p, end, sizeThreshold, depthLimit)
        end = p
    # insert Sort로 종료
    return insertSort(array, start, end)

result.txt

array4 = [randint(-5000, 5000)
              for i in range(5000//3)] + \
        [i for i in range(5000//3)] + \
        [1] + \
        [i for i in reversed(range(5000//3))]

# Result
def: sorted(), Min Execution Time: 0.00000초
def: countSort(), Min Execution Time: 0.00300초
def: introSort(), Min Execution Time: 0.01200초
def: quickSort(), Min Execution Time: 0.01300초
def: mergeSort(), Min Execution Time: 0.01800초
def: timSort(), Min Execution Time: 0.02100초
def: heapSort(), Min Execution Time: 0.03100초
def: smoothSort(), Min Execution Time: 0.03100초
def: insertSort(), Min Execution Time: 1.31700초
def: bubbleSort(), Min Execution Time: 2.35200초

array = [i for i in reversed(range(5000))]

# Result
def: sorted(), Min Execution Time: 0.00000초
def: countSort(), Min Execution Time: 0.00200초
def: introSort(), Min Execution Time: 0.00600초
def: quickSort(), Min Execution Time: 0.01400초
def: mergeSort(), Min Execution Time: 0.01500초
def: timSort(), Min Execution Time: 0.02600초
def: smoothSort(), Min Execution Time: 0.02800초
def: heapSort(), Min Execution Time: 0.02900초
def: insertSort(), Min Execution Time: 2.73700초
def: bubbleSort(), Min Execution Time: 3.69000초