Sorting Algorithms - Python

생성일: 2021년 12월 13일 오후 6:59

SelectionSort.py

def min_index(values, start_index, end_index):
    index_of_min = start_index
    for index in range(start_index + 1, end_index + 1):
        if (values[index] < values[index_of_min]):
            index_of_min = index
    return index_of_min

def selection_sort(values):
    endIndex = len(values) - 1
    for current in range(0, endIndex):
        index = min_index(values, current, endIndex)
        values[current], values[index] = values[index], values[current]

BubbleSort.py

def bubble_sort(values):
    current = 0

    while(current < len(values) - 1):
        BubbleUp(values, current, len(values) - 1)
        current += 1
    
def BubbleUp(values, startIndex, endIndex):
    for i in range(endIndex, startIndex, -1):
        if (values[i] < values[i-1]):
            values[i], values[i-1] = values[i-1], values[i]

ShortBubble.py

def short_bubble(values, numValues):
    '''[10]'''
    current = 0
    sort = False

    while(current < numValues - 1 and not sort):
        bubble_up(values, current, numValues - 1, sort)
        current += 1

def bubble_up(values, startIndex, endIndex, sort):
    '''[11]'''
    sort = True
    for index in range(endIndex, startIndex - 1, -1):
        if (values[index] < values[index - 1]):
            values[index], values[index - 1] = values[index - 1], values[index]
            sort = False

InsertionSort.py

def insertion_sort(values):
    for count in range(0, len(values)):
        insert_item(values, 0, count)

def insert_item(values, start_index, end_index):
    finished = False
    current = end_index
    more_to_search = (current != start_index)

    while(more_to_search and not finished):
        if (values[current] < values[current - 1]):
            values[current], values[current - 1] = values[current- 1], values[current] 
            current -= 1
            more_to_search = (current != start_index)
        else:
            finished = True

HeapSort.py

def reheap_down(elements, root, bottom):
    left_child  = root * 2 + 1
    right_child = root * 2 + 2
    if(left_child <= bottom):
        if (left_child == bottom):
            max_child = left_child
        else:
            if (elements[left_child] <= elements[right_child]):
                max_child = right_child
            else:
                max_child = left_child
        if (elements[root] < elements[max_child]):
            elements[root], elements[max_child] = elements[max_child], elements[root]
            reheap_down(elements, max_child, bottom)

def heap_sort(values, numValues):
    for index in range(numValues//2 - 1, -1, -1):
        reheap_down(values, index, numValues - 1)
    for index in range(numValues - 1, 0, -1):
        values[0], values[index] = values[index], values[0]
        reheap_down(values, 0, index - 1)

QuickSort.py

def split(values, first, last):
    splitVal = values[first]
    saveFirst = first

    first += 1
    while(True):
        onCorrectSide = True
        while(onCorrectSide):
            if(values[first] > splitVal):
                onCorrectSide = False
            else:
                first += 1
                onCorrectSide = (first <= last)

        onCorrectSide = (first <= last)

        while(onCorrectSide):
            if(values[last] <= splitVal):
                onCorrectSide = False
            else:
                last -= 1
                onCorrectSide = (first <= last)

        if(first < last):
            values[first], values[last] = values[last], values[first]
            first += 1
            last -= 1

        if (first > last):
            break
        
    splitPoint = last
    values[saveFirst], values[splitPoint] = values[splitPoint], values[saveFirst]

    return splitPoint

    
def quick_sort(values, first, last):
    if (first < last):
        splitPoint = split(values, first, last)
        quick_sort(values, first, splitPoint - 1)
        quick_sort(values, splitPoint + 1, last)
        return values

MergeSort.py

def merge_sort(values, first, last):
    if (first < last):
        middle = (first + last) // 2
        merge_sort(values, first, middle)
        merge_sort(values, middle + 1, last)
        return merge(values, first, middle, middle + 1, last)
    else:
        return values

def merge(values, leftFirst, leftLast, rightFirst, rightLast):
    tempArray = [0] * len(values)
    index = leftFirst
    saveFirst = leftFirst

    while((leftFirst <= leftLast) and (rightFirst <= rightLast)):
        if (values[leftFirst] < values[rightFirst]):
            tempArray[index] = values[leftFirst]
            leftFirst += 1
        else:
            tempArray[index] = values[rightFirst]
            rightFirst += 1
        index += 1

    while(leftFirst <= leftLast):
        tempArray[index] = values[leftFirst]
        leftFirst += 1
        index += 1
    
    while(rightFirst <= rightLast):
        tempArray[index] = values[rightFirst]
        rightFirst += 1
        index += 1
    
    for index in range(saveFirst, rightLast + 1):
        values[index] = tempArray[index]

    return values