Become a better programmer

Divide and Conquer, Sorting and Searching, and Randomized Algorithmsby Stanford University 의 Merge Sort : Analysis 정의 Merge sort는 6nlogn+6n의 operation을 갖는다. (n은 array의 수의 갯수) 먼저 한 번의 리컬시브에서 계산량을 구한다.operation의 수는 4m + 2i, j assignm번 루프k assign배열 카피 i 또는 j의 증가m이 1보다 크거나 같다고 가정했을떄 6m 보다 작거나 같다계산의 편의를 위해 6m으로 사용 다음은 총 리컬시브의 양을 구한다. subproblem의 수는 2^n (맨 마지막 level의 노드 수)각 node의 사이즈는 n/2^n 한 리컬시브 계산량..

분할정복으로 행열을 쪼갤만큼 쪼갠다음 merge하면서 sort한다 항상 nlogn 하지만 일반적으로 quick sort가 빠름 출처 : http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort 예제 파일 : https://gist.github.com/yujuwon/5810996#file-gistfile1-c import java.util.Arrays; public class MeargeSort20160305 {public static void main(String args[]) {int[] arr = { 1, 3, 3, 4, 5, 2, 7 };int[] temp = new int[arr.length];mergeSort(..

참고 : http://www.java2s.com/Code/Java/Collections-Data-Structure/BinaryTree.htm static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } }public void insert(Node node, int value) { if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { System.out.println(" Inserted " + value + " to left of " + node.value); node.left = new ..

참고 : http://www.algolist.net/Algorithms/Sorting/Quicksort Why does it work?On the partition step algorithm divides the array into two parts and every element a from the left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤ binequality. After completion of the recursion calls both of the parts become sorted and, taking into account arguments stated ..