Recursive Solutions - Python

생성일: 2021년 11월 10일 오후 11:39

Binary_search

BinSearch.py

def binary_search(info, item, fromLocation, toLocation):
    if fromLocation > toLocation:
        return False
    else:
        midPoint = int((fromLocation + toLocation) / 2)
        if item < info[midPoint]:
            return binary_search(info, item, fromLocation, midPoint-1)
        elif item == info[midPoint]:
            return True
        else:
            return binary_search(info, item, midPoint+1, toLocation)

Combinations

ComBin.py

def combinations(group, members):
    if (members == 1):
        return group
    elif (group == members):
        return 1
    else:
        return (combinations(group - 1, members) + combinations(group - 1, members - 1))

Factorial

Factorial.py

def factorial(number):
    if(number == 0):
        return 1
    else:
        return number * factorial(number - 1)

QuickSort1

QuickSort1.py

from io import RawIOBase

def split(values, first, last):
    splitVal = values[first]  # 첫번째 아이템을 pivot으로 잡음
    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