1. Opening
Tim sort (Tim 정렬)는 2002년 Tim Peters라는 Software Engineer에 의해 고안되었다.
주요 특징은 Insertion Sort(삽입정렬)과 MergeSort(병합정렬)을 결합하여 만들었다는 데에 초점을 두었다.
:: 시간 복잡도 ::
최적 : O(n)
평균 : O(n * log n)
최악 : O(n * log n)
> 시간복잡도에서 표현이 가능해서 알겠지만, 평균과 최악의 차이가 없다.
:: 안정성 ::
Tim Sort는 위에서 언급 하였듯, Insertion sort, Merge Sort의 결합된 알고리즘이다.
Insertion Sort와 Merge Sort의 안정성이 비교적 다른 알고리즘들에 비해 좋은편이다.
고로 두 알고리즘을 결합한 Tim Sort또한 안정적인 알고리즘이라고 볼 수 있다.
:: 구현 언어 ::
초기에는 Pyhton, Java와 같은 언어들로 구현되었다 한다.
2. Principle
Tim Sort는 Insertion 과 Merge sort를 사용하는데,
먼저 알아야 할 개념이 있다. 바로 Run이라는 개념인데,
일반적으로 sort알고리즘이 기본 정렬 알고리즘이 나왔을 때 이후로,
많은, 그러니까 대량의 데이터를 정렬하는데 더 효율적인 방법을 찾게된다.
2 - 1 Run
Run은 데이터를 일정 크기의 블록으로 나누는 개념이다.
Run은 주로 2^5, 32로 보통 지정한다.
100개의 데이터가 존재한다면,
#R1 = 0 ~ 31 ( 32개 )
#R2 = 32 ~ 63 ( 32개 )
#R3 = 64 ~ 95 ( 32개 )
#R4 = 96 ~ 99 ( 4개 ) ====>> 총 100개
이와 같이 4개의 Run이 발생하게 된다.
Run은 2의 지수승으로 올라가는 규칙이있다.
2 - 2 Insertion Sort
데이터를 Run 단위로 나눈 후, Insertion Sort를 진행한다.
Insertion Sort는 기본 알고리즘이라 여기서 언급은 안하겠다.
그렇게 되면 각 Run 마다, 즉 32개의 데이터 마다 Insertion Sort를 진행한다.
위의 예시로 100개의 데이터면 32개씩 삽입정렬이 이루어지고, 마지막 4번째 Run에서는 4개의 데이터만 삽입 정렬이 이루어진다.
2- 3 Merge Sort
위에서 진행된 삽입정렬 후, 각 Run 별로는 정렬이 되어있지만 Run끼리는 정렬되어 있지 않다.
따라서 마지막으로 정렬되지 않은 부분들을 Divide & Conquer를 쓰는 병합정렬을 이용해
나뉘어졌던 Run들을 다시 정렬을 해준다.
3. C Source
C언어로 구현한 코드를 밑에 기재했다.
:: 조건 ::
1)) 0 ~ 99, 100개의 정렬되는지 확인하는 테스트
2)) 30000개의 데이터를 입력해서 Insertion Sort와 Tim Sort의 성능 차이 비교
3)) 모든 데이터는 독립된 값, 즉 겹치는 숫자가 없다.
또한, 음수는 존재하지 않는다.
Windows에서 먼저 구현 하였지만
동일한 소스코드가 Mac OS에서 작동하지 않았다.
고로 조금 수정하였다.
P.S. Mac OS수정본이 조금더 볼게 많다. 나중에 수정하였기 때문. 윈도우 버전을 다시 수정하기에는 귀찮다.
// C source for MAC
#define _CRT_RAND_S
#define TOTAL_SIZE 30000
#define MAX_NUMBER 30000
#define TEST 100
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
void printArr(int[], int);
void sortInsertion(int[], int, int);
void Merge(int[], int, int, int);
void sortTim(int[], int); // Tim Sort
void sortTimtest(int[], int);
void printRun(int[], int);
int main() {
unsigned int input;
int arr_test[TEST];
int arr_raw[TOTAL_SIZE];
int arr[TOTAL_SIZE];
srand(time(NULL));
for (int i = 0; i < TEST; i++) {
input = rand() % TEST;
arr_test[i] = input;
for (int j = 0; j < i; j++) {
if (arr_test[i] == arr_test[j]) {
i--;
break;
}
}
}
for (int i = 0; i < TOTAL_SIZE; i++) {
input = rand() % TOTAL_SIZE;
arr_raw[i] = input % MAX_NUMBER;
for (int j = 0; j < i; j++) {
if (arr_raw[i] == arr_raw[j]) {
i--;
break;
}
}
}
printf("[TIM]\nBefore Sort: \n");
printArr(arr_test, TEST);
printf("\nRuns >>\n");
printRun(arr_test, TEST);
printf("\nAfter Sorted >>\n");
sortTimtest(arr_test, TEST);
printf("\nTotal Sort: \n");
printArr(arr_test, TEST);
time_t start, end;
float gap, insert, tim;
printf("\n\n=============================================================\nComparing Execution Time\n");
memcpy(arr, arr_raw, sizeof(int) * TOTAL_SIZE);
start = clock();
sortInsertion(arr, 0, TOTAL_SIZE);
end = clock();
gap = (float)(end - start) / CLOCKS_PER_SEC;
printf("[INSERTION SORT]\nExecution Time: %f\n", gap);
insert = gap;
memcpy(arr, arr_raw, sizeof(int) * TOTAL_SIZE);
start = clock();
sortTim(arr, TOTAL_SIZE);
end = clock();
gap = (float)(end - start) / CLOCKS_PER_SEC;
printf("\n\n[TIM SORT]\nExecution Time : %f\n", gap);
tim = gap;
printf("\nTim Sort is %d times better than Insertion Sort!\n", (int)(insert / tim));
return 0;
}
void sortInsertion(int arr[], int start, int end) {
int tmp;
for (int i = start + 1; i <= end; i++) {
for (int j = start; j < i; j++) {
if (arr[j] > arr[i]) {
tmp = arr[i];
for (int k = i; k > j; k--)
arr[k] = arr[k - 1];
arr[j] = tmp;
break;
}
}
}
}
void Merge(int arr[], int start, int mid, int end) {
int leng1 = mid - start + 1;
int leng2 = end - mid;
int* arrL = (int*)malloc(sizeof(int) * leng1);
int* arrR = (int*)malloc(sizeof(int) * leng2);
for (int i = 0; i < leng1; i++)
arrL[i] = arr[start + i];
for (int i = 0; i < leng2; i++)
arrR[i] = arr[mid + 1 + i];
int i = 0;
int j = 0;
int k = start;
for (; i < leng1 && j < leng2;) {
if (arrL[i] <= arrR[j])
arr[k++] = arrL[i++];
else
arr[k++] = arrR[j++];
}
while (i < leng1)
arr[k++] = arrL[i++];
while (j < leng2)
arr[k++] = arrR[j++];
free(arrL);
free(arrR);
}
void sortTim(int arr[], int leng) {
int minrun = 32;
for (int i = 0; i < leng; i += minrun)
sortInsertion(arr, i, ((minrun + i - 1) < (leng - 1) ? (minrun + i - 1) : (leng - 1)));
for (int size = minrun; size < leng; size = 2 * size) {
for (int start = 0; start < leng; start += 2 * size) {
int mid = size + start - 1;
int end = ((start + 2 * size - 1) < (leng - 1) ? (start + 2 * size - 1) : (leng - 1));
Merge(arr, start, mid, end);
}
}
}
void sortTimtest(int arr[], int leng) {
int minrun = 32;
for (int i = 0; i < leng; i += minrun)
sortInsertion(arr, i, ((minrun + i - 1) < (leng - 1) ? (minrun + i - 1) : (leng - 1)));
for (int i = 1; i <= leng / minrun + 1; i++) {
printf("RUN #%d\n", i);
for (int j = (i - 1) * minrun; j < i * minrun; j++) {
printf("%d ", arr[j]);
if (j == leng - 1)
break;
}
printf("\n");
}
for (int size = minrun; size < leng; size = 2 * size) {
for (int start = 0; start < leng; start += 2 * size) {
int mid = size + start - 1;
int end = ((start + 2 * size - 1) < (leng - 1) ? (start + 2 * size - 1) : (leng - 1));
Merge(arr, start, mid, end);
}
}
}
void printRun(int arr[], int leng){
int run = 32;
for(int i = 1; i <= leng / run + 1; i++){
printf("RUN #%d \n", i);
for(int j = (i - 1) * run; j < i * run; j++){
printf("%d ", arr[j]);
if(j == leng - 1)
break;
}
printf("\n");
}
}
void printArr(int arr[], int leng) {
for (int i = 0; i < leng; i++)
printf("%d ", arr[i]);
printf("\n");
}
// C Source for Win OS
#define _CRT_RAND_S
#define TOTAL_SIZE 30000
#define MAX_NUMBER 30000
#define TEST 100
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
void printArr(int[], int); // 배열 출력
void sortInsertion(int[], int, int);
void Merge(int[], int, int, int);
void sortTim(int[], int); // Tim Sort
void sortTimtest(int[], int); // 과정 보여주는 Tim Sort
int main() {
unsigned int input;
// Tim Sort 진행과정 보기용
int arr_test[TEST];
// Tim Sort 성능 비교용
int arr_raw[TOTAL_SIZE];
int arr[TOTAL_SIZE];
for (int i = 0; i < TEST; i++) {
rand_s(&input);
arr_test[i] = input % TEST;
for (int j = 0; j < i; j++) {
if (arr_test[i] == arr_test[j]) {
i--;
break;
}
}
}
for (int i = 0; i < TOTAL_SIZE; i++) {
rand_s(&input);
arr_raw[i] = input % MAX_NUMBER;
for (int j = 0; j < i; j++) {
if (arr_raw[i] == arr_raw[j]) {
i--;
break;
}
}
}
printf("[TIM]\nBefore Sort: \n");
printArr(arr_test, TEST);
sortTimtest(arr_test, TEST);
printf("After Sort: \n");
printArr(arr_test, TEST);
// 성능 테스트
time_t start, end;
float gap;
memcpy(arr, arr_raw, sizeof(int) * TOTAL_SIZE);
start = clock();
sortTim(arr, TOTAL_SIZE);
end = clock();
gap = (float)(end - start) / CLOCKS_PER_SEC;
printf("\n\n[TIM SORT]\n수행시간: %f\n", gap);
return 0;
}
// 기존의 Insertion Sort에는 범위 지정이 필요 없었지만 run을 이용하기 위해 범위 지정 필요
void sortInsertion(int arr[], int start, int end) {
int tmp;
for (int i = start + 1; i <= end; i++) {
for (int j = start; j < i; j++) {
if (arr[j] > arr[i]) {
tmp = arr[i];
for (int k = i; k > j; k--)
arr[k] = arr[k - 1];
arr[j] = tmp;
break;
}
}
}
}
// 병합정렬이라기 보다는 병합하는 과정이 중점이기 때문에 sort 제외
void Merge(int arr[], int start, int mid, int end) {
//두개의 메모리를 할당해서 따로 정렬후, 다시 병합하는 과정이 필요
//먼저 2개 메모리 할당을 위한 사이즈 구하고 메모리 할당
int leng1 = mid - start + 1;
int leng2 = end - mid;
int* arrL = (int*)malloc(sizeof(int) * leng1);
int* arrR = (int*)malloc(sizeof(int) * leng2);
for (int i = 0; i < leng1; i++)
arrL[i] = arr[start + i];
for (int i = 0; i < leng2; i++)
arrR[i] = arr[mid + 1 + i]; // mid 는 중간값이기 때문 + 1 필요
int i = 0;
int j = 0;
int k = start;
for (; i < leng1 && j < leng2;) {
if (arrL[i] <= arrR[j])
arr[k++] = arrL[i++];
else
arr[k++] = arrR[j++];
}
while (i < leng1)
arr[k++] = arrL[i++];
while (j < leng2)
arr[k++] = arrR[j++];
free(arrL);
free(arrR);
}
void sortTim(int arr[], int leng) {
int minrun = 32; // run 의 크기는 2의 5승, 즉 32로
// run 크기 만큼 insertion sort 진행
for (int i = 0; i < leng; i += minrun) // 총 배열 사이즈가 minrun, 32만큼 안되면 배열의 사이즈에 맞게 변경.
sortInsertion(arr, i, ((minrun + i - 1) < (leng - 1) ? (minrun + i - 1) : (leng - 1)));
// minrun 사이즈가 1개씩 Insertion Sorting 되어있기 때문에 병합 시 minrun의 2배가 필요
for (int size = minrun; size < leng; size = 2 * size) {
// 시작 인덱스를 생성해서 병합을 진행, 시작 인덱스는 minrun의 2배씩 커져야 함.
for (int start = 0; start < leng; start += 2 * size) {
// 병합 진행하기 위해, 시작은 주어졌으니, 중간, 말단 인덱스를 구해서 병합을 진행
int mid = size + start - 1;
int end = ((start + 2 * size - 1) < (leng - 1) ? (start + 2 * size - 1) : (leng - 1));
// 사실상 이 구문은 필요 없이 그냥 size * 2 + start - 1 해도 상관 없을 듯 함.
Merge(arr, start, mid, end);
}
}
}
// Tim Sort의 진행 과정을 보이기 위한 동일하지만 과정 출력하는 코드 포함된 함수
void sortTimtest(int arr[], int leng) {
int minrun = 32; // run 의 크기는 2의 5승, 즉 32로
// run 크기 만큼 insertion sort 진행
for (int i = 0; i < leng; i += minrun) // 총 배열 사이즈가 minrun, 32만큼 안되면 배열의 사이즈에 맞게 변경.
sortInsertion(arr, i, ((minrun + i - 1) < (leng - 1) ? (minrun + i - 1) : (leng - 1)));
// 여기서 minrun 만큼 나눈 사이즈의 배열들을 파악 할 수 있다.
for (int i = 1; i <= leng / minrun + 1; i++) {
printf("RUN #%d\n", i);
for (int j = (i - 1) * minrun; j < i * minrun; j++) {
printf("%d ", arr[j]);
if (j == leng - 1)
break;
}
printf("\n");
}
// minrun 사이즈가 1개씩 Insertion Sorting 되어있기 때문에 병합 시 minrun의 2배가 필요
for (int size = minrun; size < leng; size = 2 * size) {
// 시작 인덱스를 생성해서 병합을 진행, 시작 인덱스는 minrun의 2배씩 커져야 함.
for (int start = 0; start < leng; start += 2 * size) {
// 병합 진행하기 위해, 시작은 주어졌으니, 중간, 말단 인덱스를 구해서 병합을 진행
int mid = size + start - 1;
int end = ((start + 2 * size - 1) < (leng - 1) ? (start + 2 * size - 1) : (leng - 1));
// 사실상 이 구문은 필요 없이 그냥 size * 2 + start - 1 해도 상관 없을 듯 함.
Merge(arr, start, mid, end);
}
}
}
// 배열 출력함수
void printArr(int arr[], int leng) {
for (int i = 0; i < leng; i++)
printf("%d ", arr[i]);
printf("\n");
}