[Python] 5장 재귀와 반복 : 정렬 (Sorting)

 

 

 

1. 선택 정렬 (Selection sort)

 

 

 

 

 

재귀 버전

def selectionSort(xs):
    if xs != []:
        smallest = min(xs)
        xs.remove(smallest)
        return [smallest] + selectionSort(xs)
    else:
        return []

 

 

꼬리재귀 버전

def selectionSort(xs):
    def loop(xs, ss):
        if xs != []:
            smallest = min(xs)
            xs.remove(smallest)
            return loop(xs, [smallest] + ss)    #ss.append(smallest) return loop(xs,ss)
        else:
            return ss

    return loop(xs, [])

 

 

 

 

while 루프 버전

def selectionSort(xs):
    ss = []
    while xs != []:
        smallest = min(xs)
        xs.remove(smallest)
        ss = [smallest] + ss   #ss.append(smallest)
    return ss

 

 

 

 

 

 

 

2. 삽입정렬 (Insertion sort)

 

 

 

2-1. insertion : insert 함수를 이용해 새로운 값을 리스트에 삽입

insertion 알고리즘

insertionSort 재귀 버전

def insertionSort(xs):
    if xs != []:
        return insert(xs[0], insertionSort(xs[1:]))
    else:
        return []

print(insertionSort([4,5,2,6,8,7]))

 

 

 

insertionSort 꼬리재귀 버전

def insertionSort_l(xs):
    def loop(xs, ss):
        if xs != []:
            return loop(xs[1:], insert(xs[0], ss))
        else:
            return ss

    return loop(xs, [])

print(insertionSort_l([4,5,2,6,8,7]))
print(insertionSort_l([3,2,1,5,4]))

 

 

 

 

insertionSort while 루프 버전

def insertionsSort(xs):
    ss = []
    while xs != []:
        xs, ss = xs[1:], insert(x[0], ss)
    return ss

print(insertionSort([4,5,2,6,8,7]))

 

 

 

 

insertionSort for 루프 버전

def insertionSort(xs):
    ss = []

    for i in xs: # i는 리스트 xs의 값들을 차례대로 가짐
       ss = insert(i, ss) 

    return ss

print(insertionSort([4,5,2,6,8,7]))

 

 

 

 

2-2. insert : 리스트 정렬

 

 

insert 알고리즘

 

 

insert 재귀 버전

def insert(x, ss):
    if ss != []:
        if x <= ss[0]:
            return [x] + ss            
        else:
            return [ss[0]] + insert(x, ss[1:])
    else:
        return [x]
print(insert(6,[2,4,5,7,8]))

 

 

insert 꼬리재귀 버전

def insert(x, ss):
    def loop(ss, left):
        if ss != []:
            if x <= ss[0]:
                return left + [x] + ss

            else:
                return loop(ss[1:], left + [ss[0]] )

        else:
            left.append(x)
            return left
    return loop(ss, [])
print(insert(6,[2,4,5,7,8]))

 

 

insert while 루프 버전

def insert(x, ss):
    left = []
    while ss != []:
        if x <= ss[0]:
            return left + [x] + ss

        else:
            left += [ss[0]]
            ss = ss[1:]


    left.append(x)
    return left
print(insert(6,[2,4,5,7,8]))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 합병정렬 (Merge sort)

 

 

합병정렬 알고리즘

 

 

 

 

 

 

 

#5-8

def merge_f(left, right):
    def loop(left, right, ss):
        if left != [] and right != []:
            if left[0] <= right[0]:
                ss.append(left[0])
                return loop(left[1:], right, ss)

            else:
                ss.append(right[0])
                return loop(left, right[1:], ss)

        else:
            return ss + left + right

    return loop(left, right, [])

print(merge_f([2,4,6], [1,3,5,7]))


# 5-9
 
def merge_w(left, right):
    ss = []
    while left != [] and right != []:
        if left[0] <= right[0]:
            ss.append(left[0])
            left = left[1:]
        else:
            ss.append(right[0])
            right = right[1:]

    return ss + left + right

print(merge_w([2,4,6], [1,3,5,7]))


#5-10

def partition(pivot, xs):
    def loop(xs, ls, rs):
        if xs != []:
            if pivot <= xs[0]:
                return loop(xs[1:], ls, [xs[0]] + rs)
            else :
                return loop(xs[1:], [xs[0]] + ls, rs)
        else:
            return ls, rs
    return loop(xs, [], [])

print(partition(5,[7,2,1,9,4]))



#5-11
def partition(pivot, xs):
    ls, rs = [], []
    while xs != []:
        if pivot <= xs[0]:
            rs, xs = [xs[0]] + rs, xs[1:]
            
        else:
            xs, ls = xs[1:], [xs[0]] + ls

    return ls, rs

print(partition(5, [7,2,1,9,4]))
        

#5-12
def partition(pivot, xs):
    ls, rs = [], []
    for x in xs:
        if pivot <= x:
            rs= rs + [x]
        else:
            ls = ls + [x]
    return ls, rs
print(partition(5, [7,2,1,9,4]))


#6-1   문제점 확인하기 !!!!
def bin_search_OX(ss,x):
    mid = len(ss) // 2
    return ss != [] and \
           (x == ss[mid] or \
           (x < ss[mid] and  bin_search_OX(ss[mid:], x)) or \
           (x > ss[mid] and bin_search_OX(ss[:mid], x)) )

print(bin_search_OX([1,2,3], 3))
print(bin_search_OX([1,2,3,4], 6))


#연습문제 5-10

def updown(ns):
    if ns != []:
        if ns[0] % 2 == 0:
            return [ns[0]//2] + updown(ns[1:])
        else:
            return [ns[0]*2] + updown(ns[1:])
    else:
        return []

print(updown([4,5,6,5,3,7,6,2,1,3,2]))
print(updown([]))


def updown(ns):
    def loop(xs, ns):
        if ns != []:
            if ns[0] % 2 == 0:
                return loop(xs + [ns[0]//2], ns[1:])
            else:
                return loop(xs + [ns[0]*2], ns[1:])
        else:
            return xs
    return loop([], ns)

print(updown([4,5,6,5,3,7,6,2,1,3,2]))
print(updown([]))


def updown(ns):
    xs = []
    while ns != []:
        if ns[0] % 2 == 0:
            xs, ns = xs + [ns[0]//2], ns[1:]

        else:
            xs, ns = xs + [ns[0]*2], ns[1:]

    return xs

print(updown([4,5,6,5,3,7,6,2,1,3,2]))
print(updown([]))


def updown(ns):
    xs = []
    for x in ns:
        if x % 2 == 0:
            xs = xs + [x//2]
        else:
            xs = xs + [x*2]
    return xs

print(updown([4,5,6,5,3,7,6,2,1,3,2]))
print(updown([]))