뇌를 자극하는 알고리즘책 공부하면서 정리.

• 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행.
• 시간복잡도가 O(n^2) 으로 매우 느리지만 코드가 단순함.
• 최선의 경우: 이미 자료가 정렬되어있는 경우. 자리교환이 이루어지지 않음
• 최악의 경우: 자료가 역순으로 정렬되어있는 경우. n(n-1)/2 만큼 (비교/자리교환)이 이루어짐.

• 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입하는 방법으로 수행.
• 버블정렬만큼의 시간복잡도를 가짐

• 분할 정복(Divide and Conquer)에 기반한 정렬알고리즘.
• 순서

1. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 상관없이 기준 요소 왼편에, 큰 값은 오른편에 위치시킨다.
2. 이렇게 나눠진 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택하고 분할한다.
3. 1, 2의 과정을 더이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 된다.

• 일반적으로 반복되는 분할과정을 함수로 만들어서 이를 재귀 호출을 통하여 구현.
• 따라서 재귀 호출의 깊이 + 데이터 집합을 나누기 위한 비교 회수가 성능의 근거가 된다.
• 시간복잡도: n(각 재귀 호출단계의 비교횟수) x log2n(재귀호출깊이) = nlog2n
• 최악의 경우: 이미 정렬되어이 있는 경우(매 재귀 호출에서의 기준요소가 최소값이 되는 경우 좌,우로 분할되지 않는다.) 이 경우에는 재귀 호출 깊이가 n이 되기 때문에 O(n^2)가 된다.

• 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교하여 데이터를 찾는 알고리즘.

• 정렬된 데이터 집합에서 사용할 수 있는 방법.
• 순서

1. 데이터 집합의 중앙에 있는 요소를 고른다.
2. 중용 요소의 값과 찾고자 하는 목표값을 비교한다.
3. 목표 값이 중앙 요소의 값보다 작으면 중앙을 기준으로 데이터 집합 왼편에 대해 검색, 크면 오른편에 대해 검색.
4. 찾을 때까지 1~3을 반복.

• 시간복잡도는 O(logN)
• 문제점: 정렬된 데이터 집합에서는 매우 빠른 성능을 보이지만, 구현 특성상 고정된 데이터 집합에 대하서만 사용가능하다. ( 동적으로 크기가 달라지면 적용 불가 )

• 이진 탐색트리는 '이진 탐색'을 위한 트리 이자, 탐색을 위한 '이진 트리'이다.
• 이진 탐색이 고정된 데이터 집합에서만 적용가능한 알고리즘이었는데 이런 딜레마를 해결해주는 자료구조.
• "왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다" 이 조건으로 이진 탐색 트리를 생성.
• 탐색: 찾고자 하는 값을 root와 비교하여 root보다 작으면 left, 크면 right node와 비교 하는 방식으로 탐색.
• 문제점: 기형적으로 자라나는 트리형태가 될 수 있다. 이렇게 되면 탐색의 효율이 떨어짐. (레드블랙트리로 해결)

• 이진 탐색 트리를 균형있게 만들어주어서 탐색 효율을 높이기 위한 알고리즘.
• 균형을 유지하는 비결?

1. 모든 노드는 빨간색 아니면 검은색이다.
2. 루트 노드는 검은색이다.
3. 잎 노드는 검은색이다
4. 빨간 노드의 자식들은 모두 검은색이다 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.
5. 로트 노드에서 모든 잎 노드 사이에 있는 검은색 노드 수는 동일하다.

• 노드의 추가, 삭제가 이루어지면 위 조건을 토대로 트리가 균형있게 변형된다.

• First-In First-Out의 큐에 우선순위 속성을 준 알고리즘. (우선순위에 따라 out의 순서가 바뀜)
• 밑에 힙 으로 구현하기 위해 먼저 소개.

• 힙 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리.
• 완전 이진 트리이기 때문에 최고 깊이를 제외한 모든 깊이의 노드들이 완전히 채워져 있음.
• 힙 조건: "힙에서 가장 작은 데이터를 갖는 노드는 루트 노드이다." (min heap 경우)
• 노드 삽입

1. 힙의 최고 깊이에 노드 추가
2. 부모 노드와 비교하여 자신이 더 작으면 부모와 위치 변경.
3. 더이상 위치 변경이 이루어지지 않을 때 까지 2번 반복.

• 최소값 삭제

1. 로트 노드 삭제
2. 힙의 최고 깊이에 있는 노드를 root로 이동.
3. 자식과 비교하여 자식이 더 작으면 위치 변경.
4. 더이상 위치 변경이 이루어지지 않을 때 까지 3번 반복.

• 구현: 배열로 구현하면 빠름

1. k번 인덱스에 위치한 노드의 양쪽 자식 노드 인덱스: 2k+1, 2k+2
2. k번 인덱스에 위치한 노드의 부모노드 인덱스: (k-1)/2