정렬의 종류별 알고리즘에 대해 정리할 때, 기수 정렬의 시간복잡도는 O(N)이 나왔었다. 그런데 일반적으로 정렬의 시간 복잡도는 O(N log N) 으로 알려져있다. 어떻게 기수 정렬은 O(N) 시간에 정렬을 할 수 있었을까? 그리고 왜 일반적으로 정렬의 시간 복잡도는 O(N log N) 으로 알려져 있는 걸까? 한번 O(n log n) 시간으로 고정되어있는 merge sort 의 comparison 과정을 tree로 표현해보자. a, b, c, d 라는 4개의 데이터에 대해 merge sort 를 수행하면, 반씩 쪼개다가 merge 하는 과정에서 비교를 수행한다. 이때 비교를 통해 정렬을 수행하는 모든 경우의 수를 comparison tree 로 그려보자. 제일 먼저 비교가 일어나는 부분은 a, b 이..
방식의 비교횟수와 쓰기 횟수를 비교해보고자 한다. 병합 정렬 merge_sort() 함수의 호출시, 기존 배열을 복사해서 넣어놓고, 카운팅할 비교횟수와 데이터 쓰기 횟수를 초기화한다. mergeSort() 라는 재귀용 함수를 호출한다. 받은 배열을 반씩 나눠서 재귀적으로 mergeSort 를 호출하며, mergeSort 로 반씩 정렬된 결과를 다시 합쳐서 정렬할 merge 함수도 호출한다. 실질적인 정렬이 수행되는 merge 함수다. 먼저 반씩 정렬된 배열을 다른 배열에 복사해서 옮겨둔다. merge sort 를 배열롤 구현할 때 반드시 수행해야 하는 작업이기에, 이는 데이터 쓰기 횟수에 포함시켜서 카운팅했다. 그리고 기존 입력된 배열을 복사한 배열을 반씩 나눠 탐색하면서 작은값부터 채워나간다. 이 과정..
그림과 같이 100만개의 랜덤 성생된 정수가 있다. 이 정수를 각 정렬 방법으로 정렬해보려고 한다. (100만개를 N^2 시간에 정렬하면 시간이 오래 걸려서, 실제로는 100, 200, ..., 900 단위로만 정렬해 볼 것이다.) 정렬을 수행하면서, 비교는 몇번 일어나는지, 정렬을 하기 위해, 기존 배열에 (또는 새로 생성한 배열에) 데이터를 쓰는 행위를 몇번이나 하는지 횟수를 세보고자 한다. 이를 위해 먼저 100만개의 정수가 담긴 데이터를 ' ' 기준으로 끊어 배열에 저장한다. 그리고 각 정렬을 수행한다. 정렬은 사이즈가 100, 200, 300, ..., 900 인 상황을 매번 수행해보면서, 그 때의 비교횟수와 데이터 쓰기 횟수를 카운팅한다. 차례대로 정렬을 구현하고, 횟수를 카운팅한 결과를 출력..
정렬은 큰 사이즈의 작업에 대해 컴퓨터가 자주 수행하는 동작 중 하나다. 이번 글에서는 5가지 정렬 방법에 대해 간단하게 정리하고자 한다. 선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) 은 말 그대로 정렬 기준에 맞는 값을 선택해서 정렬하는 알고리즘이다. 선택 정렬은 In-Place 방식으로, O(n^2) 시간에 수행된다. 알고리즘은 다음과 같다. 1. 정렬된 결과의 0번째 원소를 결정하려고 한다. 2. 0번째원소를 1번째 원소부터 N-1번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap 한다. 3. 이번엔 1번째 원소를 결정하려고 한다. 4. 1번째 원소를 2번째 원소부터 N-1 번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap ..
용어 Memory : stores a programs instructions and data size of an instrcution : 4 byte size of data : Byte(1 byte), Half word(2 byte), Word(4 byte), Double (8 byte) => memory read/write size Register : memory place in a processor (CPU), store intermediate results during calculation, or values often used size of register : 4 byte Text Section : save the program instructions, save read-only data (glo..
지난 글에서는 단점일도 FPU 명령어 사용 예제를 살펴보았다. 이번 글에서는 배정밀도 FPU 명령어 사용 예제를 살펴보고자 한다. Double-Precision Floating Point Computation 배정밀도 연산자는 기존 연산자 끝에 s 대신 d 가 붙는 것만 다르다. faddd fsubd fmuld fsmuld (single * single = double, 피연산자는 single 이다.) fdivd fsqrtd double 연산자의 피연산자 레지스터는 반드시 짝수번째 레지스터가 들어가야 한다. %fi 와 %f(i+1) 의 2개 레지스터로 하나의 소수를 표현하기 때문이다. 연산 결과도 double 로 나오므로 짝수번째 레지스터를 사용한다. 데이터 형변환 명령어도 종류가 늘어났다. fitod ..
지난 글까지 실수에서의 산술연산 방법과 FPU의 개념 및 FPU에서 사용 가능한 연산들에 대해 정리하였다. 이번 글에서는 정리한 명령어를 직접 사용해보면서 명령어에 익숙해져보려고 한다. 단정밀도 예제 1 다음 코드를 어셈블리로 컴파일해보자. void main() { static float a = 1.5, b=10.5, c=0.0, d=3.5; if (c == d) c = a+b; else c = a-b; } 간단히 float 형 (단정밀도) 정적 변수 4개를 선언해 값을 할당하고, 비교해서 연산 결과 값을 저장하는 코드이다. 먼저 static 정적 공간에 데이터를 생성해야 하므로, ".data" 섹션을 사용하면 된다. .data 섹션에 단정밀도 공간을 할당하는 방법은 아래와 같이 하면 된다. 선언하는 사..
지난 글에서는 Floating Point 의 개념과 10진 소수를 이진 소수로 상호 변환하는 과정을 정리하였다. 이번 글에서는 Floating Point 간 사칙 연산을 정리하고자 한다. SPARC는 FPU 라고 하는 실수 계산용 arithmetic units (산술 연산 유닛) 이 존재하여, 덧셈/뺄셈/곱셈/나눗셈 기능을 지원한다. 그래서 정수와는 다르게, 곱셈과 나눗셈을 '명령어' 수준으로도 지원한다. 먼저 FPU를 살펴보기 전에, 실수의 산술 연산 과정을 정리해보자. 실수 덧뺄셈 실수의 덧뺄셈은 아래 과정으로 진행된다. 1. significand를 맞춘다. 2. significand 끼리 더해준다. 3. 결과를 Normalize 한다. 4. 기존 자릿수에 맞게 유효숫자를 맞춘 뒤, 필요하다면 다시 ..
10진수 소수 2진수 소수 상호 변환 이번 글에서부터는 컴퓨터가 '실수'를 어떻게 표현하는지 정리하고자 한다. 이진수를 다루는 컴퓨터가 실수를 어떻게 표현하는지를 알기 위해 먼저 10진수의 소수가 어떤 식으로 표현되고 있는지를 생각해보자. 10.155 라는 소수는 1 x 10^1 0 x 10^0 1 x 10^-1 5 x 10^-2 5 x 10^-3 이렇게 표현된다는 건 자연스럽게 알고 있다. 이는 이진수에서도 마찬가지로 작용한다. 10.111 이라는 이진수 소수는 1 x 2^1 0 x 2^0 1 x 2^-1 1 x 2^-2 1 x 2^-3 이렇게 표현된다. 그리고 이 값을 10진수로 잘 계산해주면 우리가 사용하는 10진수 소수값이 나온다. 그리고 이 과정을 통해 자연스럽게 2진수를 10진수로 변환하는 방..
이번에는 지금까지 정리한 내용에 더불어 C 라이브러리를 활용하여 버블소트를 SPARC로 구현할 것이다. C 코드 #include #incdlue #incdlue struct sort_info { unsigned int num_items; unsigned int max_value; }; unsigned int askNumber(char* message) { unsigned int val; register int result; do { printf("%s", message); result = scanf("%u", &val); } while (result != 1); return val; } struct sort_info askInfo() { struct sort_info si; si.num_items = a..
