1. 삽입정렬 알고리즘 코드 빈칸문제로 나온다
while 루프 버전
def insertion_sort(a) :
n = len(a)
for i in range(1,n):
j = i -1;
key = a[i]
while j >= 0 and a[j] > key :
a[j+1] = a[j]
j -= 1
a[j+1] = keyfor 루프 버전
def insertion_sort(a) :
n = len(a)
for i in range(1,n):
for j in range(i,0,-1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
쉘 정렬 4,2,7,1,9
리스트를 나눌 간격인 갭은 전체 리스트 길이 5 // 2 +1인 3으로 시작한다
{4,1}, {2,9}의 부분 리스트를 부분 정렬해 전체 리스트가 1,2,7,4,9가 되고
갭이 3//2 인 1이 되서 리스트 전체에 삽입 정렬을 해 리스트가 1,2,4,7,9로 정렬되고 갭이 1//2 로 0이 되 반복문을 탈출하고 정렬된 리스트를 리턴한다
퀵 정렬 정렬과정 4,2,7,1,9
피벗을 맨 왼쪽인 4로 잡고 low는 2부터 피벗보다 큰 값을 만날때까지 오른쪽으로, high는 9부터 피벗보다 작은 값을 만날때 까지 왼쪽으로 움직인다 low가7, high가 1일때 서로 값을 교환하고 low +1, high-1을 하면 리스트는 4,2,1,7,9가 되고
low와 high가 교차되었기에 pivot과 high의 값을 스왑해 리스트는 1,2,4,7,9가 되고 high인 4를 리턴한다
4를 기준으로 좌측 리스트 {1,2}와 우측 리스트 {7,9}가 나오게 되고 {1,2}와 {7,9}는 이미 정렬된 상태라 partition 함수 내 반복문을 돌고 나면 low = 2. high = 0이 되어 high와 left를 교환해도 정렬된 상태 그대로를 유지한다, {7,9}도 정렬된 상태 그대로를 유지하고 1,2,4,7,9 를 리턴한다
힙 정렬 정렬과정
먼저, 리스트의 a의 크기 n이 있을때 a[n//2]부터 a[1]번 인덱스까지 상향식으로 리스트 내에서 부모와 자식을 비교해 자식이 부모보다 크면 서로 교환하는
추가 메모리가 필요하지 않은 제자리 정렬인 downheap 연산을 수행하여 최대 힙을 생성한다,
a[N//2+1]∼a[N]에 대하여 downheap을 수행하지 않는 이유는 이 인덱스의 노드들 각각은 힙의 크기가1인 리프 노드기 때문이다.
위에 과정으로 생성된 최대힙에서 마지막 노드와 루트를 교환하여 최대값을 리스트의 마지막으로 보내고 힙의 크기를 1씩 감소시킨다
루트와 마지막 노드를 스왑한 최대힙 속성이 사라진 힙에 다시 downheap 연산을 수행하여 힙 속성을 만족하도록 조정한다.
이진탐색트리 삽입, 삭제, 코드
삽입연산
루트의 키와 삽입하는 키 k를 비교하는것으로 시작, 루트의 키가 k 보다 크면, 루트의 왼쪽 서브트리에서 k를 찾고,
작으면 루트의 오른쪽 서브트리에서 k를 찾는다, 이렇게 내려오다가 None을 만나면 그 자리에 값을 삽입하고, 이미 그 키값이 존재하면 value 값만 갱신하게 된다, 값을 삽입한 후에는 루트 방향으로 다시 거슬러 올라가면서 부모 노드와 재연결 한다
#삽입연산
def put(self, key, value):
self.root = self.put_item(self.root, key, value)
def put_item(self, node, key, value):
#n번째 노드가 없으면 생성
if node == None:
return Node(key,value)
# n번째 노드의 키값이
if node.key > key:
node.left = self.put_item(node.left, key, value)
elif node.key < key:
node.right = self.put_item(node.right, key, value)
#기존에 해당 키 값이 있으므로 값을 갱신
else:
node.value = value
return node
최솟값 삭제 - 루트 노드 부터 왼쪽 자식을 타고 내려가다 none을 만났을때 none을 자식으로 가진 노드n을 찾아내고
n의 오른쪽 자식c와 n의 부모 p를 연결한다
삭제 연산
자식이 없는 경우, 자식이 하나인 경우, 자식이 두개인 경우
자식이 없는 단말 노드의 경우에는 삭제될 노드 n의 부모가 n을 가리키는걸 none을 가리키게 변경한다
자식이 하나만 잇는 경우 삭제될 노드 n의 자식 p와 n의 부모 c를 연결한다
삭제될 노드 n이 두개의 자식을 가진 경우 n의 오른쪽 서브트리에서 제일 왼쪽 값 p를 찾아서 n의 자리에 복사하고, p의 오른쪽 자식과 p의 부모를 연결한다
#삭제 연산
def delete(self, k):
self.root = self.del_node(self.root,k)
def del_node(self, node, k):
if node == None:
return None
if node.key > k :
node.left = self.del_node(node.left, k)
elif node.key < k:
node.right = self.del_node(node.right, k)
else:
if node.right == None:
return node.left
if node.left == None:
return node.right
target = node #삭제될 노드
node = self.minimum(target.right)
node.right = self.del_min(target.right)
node.left = target.left
return node
삽입1
삽입2
삭제
