정렬

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..

1. Bubble Sort? - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘--> 인접한 2개의 노드를 비교하여 크기순으로 서로 교환을 해준다. 2. 더 자세히!- 버블 정렬은 인접된 두 노드, 즉 (첫 번째, 두번째),(두 번째, 세 번째),(세 번째,네 번째)... 이런 식으로마지막 노드를 비교하여 교환하면서 데이터를 정렬한다.- 그림을 보면 더 쉽게 이해가능하다.- 반대로 마지막 부터 시작으로 역순으로 버블이 움직여도 괜찮다.(CLRS에선 역순으로 움직인다.) 3. Code(Python)def bubble_sort(arr,n): for i in range(n): for j in range(n,i,-1): if arr[j]  4. Bubble Sort의 시간..

1. Introduction- 알고리즘은 다양하게 선택가능하다. - 예를들어 Insertion Sort는 Incremental method(증분 방법)을 사용한다.- 이번 챕터에선 분할 정복(divide and conquer) 이라는 설계 방법을 간단하게 다루게 된다. - 자세한 방법은 챕터 4때 알아보도록 하자. 2. Divide and Conquer(분할 정복)- 많은 유용한 알고리즘들은 재귀적(recursive) 구조를 가지고 있음.- 주어진 문제를 해결하기 위해, 이들은 스스로 한번 이상 호출하여 하위문제들을 해결함- 일반적으로 분할 정복(Divide & Conquer)을 따름- 문제를 원래 문제와 유사하지만 더 작은 크기의 여러 하위 문제로 나누고, - 하위 문제를 재귀적으로 해결한 뒤 이러한 ..

1. Introduction- 앞서 1-1 에 설명했던 Sorting Problem을 풀기위해 삽입 정렬(Insertion Sort)를 알아보자. 2. Insertion Sort- 적은 수의 요소를 정렬하는 데 효율적인 알고리즘- 카드를 한손에 들고 정렬하는 방식과 유사- 각 숫자를 적절한 위치에 삽입하는 방법을 의미함- 파이썬으로 해당 알고리즘을 구현한 걸 함께 살펴보자.(parameter는 2개 / 배열, 배열길이)def insertion_sort(A,n): for i in range(1,n): key = A[i] j = i-1 while j >=0 and A[j] > key: A[j+1] = A[j] j -=1 ..