Algorithms

0. Intro- 이번 7 챕터에서는 quicksort, 퀵정렬에 대해서 알아보고자 한다. 1. Quicksort(퀵정렬)- quicksort(퀵정렬)은 2-3에서 배웠던 mergesort(병합정렬)과 비슷하다.- divide-and-conquer(분할정복)알고리즘을 이용한다.- 평균적으로 매우 빠른 수행 속도를 보여주기 때문에 quicksort 라고 불린다. 2. Quicksort의 알고리즘 - QuickSort의 핵심은 분할(divide)하는 과정이다. - QuickSort는 배열을 작은 부분으로 쪼개서 정렬하는 방식으로 작동하며, 다음과 같은 과정을 거친다. i) Pivot 선택- 배열에서 임의의 기준이 되는 Pivot 요소를 선택한다.- Pivot을 선택하는 방식은 크게 4가지가 존재한다. a) ..

0. Intro- 우리는 6-2, 6-3 에서 max_heapify()와 build_max_heap()을 구현해보았다.- 두 함수를 이용하여 배열을 정렬하는 알고리즘을 한번 구현해보자(Heapsort) 1. Heapsort?- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법을 의미함- Heapsort의 알고리즘을 나타내면 다음과 같다. i) 정렬해야할 n개의 데이터들을 Max-Heap을 만든다.ii) root-node(최댓값을 가장 마지막 node와 바꾼다.iii) 그 후 heap에서 pop()을 한 후 queue에 enqueue한다.iv) 그 후 max_heapify()를 root_node에서 실행한다.v) ii)~iv)까지를 계속 반복한다. (heap이 empty가 될 때까지) - heaps..

0. Review- 이번 챕터에서는 Max-Heap을 만들기 위해 6-2에서 구현했던 max_heapify()를 이용하고자 한다.- 이를 leaf-node(자식이 없는 노드)부터 시작하여 root-node까지 거슬러 올라가 max_heapify()를 호출하면 된다.- 이때 leaf-node는 heap에서 다음과 같다. A[n//2 + 1: ] 까지에 해당한다. - leaf-node에서 max_heapify()를 호출하더라도 변함없기 때문에 구현할 코드에선 A[n//2] ~A[1]까지만 호출하는 것으로 구현하였다. 1. Code1.1. max_heapify()def max_heapify(arr,i): left_node = 2*i right_node = 2*i+1 if (left_no..

0. Review- 6-1 에서 우리는 Heap을 알아가는 동안 Max-Heap에 대해서 알아보았다.- 이번 챕터에서는 Max-Heap을 유지하게 해주는 Max-Heapify 에 대해서 알아볼 것이다. 1. Max-Heapify- Max-Heapify 절차는 최댓값 힙 속성을 유지한다.- 입력값은 배열 A, 그리고 배열의 인덱스 i를 받는다.- Max-Heapify는 LEFT(i), RIGHT(i)로 시작하는 Heap들이 이미 Max Heap이라는 것을 가정한다. - 하지만 A[i]가 자식노드보다 작을 경우 Max-Heap을 만족하지 않는다.- 그래서 A[i]를 아래에 있는 노드로 계속 흘려보내면서 Max-Heap을 만족하게 한다.- 다음 그림은 Max-Heapify의 동작을 보여준다. - (a)상황을 ..