Quick sort '알고리즘' 전공 수업시간에 나온 과제인 '1000만개 데이터 정렬 후 해시 값 구하기'를 하면서 정리한 내용이다. 분할 정복 방법을 통해 구현되는 정렬 방법 시간 복잡도 최악 : O(n^2) 평균 : O(nlogn) 설계를 통해서 개선 가능한 부분 구현 과정 pivot을 선택한다. 위쪽 포인터가 낮은 쪽으로 가면서 피벗보다 작은 수를 찾는다. 아래쪽 포인터가 높은 쪽으로 가면서 피벗보다 큰 수를 찾는다. 두 포인터가 가리키는 요소를 교환한다. 2-4를 반복한다. 두 포인터가 교차한다면 현재 피벗과 해당 위치의 값을 교환한다. 피벗과 피벗보다 작은 section, 피벗보다 큰 section으로 나누고 각 section에 대해 1-5를 실행한다. section의 크기가 0 또는 1이면 ..

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

첫번째 과제이다. 시간 복잡도가 f(n)인 알고리즘의 소요시간이 1 nanosecond == 10^(-9) second 이라고 할 때, 왼쪽에 표시된 시간 복잡도를 가지고 있는 알고리즘에 대해 위쪽의 시간 내에 알고리즘이 완료되려면 최대로 어떤 N까지 계산할 수 있을지 알아보자. 대표로 하나를 계산해보면 1sec는 10^(9) nanosec 이므로 n^2의 시간복잡도를 갖는 알고리즘에서 n^2 = 10^(9) 로 두고 풀면 1sec 만에 계산될 수 있는 n 값이 나온다. n 값은 모두 정수로 가정하였다.

세그먼트 트리 https://www.acmicpc.net/blog/view/9 백준님 글 배열 크기 결정 세그먼트 트리를 만들기 위해서 C++의 경우, vector 자료형을 사용하는데 python으로 구현할 것이기 때문에 배열을 사용하려고 한다. 배열의 크기가 얼마나 되어야 할지 가늠하기 위해 크기를 결정해보자. 2의 제곱 수가 리프 노드의 수(n)로 주어진다면 ( 분석해야할 data 갯수가 2의 제곱 수라면 ) 각 단계마다 1/2씩 줄어나가므로 log(n)이 필요한 총 단계(화살표)가 되고 전체 층의 갯수, 즉 높이(h)는 log(n)+1이 된다. 최상위 노드부터 2^(0)개의 노드로 시작하여 층이 증가할 수록 2의 지수 또한 증가하기 때문에 꽉찬 이중 트리(full binary tree)의 총 노드 ..