before the algorithm test

tree의 순회방법과 탐색 알고리즘

from 자료구조.btree.TNODE import tnode

F = tnode('F', None, None)
E = tnode('E', None, None)
D = tnode('D', None, None)
B = tnode('B', D, E)
C = tnode('C', F, None)
A = tnode('A', B, C)

# 순회 3가지 전위순회 , 중위순회, 후휘순회, 레벨순위
def preorder(node):
    if node is not None:
        print(node.data, end=" ")
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.data, end=" ")
        inorder(node.right)

def postorder(node):
    if node is not None:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end=" ")

def leveltrival(node):
    list = []
    list.append(node)
    while len(list) != 0:
        node = list.pop(-1)
        if node is not None:
            print(node.data, end=" ")
            list.insert(0, node.left)
            list.insert(0, node.right)

# 트리의 높이를 반환하는 함수, 트리의 터미널 노드의 갯수를 반환하는 함수, 트리의
def count_node(node):
    if node is None:
        return 0
    else:
        return 1 + count_node(node.left) + count_node(
            node.right)  # if node is not None return sum of left and right node count

def count_leaf(node):
    if node is None:
        return 0
    elif node.left is None and node.right is None:
        return 1
    else:
        return 0 + count_leaf(node.left) + count_leaf(node.right)  #

def getHeight(node):
    if node is None:
        return 0
    Lhight = getHeight(node.left)
    Rhight = getHeight(node.right)

    if Lhight > Rhight:
        return 1 + Lhight
    else:
        return 1 + Rhight

print("result of preoder:")
preorder(A)
print()
print("result of inorder:")
inorder(A)
print()
print("result of postorder:")
postorder(A)
print("height of this tree: %d" % (getHeight(A)))
print("count of node", count_node(A))
print("count of terminal node:", count_leaf(A))

Maxheap

import random

class Maxheap:
    def __init__(self):
        self.heap = []
        self.heap.append(0)

    def size(self):
        return len(self.heap) - 1

    def isEmpty(self):
        return self.size() == 0

    def display(self, string="maxheap"):
        print(string, self.heap[1:])

    def parent(self, index):
        return self.heap[index // 2]

    def Left(self, index):
        return self.heap[index * 2]

    def right(self, index):
        return self.heap[index * 2 + 1]

    def insert(self, data):

        self.heap.append(data)
        index = self.size()
        while index != 1 and data > self.parent(index):
            self.heap[index] = self.parent(index)
            index = index // 2

        self.heap[index] = data

    def delete(self):
        if not self.isEmpty():
            parent = 1
            child = 2
            last = self.heap[self.size()]
            hroot = self.heap[1]

            while child < self.size():

                if self.Left(parent) < self.right(parent):
                    child += 1
                if last > self.heap[child]:
                    break
                self.heap[parent] = self.heap[child]
                parent = child
                child = child * 2
        self.heap[parent] = last
        self.heap.pop(-1)
        return hroot

mh = Maxheap()
for i in range(10):
    mh.insert(random.randrange(0, 10))
mh.display()
print("delete:", end=" ")
for i in range(3):
    print(mh.delete(), end=" ")
mh.display()

이진 탐색트리 삭제연산과 insert연산 중심으로 공부할 것

from 자료구조.bsttest.bstNODE import bnode

A = bnode(35, 'A')
B = bnode(18, 'B')
C = bnode(68, 'C')
D = bnode(7, 'D')
E = bnode(26, 'E')
F = bnode(99, 'F')
G = bnode(3, 'G')
H = bnode(12, 'H')
I = bnode(22, 'I')
J = bnode(30, 'J')

list = [B, C, D, E, F, G, H, I, J]

# bst에서 값을 찾는 함수 순환을 이용
def search_bst(node, key):
    if node == None:  # 탐색트리 안에 같은 값이 존재하지 않는경우
        return None
    if key == node.key:  # 같은 키를 찾은경우
        return node
    elif key > node.key:
        search_bst(node.right, key)  # 키값이 비교하는 노드보다 큰경우 오른쪽 자식을 기준으로 함수 다시 호출
    else:
        search_bst(node.left, key)  # 키값이 비교하는 노드보다 작은경우 왼쪽을 자식을 기준으로 함수 다시 호출

# bst에서 값을 찾는함수 반복문을 사용함
def search_bst_iter(node, key):
    while node is not None:  # while문이 끝나면 같은 키를 찾지 못한거임
        if node.key == key:  # 찾음
            return node
        if node.key < key:  # 키가 더 큰경우
            node = node.right  # 오른쪽 자식을 기준으로 변경
        else:
            node = node.left  # 왼쪽 자식을 기준으로 변경
    return None

# 최대값을 찾는 함수
def find_max(node):
    while node != None and node.right != None:  # node의 오른쪽 자식이 None일때까지 이동
        node = node.right  # 오른쪽 자식이 None일때 반복문이 종료됨
    return node

# 최소값을 찾는 함수
def find_left(node):
    while node != None and node.left != None:  # 왼쪽 자식이 None일때 반복문이 종료된다.
        node = node.left
    return node

def insert(root, node):
    if root.key < node.key:  # 노드의 키값이 더 작은경우
        if root.right is None:  # 노드의 오른쪽 자식이 비어있는경우 그자리에 삽입
            root.right = node
            return True  # 삽입에 성공하면 True를 반환한다.
        else:
            insert(root.right, node)  # 비어있지 않으면 오르쪽 자식을 기준으로 함수 다시 호출
    elif root.key > node.key:  # 찾으려는 키값이 더 작은경우
        if root.left is None:  # 왼쪽 자식이 비어 있는 경우에서는 그자리에 삽입한다.
            root.left = node
            return True
        else:
            insert(root.left, node)  # 왼쪽 자리가 비어있지 않은 경우 왼쪽 자식을 기준으로 함수 제호출
    else:
        return False  # 같은 키값을 가진 노드가 있는 경에는False삽입이 불가능하고 중복을 허용하지 않는다.

def delete_bst_case1(root, node, parent):  # 자식이 없는 단말노드의 삭제

    if parent is None:  # 부모 노드가 앖다는 건 parent가 제일 상단의 root라는 소리고 빈 트리가 된다.
        root = None
    else:
        if parent.left == node.key:  # 부모의 어느쪽 자식인지 파악하고 바로 삭제
            parent.left = None  # 링크를 공백으로 바꾼다.
        else:
            parent.right = None
    return root

def delete_bst_case2(root, node, parent):
    if parent.right == node:
        if node.right is None:
            parent.right = node.left
        else:
            parent.right = node.right
    else:
        if node.right is None:
            parent.left = node.left
        else:
            parent.left = node.right
    return root

def delete_bst_case3(root, node, parent):
    succ = node.right
    succp = node

    while succ.left != None:
        succp = succ
        succ = succ.left

    if succp.left == succ:
        succp.left = succ.right
    else:
        succp.right = succ.right
    node.key = succ.key
    node.value = succ.value
    node = succ

    return root

def delete(root, key):
    # 트리가 공백인경우
    if root is None:
        return None

    parent = None
    node = root
    while node.key != key and node is not None:
        parent = node
        if node.key < key:
            node = node.right
        else:
            node = node.left
    if node == None:
        return None
    if node.right is None and node.left is None:
        delete_bst_case1(root, node, parent)
    elif node.right is None or node.left is None:
        delete_bst_case2(root, node, parent)
    else:
        delete_bst_case3(root, node, parent)

def display(root):
    if root is not None:
        display(root.left)
        print(root.key, end=" ")
        display(root.right)

def count_node(node):
    if node is None:
        return 0
    else:
        return 1 + count_node(node.left) + count_node(node.left)

def search_node(node, key):
    if node == None:
        return None
    if node.key == key:
        return node
    elif node.key > key:
        search_node(node.left, key)
    elif node.key < key:
        search_node(node.right, key)

for i in range(9):
    insert(A, list[i])
display(A)
print()
for i in range(3):
    delete(A, list[i].key)
display(A)

class BstMap():
    def __init__(self):
        self.root = None

    def isEmpty(self):
        return self.root is None

    def clear(self):
        self.root = None

    def size(self):
        return count_node(self.root)

    def search(self, key):
        return search_node(self.root, key)

    def search_value(self, key):
        node = search_node(key)
        return node.value

    def findMax(self):
        return find_max(self.root)

    def findMin(self):
        return find_left(self.root)

    def insert(self, key, value=None):
        newNode = bnode(key, value)
        if self.isEmpty():
            self.root = newNode
        else:
            insert(self.root, newNode)

    def delete(self, key):
        if self.isEmpty():
            return None
        else:
            delete(self.root, key)

    def display(self):
        display(self.root)

bstmap = BstMap()
data = [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
print()
for i in data:
    bstmap.insert(i)
bstmap.display()
for i in range(1,6):
    bstmap.delete(data[i])
print()
bstmap.display()

이진탐색에서 주의해서 보아야 하는 것이

def delete_bst_case3(root, node, parent):
    succ = node.right
    succp = node

    while succ.left != None:
        succp = succ
        succ = succ.left

    if succp.left == succ:
        succp.left = succ.right
    else:
        succp.right = succ.right
    node.key = succ.key
    node.value = succ.value
    node = succ

    return root

노드가 양쪽의 자식을 가지고 있는 상황에서 이를 삭제하기위해서 삭제하려는 노드의 왼쪽자식의 오른쪽 끝 자손이나 오른쪽 자식에서 가장 왼쪽 자손을 후계자로 사용한다.

그래프

# 인접향렬로 표현하 그래프이다.
vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
adjlist = [[0, 1, 1, 0, 0, 0, 0, 0],
           [1, 0, 0, 1, 0, 0, 0, 0],
           [1, 0, 0, 1, 1, 0, 0, 0],
           [0, 1, 1, 0, 1, 0, 0, 0],
           [0, 0, 1, 0, 0, 0, 1, 1],
           [0, 0, 0, 1, 0, 0, 0, 0],
           [0, 0, 0, 0, 1, 0, 1, 0],
           [0, 0, 0, 0, 1, 0, 1, 0],
           [0, 0, 0, 0, 0, 1, 1, 0]]
# 인점 집합으로 표현한 집합이다 집합내부의 요소들은 딕셔너리 형태로 표현되는데 내부의 요소들은 딕셔너리 형태이다.
adjset = {'A': set(['B', 'C']),
          'B': set(['A', 'D']),
          'C': set(['A', 'D', 'E']),
          'D': set(['B', 'C', 'F']),
          'E': set(['C', 'G', 'H']),
          'F': set(['D']),
          'G': set(['E', 'H']),
          'H': set(['E', 'G'])}

def DFS(graph, start, visited=set()):
    if start not in visited:  # start가 아직 방문한 집합에 포함도지 않는다면
        visited.add(start)  # 집합안에 start를 추가해서 이미 방문한것을 표시한다.
        print(start, end=" ")  # visited안에 넣고 이를 출력한다.
        neighborhood = graph[start] - visited  # 현재 정점의 이웃한 vertex들 중 이미 방문한 정점들을 제외하고 neighborhood를 만든다.
        for v in neighborhood:
            DFS(graph, v, visited)  # 순횐를 통해서 이웃주민들을 호출하는데 이때 각 이웃 주민의 첫번재 요소 부터 출력이 되니까 DFS가 된다.

DFS(adjset, 'A', set())

def BST(start, graph):
    visited = set([start])  # 시작점으로 주어진 정점을 방문한 리스트에 추가한다.
    que = [start]  # 너비 우선 탐색을 위해서 큐를 구현하는데 처음에 주어진 변수를 enqeue해서 초기화한다.
    while len(que) != 0:  # 큐의 길이가 0이 아닐때 까지
        vertex = que.pop(-1)  # 큐에 저장되어있던 정점을 뺀다.
        print(vertex, end=' ')  # 정점을 출력한다.
        neighborhood = graph[vertex] - visited  # 이미 방문한 정점을 제외하고 이웃 집합을 만든다.
        for v in neighborhood:  # 반복문을 통해서 이미 방문한 요소들을 추가한다.
            visited.add(v)  # 방문합 집합에 정점을 추가하는 동시에 큐에 정점들을 추가한다.
            que.append(v)

print()
BST('A', adjset)

# 신장 트리를 만드는 알고리즘인데 깊이 우선 탐색이나 너비 우선탐색을 할 때 과정을 그대로 출력하면 구현이 쌉 가능하다
def BstST(start, graph):
    visited = set([start])
    que = [start]
    while len(que) != 0:
        vertex = que.pop(0)
        neighborhood = graph[vertex] - visited
        for v in neighborhood:
            print("(", vertex, ",", v, ")", end=" ")  # 간선을 반복문을 통해서 출력한다.
            visited.add(v)
            que.append(v)

print()
BstST('A', adjset)

def dfs_cc(graph, vertex, color, visited):#열결성분검사에서 사용되는되는 것
    if vertex not in visited:#정점이 아직 방문되지 않았다면
        visited.add(vertex)#방문된 정점 추가
        color.append(vertex)#라벨리스트에 추가
        neighborhood = graph[vertex] - visited#이미 방문한 요소들 제거
        for v in neighborhood:
            dfs_cc(graph, v, color, visited)#순환호출로 스택 구현
    return color#마지막에 정점들이 저장된 리스트를 반환한다.

my = {'A':set({'B','C'}), 'B':set(['A']), 'C':set(['A']), 'D':set(['E']), 'E':set(['D'])}

def find_connected_component(graph):
    visited = set([])#비어 있는 방문 리스트 생성
    colorlist = []

    for vertex in graph:
        if vertex not in visited:
            colorlist.append(dfs_cc(graph, vertex, [], visited))#한번 호출된게 반환되면 이어진 요소들은 리스트에 담겨서 반환된다.
            #이미 방문된 정점들은 위의 조전문에서 걸려서 실행이 되지 않는다.
    print(len(colorlist))

find_connected_component(my)

진은아 시험 전에 보고 외

# 인접행렬로 구현한 가중치 그래프j
vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
weightlist = [[None, 29, None, None, None, 10, None],  # a
              [29, None, 16, None, None, None, 15],  # b
              [None, 16, None, 12, None, None, None],  # c
              [None, None, 12, None, 22, None, 18],  # d
              [None, None, None, 22, None, 27, 25],  # e
              [10, None, None, None, 27, None, None],  # f
              [None, 15, None, 18, 25, None, None]]

# 그래프내에 존재하는 모든 간선의 가중치의 합
def weight_sum(graph):
    sum = 0  #
    for i in range(len(graph)):
        for e in range(i + 1, len(graph)):  # 여기에서도 포문의 범위가 중요한데 i+1!! 기억할 것
            if graph[i][e] is not None:  # 간선이 존재한다면
                sum += graph[i][e]  # 합에 더함
    return sum

# 그래프 내의 모든 간선을 출력하는 함수
def printAlledges(vertex, graph):
    for i in range(len(vertex)):
        for e in range(i + 1, len(vertex)):  # 이 포문의 범위가 중요한데 그 이유는 첫번째 반복문의 i
            # 보다 하나 앞에서 시작해서 상부 삼각형이 출력됨 따라서 양방형 간선이 한번만 출력됨
            if graph[i][e] is not None:
                print("(%c, %c, %d)" % (vertex[i], vertex[e], graph[i][e]), end=" ")

print()
print("sum of the weight", weight_sum(weightlist))
printAlledges(vertex, weightlist)
print()

weightset = {'A': set([('B', 29), ('F', 10)]),
             'B': set([('A', 29), ('C', 16), ('G', 15)]),
             'C': set([('B', 16), ('D', 12)]),
             'D': set([('C', 12), ('E', 22), ('G', 18)]),
             'E': set([('D', 22), ('F', 27), ('G', 25)]),
             'F': set([('A', 10), ('E', 27)]),
             'G': set([('B', 15), ('D', 18), ('E', 25)])}

# 인접 리스트를 이용한 가중치 그래프의 가중치의 합

def weight_sum2(graph):
    sum = 0
    for i in graph:  # 집합의 요소에서 딕셔너리의 키값이 반복문으로 출력됨
        for e in graph[i]:  # 딕셔너리의 키값을 이용해서 정점의 인접 튜플을 하나씩 출력
            sum += e[1]  # 가중치는 튜플에서 두번째 요소임

    return sum // 2

def printAllweightedEdges(graph):
    for i in graph:
        for e in graph[i]:
            print("(%s, %s, %d)" % (i, e[0], e[1]), end=" ")

print("sum of weight", weight_sum2(weightset))
printAllweightedEdges(weightset)

parent = []
set_size = 0

def init_set(nSets):
    global parent, set_size  # 전역 변수를 사용하겠다고 선언
    set_size = nSets  # 파라민터로 전달된 집합의 사이즈를 저장
    for i in range(nSets):  # set의 사이즈 만큼 반복
        parent.append(-1)  # 부모를 나타내는 집합에 -1로 초기화

def find(id):  # 집합의 root노드의 id를 반환하는 함수
    while parent[id] >= 0:  # 노드의 자식이 -1이라면 자식이 위에 부모가 없는거고 그러면 정점 루트 노드임
        id = parent[id]  # 자식의 id를 부모의 id로 바꾼다.
    return id

def union(s1, s2):  # s1와 s2를 연결해 하나의 집합으로 만드는 함수인데 s2가 부모이다.
    global set_size
    parent[s1] = s2  # s1의 부모 id로 s2를 등록함
    set_size = set_size - 1  # 두개의 집합이 합쳐져서 집합의 총 갯수가 줄어듦

def MSTKruskal(vertex, adjlist):
    vertexSize = len(vertex)  # 정점의 갯수 저장
    init_set(vertexSize)  # 정점의 갯수만큼 부모 리스트 초기화
    eList = []  # 간선이 저장될 리스트

    for i in range(vertexSize - 1):  # 그냥 외워
        for j in range(i + 1, vertexSize):  # 상부 삼각행렬
            if adjlist[i][j] != None:  # 인접 행렬
                eList.append((i, j, adjlist[i][j]))  # 간선을 저장하는 리스트에 정점의 정보와 가중치를 튜플로 저장

    eList.sort(key=lambda e: e[2], reverse=True)  # 저장한 튜플의 마지막 요소인 가중치로 내림차순 정렬 갈수록 작아짐
    edgeAccepted = 0  # 간선의 수
    sum = 0
    while (edgeAccepted < vertexSize - 1):  # 신장트리는 간선의 갯수가 정점의 수 -1 개임
        e = eList.pop(-1)  # 가중치가 가장 작은 간선을 꺼냄
        uset = find(e[0])  # 간선을 연결하는 정점 1 집합의 대표 정점을 반환
        vset = find(e[1])  # 간선으로 연결된 정점 2 집합의 대표 정점을 반환

        if uset != vset:  # 두 정점이 속한 대표 정점이 다르다면 이는 다른 집합에 속한 정점이라는 것임
            sum += e[2]
            print("간선 추가 : (%s, %s, %d)" % (vertex[e[0]], vertex[e[1]], e[2]))
            # 두집합을 하나로 합침
            union(uset, vset)
            edgeAccepted += 1  # 간선이 하나 추가됨
    return sum

print()
min = MSTKruskal(vertex, weightlist)
print(min)

INF = 9999

def choose_vertex(dist, found):  # 최소 정점을 찾는 함수
    min = INF  # 최소값 맥스로 초기화
    minpos = -1
    for i in range(len(dist)):  # 정점의 갯수만큼
        if dist[i] < min and found[i] == False:  # 저장된 최단거리중 가장 작고 아직 방문하지 않은 정점 선택
            min = dist[i]
            minpos = i
    return minpos  # 가장 작은 정점의 인덱스 반환

def shortest_path_dijkstra(vertex, adjlist, start):
    vsize = len(vertex)
    dist = list(adjlist[start])
    path = [start] * vsize
    found = [False] * vsize
    dist[start] = 0

    for i in range(vsize):  # 정점의 갯수만큼 반복
        print("step%2d:" % (i + 1), dist)  # 각단계의 최단거리 출력
        u = choose_vertex(dist, found)  # 방문하지 않는 정점들 중 가장 최소 정점 선택
        found[u] = True  # 최소 정점을 방문한것으로 바꿈

        for w in range(vsize):  # 모든 정점에 대해서 반복
            if not found[w]:  # 방문하지 않은 노드에 있다면
                if dist[u] + adjlist[u][w] < dist[w]:  # 직접가는 경로보다 위에서 선택한 제일 작은 경로를 거쳐서 가는 것이 더 짧다면
                    dist[w] = dist[u] + adjlist[u][w]  # 갱신
                    path[w] = u  # 이전 노드를 저장
    return path

vertex2 = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

weight = [[0, 7, INF, INF, 3, 10, INF],
          [7, 0, 4, 10, 2, 6, INF],
          [INF, 4, 0, 2, INF, INF, INF],
          [INF, 10, 2, 0, 11, 9, 4],
          [3, 2, INF, 11, 0, 13, 5],
          [10, 6, INF, 9, 13, 0, INF],
          [INF, INF, INF, 4, 5, INF, 0]]
print("Shortest_path_dijkstra algorithm")
start = 0
path = shortest_path_dijkstra(vertex2, weight, start)

for end in range(len(vertex)):
    if end != start:
        print("[최단경로 %s -> %s] %s" % (vertex2[start], vertex2[end], vertex2[end]), end=" ")
        while (path[end] != start):
            print("<- %s" % (vertex[path[end]]), end='')
            end = path[end]
        print("<- %s" % (vertex[path[end]]))

def floyd(vertex,weight):
    vsize = len(vertex)
    copy = list(weight)
    for i in range(weight):
        copy[i] = list(weight[i])
    for k in range(vsize):
        for i in range(vsize):
            for j in range(vsize):
                if(copy[i][k] + copy[k][j] < copy[i][j]):
                    copy[i][j] = copy[i][k] + copy[k][j]
        print(copy)

병합정렬

need_list = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

sorted = [35, 4, 6245, 62, 442, 341, 35, 255, 2, 3]
#정렬될 원소들이 임시로 저장되어질 함수

def merge(list, left, mid, right):
#병합을 진행하는 함수

    global sorted
#전역변수 사용설정

    leftIndex = left
 #왼쪽 리스트의 첫번째 원소를 가르키는 리스트
    sortedIndex = left
#정렬될 원소들이 들어갈 리스트를 현재 함수에서 가장 작은 left로 초기화해서 사용한다.
    rightIndex = mid + 1
#오른쪽 리스트의 가장 첫번째 원소를 가르키기 위해서 mid +1을 사용함

    while leftIndex <= mid and rightIndex <= right:
#둘다 반으로 나눈 범위를 넘지안을때 까지 실행함.
        if list[leftIndex] <= list[rightIndex]:
#만일 왼쪽 리스트의 값이 오른쪽 리스트 보다 작다면
            sorted[sortedIndex] = list[leftIndex]
#왼쪽 리스트의 값을 정렬된 리스트에 추가하고
            sortedIndex, leftIndex = sortedIndex + 1, leftIndex + 1
#왼쪽 그리고 정렬된 리스트의 인덱스의 값을 증가시킴
        else:
            sorted[sortedIndex] = list[rightIndex]
# 오늘쪽 리스트의 값이 더 작으면 정렬된 리스트에 오른쪽 값을 삽입한다.
            sortedIndex, rightIndex = sortedIndex + 1, rightIndex + 1
#오르쪽 인덱스와 정렬된 리스트의 값을 증가

    if left > mid:
#왼쪽이 mid보다 크다는거는 오른쪽리스트 보다 작은 값이 많아서 이미 정렬된 리스트에 다 들어갔다는 거임

        #오른쪽 리스트에 남은 값들을 정렬된 리스트에 삽입한다.
        sorted[sortedIndex: sortedIndex + right - rightIndex + 1] = list[rightIndex:right]
#오른쪽 인덱스부터 끝까지
        #리스트에 삽입된 인덱스부터 right - rightIndex:오른쪽에 남은 인덱스 만큼

    else:
        sorted[sortedIndex: sortedIndex + mid - leftIndex + 1] = list[leftIndex:mid + 1]
#왼쪽리스트에서 끝이 mid임
        #mid - leftIndex 왼쪽에 남은 인덱스크기임
    list[left:right + 1] = sorted[left:right + 1]
#왼쪽 끝에서 오른쪽 끝까지 전부다 복사를 실시하는데 항상 인덱싱할 때는 끝에 1을 더해준다.

def mergeSort(list, left, right):
    if left < right:#왼쪽 값이 오른쪽 값보다 클때라는 거는 나누기해서 0이 나오기 전까지임
        mid = (left + right) // 2#중앙값을 구한다.
        mergeSort(list, left, mid)#왼쪽부분의 리스트에 대해서 재귀적으로 호출한다.
        mergeSort(list, mid + 1, right)#오른쪽에 대해서 재귀적으로 호출하기 위해서 사용
        merge(list, left, mid, right)#병합을 실시한다.

print("before sorting:", need_list)

mergeSort(need_list, 0, len(need_list) - 1)
print("after sorting:", need_list)

quick Sorting