QuickSort 논문 brief Part One: Theory 이 sorting은 두 개의 간단한 보조문제로 나뉘어 해결될 수 있는데, 각 문제는 이미 알려진 방식으로 풀 수 있다. Partition : key값을 dividing line에 따라 위 아래로 나누어 이분하는 것 실제로 이 dividing line은 흔치 않고, 있다 할지라도 찾기 힘든데 dividing line이 존재하고 그것의 위치만 안다면 item들을 재정렬하기는 쉬워진다. partition 과정 정렬되어야하는 아이템의 키 중 특정 키를 고른다. 이 키는 bound 라 불린다. dividing line 아래에는 bound보다 작거나 같은 key값이, 위쪽에는 큰 key 값이 오게 한다. dividing line의 위치는 미리 알 필요..

/* 2020-03-19 우희은 삽입정렬 알고리즘 */ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int buffer[10000000]; // 전역 변수로 넣어야 stack overflow가 나지 않음 void fileOpen() { FILE *fp = fopen("d://algorithm/unsorted10000000.txt", "r"); int i = 0; int tmp = 0; if (fp == NULL) { printf("파일을 열 수 없습니다.\n"); } while (fscanf(fp, "%d ", &tmp)!=EOF) { buffer[i++] = tmp; } fclose(fp); } void insertSortin..

7. 분할 정복 7.1 도입 분할 정복( Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라고 설명할 수 있음 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 재귀 호출을 이용해 각각의 답을 계산하고, 부분 문제의 답을 이용해 전체의 답을 계산하는 방식 알고리즘 구성 divide 문제를 더 작은 문제로 분할 merge 각 문제의 답을 전체 문제의 답으로 병합 base case 더이상 답을 분할하지 않고 풀 수 있는 매우 작은 문제 적용가능한 문제의 특성 문제를 부분 문제로 나누는 자연스러운 방법이 존재해야함 부분 문제의 답을 조합해 전체 문제의 답을 계산하는 효율적인 방법이 있어야함 장점 대부분의 경우에서 작업을 빠르게 처리해줌 예제 : 수열의 빠른 합과 행렬의 빠른..