Kim'sWorlds

위상 정렬 (Topoligical Sort) DAG에 속해 있는 알고리즘  - 어떤 일을 하는 순서를 찾는 알고리즘 이다. - 1-> 2 이런 식의 그래프가 있다고 하면, - 2를 하기 전에 1을 먼저 해야 하는 알고리즘이다. - BFS와 비슷한 알고리즘 위의 그림을 예로 들겠다. A에서 D로 가고 싶다. 하지만 D를 가르키는 간선이 두개가 있다.(정점 A와 C에서 나온 간선) 위상 정렬은 이 두개의 간선을 먼저 탐색을 해야지 D를 검색 할 수 있는 것이다. 어디에 쓰일 수 있을까? 기본적으로 선행과목을 예시로 들 수 있다. 가령 과목 D를 듣고 싶다. 과목 D를 듣기 위해선 우선 적으로 A와 B 그리고 C과목 까지 들어야 D과목을 들을 수 있다. 위상정렬 기본적인 자바 코드 Queue<Integer> q = new LinkedList<Integer>(); for (int i = 1; i &lt;= n; i++) { if (inDegree[i] == 0) { q.add(i); } } for (int k = 0; k &lt; n; k++) { int x = q.remove(); System.out.print(x + " "); for (int y : a[x]) { inDegree[y] -= 1; if (inDegree[y] == 0) { q.add(y); } } }

힙 정렬  Heapsort 힙 정렬 (Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다. 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다. 2와 3을 반복한다. 이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어 지므로  {\displaystyle O(\log n)} 의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과  {\displaystyle n} 개의 데이터 삭제 및 재구성 시간을 포함한다. 시간 복잡도는 = (log n+log(n-1)+...+log 2) = (log n+log(n-1)+...+log 2)+(log n+log(n-1)+...+log 2) = O(n*log n) 따라서 힙 정렬은 일반적인 경우  {\displaystyle O(n\log n)} 의 시간복잡도를 가진다. 위키 피디아 참조. 자바 코드 public class JAVAHeap{ public static void main(String[] args) { int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22 }; HeapSort(arr); } public static void HeapSort(int[] arr) { JAVAHeap heap = new JAVAHeap(

버블정렬 BubbleSort 단순한 알고리즘으로 거품으로 비유를 하지만 개인적으로 물고기가 팔짝팔짝 뛰는 것을 연상했다. 1. 인접한 두 인덱스를 비교해서 정렬이 되어있지 않을경우 정렬한다. 2. 리스트 처음부터 끝까지 이런식의 정렬을 하고 나면 제일 마지막 리스트에는 제일 큰 값(또는 작은 값)이 저장된다. 3. 다시 처음 리스트부터 마지막 리스트 이전 리스트까지 서로 이웃한 인덱스를 비교해가며 정렬한다. 4. 위 방법으로 계속해서 정렬한다. 쉽게 말해 인접한 두 수를 비교해서 큰 수 혹은 작은 수를 뒤로 보내는 형태이다. 이해하기 쉬운 동영상 자바 코드 public class BubbleSort { public static void main(String[] args) { int[] data = { 4, 54, 2, 8, 63, 7, 55, 56 }; int temp; int cnt = 0; System.out.print("======정렬 전===============\n"); for (int m = 0; m < data.length; m++) { System.out.print(data[m] + ", "); } for (int i = data.length; i > 0; i--) { // for (int j = 0; j < i - 1; j++) { cnt++; if (data[j] > data[j + 1]) { temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; } } } System.out.print("\n\n======Bubble Sort=========\n"); for (int k = 0; k < data.length; k++) {