0. Intro
일전에 정렬편(1)에서 병합정렬(합병정렬)을 다뤘다.
앞서 팀정렬에 관해 가볍게 이야기를 했는데, TimSort에 관해 간단하게 이야기를 해 보도록 하자!
우선, 해당 정렬 코드를 적용해 보기 위해
팀정렬의 내용을 공부도 했고, 다른 링크들을 참조도 해서 구현은 했지만 막상 이를 적용할 문제를 찾지 못하고 있어 이를 포스팅 하기가 어려웠다.
그러던 중, LeetCode에서 정렬 라이브러리를 사용하지 않고 정렬을 해서 사용하라는 문구가 있어, 이를 굳이 TimSort를 활용했다.
1. TimSort (!= Team)
내가 처음 접했을 때 이 정렬에 대한 첫 번째 오해는 이름에서 왔다.
뭐 하이브리드 정렬로 분류 되니까 맞는 거 아닌가?
Tim이란 사람이 만들어서 이런 이름을 쓴다고 한다.
대단한 개발자라는 생각이 듭니다. 자신이 사용하기 위해 구현한 코드가 기본 라이브러리에 포함이 되었다는 것 부터가 예사롭지 않다고 생각되는데,
TimSort는 2002년 파이썬 프로그래밍에 사용하기 위해 팀 피터스가 구현했다.(출처 : 위키피디아)
23년인 현재로 따지면 21년 전에 등장한 정렬 방식인데 이게 무엇 보다도 파이썬 2.3부터 파이썬의 표준 정렬 알고리즘이 되었으며, 자바 SE 7 등의 다양한 언어에서도 정렬을 위한 표준 라이브러리가 되었다는 점이 놀랍다.(출처는 역시 동일한 위키피디아를 따릅니다.)
피터 매클로이의 1993년 논문 "최적의 정렬 및 정보이론복잡성"(Optimistic Sorting and Information Theoretic Complexity)의 기법들을 사용한다.라고까지만 나와 있어서 더 찾아 봤다.
해당 논문은 당연하지만 영어로 작성되어 있기 때문에 핵심 정리를 Chat GPT를 통해 빠르게 작업했다.
아래의 내용으로 이해해 보자.
-
해당 논문은 "Optimistic Sorting and Information Theoretic Complexity"라는 주제로, 불완전하게 섞인 데이터를 정렬하는 문제에 대해 다루고 있습니다. 논문의 주요 내용은 다음과 같습니다:
-
개요: 엔트로피 고려를 통해 불완전하게 섞인 데이터를 정렬하는 비교 횟수의 자연스러운 추정을 제공합니다. 삽입 정렬과 병합 정렬의 간단한 수정을 통해 이러한 데이터에 대한 성능이 향상됩니다. 수정된 병합 정렬은 이론적으로도 실제로도 효율적입니다.
-
정렬 알고리즘의 특성: 본 논문에서는 정렬 알고리즘이 정보 이론적 복잡성에 가까워지도록 몇 가지 속성을 나열합니다.
-
병합 정렬의 변형: 지수 검색과 선형 검색의 하이브리드를 사용한 병합 정렬의 변형을 제안합니다. 이 변형은 엔트로피 고려를 통해 특정 클래스의 순열에 대해 정보 이론적 한계에 가까운 비교 횟수를 달성합니다.
-
성능 분석: 논문은 다양한 경우에 대한 MSES와 MSES/MSLS 하이브리드의 성능을 보여줍니다. 하이브리드는 심지어 무작위 데이터에 대해서도 Quicksort와 경쟁력이 있으며, 약간 정렬된 데이터에 대해서는 선택의 전략이 될 수 있습니다.
-
결론: 병합 정렬의 추가적인 개선은 시간과 공간의 패널티를 수반하며 실용적이지 않을 수 있습니다. 병합 정렬은 여전히 두드러진 이점을 유지하며, 하이브리드 전략은 심지어 무작위 데이터에서도 경쟁력이 있습니다.
-
이 논문은 복잡한 정렬 문제에 대한 새로운 접근 방식과 효율적인 해결책을 제시하며, 정보 이론과 복잡성에 대한 흥미로운 관점을 제공합니다.
해당 논문에는 코드가 한 줄도 나오지 않으며 인용 횟수도 42회로 그리 많지 않다는 점을 생각해 보면 정말 대단한 성과이며, 이를 실제 적용 구현할 수 있는 소프트웨어 개발의 멋과 미학이 느껴져서 팀소트를 많이 애용해야겠다는 생각과 더불어, 특수한 경우에서는 더 빠른 다른 정렬 알고리즘들에 대해서도 소개해 보고자, 한다.
2. What is Next?(보이어 무어 알고리즘)
그래서 다음 주제는 잠깐 다른 주제를 다루려 하는데
해당 알고리즘의 이름은 보이어 무어 알고리즘이다.
문자열 검색 알고리즘이라고 알려진 해당 알고리즘은
특정 값을 찾기 위한 방법으로 O(n)의 시간 복잡도, O(1)의 공간 복잡도를 가지는 알고리즘이다.
정렬을 하는 이유는 일반적으로 어떤 값을 검색(활용)하기 위해서라는 것을 생각해 보면 따로 떨어진 개념이라고 보기는 어렵지만,
시간 복잡도에서 O(1), 공간 복잡도에서는 O(n) 을 가지는 특수성을 가진다. 어떤 값에서 특징적인 값과 형태를 가지는지 알 필요가 있는 것이다. 순서상으로는 다음이 해당 알고리즘을 다루고 그 다음은 퀵소트 그리고 여타 정렬 알고리즘의 구현을 알아볼 예정이다.
3. 예시 문제로 알아보는 팀소트!
그렇다면 이번에 필자가 가지고 온 예시 문제를 살펴 볼 차례다.
필자는 LeetCode와 Backjoon, Programmers 등 다양한 곳을 오고가며 풀고 있는데, 이러한 알고리즘 그러니까 라이브러리를 외우고 머릿 속으로 정리하는 게 학습자 및 소프트웨어 개발자들에게는 필요하다고 생각되는 요소를 잠시 이야기 하자면,
특정 코딩 테스트들 삼성전자 SW 테스트 B형 와 최근에 생긴 현대의 Softeer Level4 와 같은 능력 인증 평가 시험에서는 이러한 정렬을 사용하려면 자신이 이를 구현할 줄 알아야 하기 때문
--> 일체의 라이브러리 사용 금지 조항!
이러한 시험을 준비하고 학습하며 알고리즘의 깊이, 코드의 아래와 내용 이해를 더해 가고 자연스럽게 머릿 속에 남기는 것이 이번 Hi-알고리즘을 기술하는 목적인 것 같다.
LeetCode의 문제에서도 라이브러리를 쓰지 말라는 조항이 있었고, 꼭 TimSort를 써야 하는 건 아니지만 TimSort를 사용했다.
문제링크
class Solution {
private final int RUN = 32;
public void sortColors(int[] nums) {
int n = nums.length;
timSort(nums, n);
}
public void insertionSort(int[] array, int left, int right){
for(int i = left + 1; i <= right; i++){
int temp = array[i];
int j = i - 1;
while(j >= left && array[j] > temp){
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
public void merge(int[] array, int l, int m, int r){
int len1 = m - l + 1, len2 = r - m;
int[] left = new int[len1];
int[] right = new int[len2];
for(int x = 0; x < len1; x++){
left[x] = array[l + x];
}
for(int x = 0; x < len2; x++){
right[x] = array[m + 1 + x];
}
int i = 0, j = 0, k = l;
while(i < len1 && j < len2){
if(left[i] <= right[j]){
array[k] = left[i];
i++;
}else {
array[k] = right[j];
j++;
}
k++;
}
while(i < len1){
array[k] = left[i];
k++;
i++;
}
while (j < len2) {
array[k] = right[j];
k++;
j++;
}
}
public void timSort(int[] array, int n){
for(int i = 0; i < n; i += RUN) {
insertionSort(array, i, Math.min((i + 31), (n-1)));
}
for(int size = RUN; size < n; size = 2 * size){
for(int left = 0; left < n; left += 2 * size) {
int mid = Math.min((left + size - 1), (n - 1));
int right = Math.min((left + 2 * size - 1), (n - 1));
merge(array, left, mid, right);
}
}
}
}라이브러리를 전혀 안 쓴건 아니다. Math.min을 썼으니, 저것까지 안 써야 더 완벽할 것 같아서 준비했다.
class Solution {
private final int RUN = 32;
public void sortColors(int[] nums) {
int n = nums.length;
timSort(nums, n);
}
private int min(int a, int b){ // 요거 추가가 전부죠 :)
return a > b ? b : a;
}
public void insertionSort(int[] array, int left, int right){
for(int i = left + 1; i <= right; i++){
int temp = array[i];
int j = i - 1;
while(j >= left && array[j] > temp){
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
public void merge(int[] array, int l, int m, int r){
int len1 = m - l + 1, len2 = r - m;
int[] left = new int[len1];
int[] right = new int[len2];
for(int x = 0; x < len1; x++){
left[x] = array[l + x];
}
for(int x = 0; x < len2; x++){
right[x] = array[m + 1 + x];
}
int i = 0, j = 0, k = l;
while(i < len1 && j < len2){
if(left[i] <= right[j]){
array[k] = left[i];
i++;
}else {
array[k] = right[j];
j++;
}
k++;
}
while(i < len1){
array[k] = left[i];
k++;
i++;
}
while (j < len2) {
array[k] = right[j];
k++;
j++;
}
}
public void timSort(int[] array, int n){
for(int i = 0; i < n; i += RUN) {
insertionSort(array, i, Math.min((i + 31), (n-1)));
}
for(int size = RUN; size < n; size = 2 * size){
for(int left = 0; left < n; left += 2 * size) {
int mid = min((left + size - 1), (n - 1));
int right = min((left + 2 * size - 1), (n - 1));
merge(array, left, mid, right);
}
}
}
}위처럼 간단하게 구현이 되는 걸 알 수 있다.
삽입 정렬은 정렬 basic이라는 이름으로 삽입 정렬, 버블 정렬, 선택 정렬을 다룰 때 한 번 더 다루겠지만 삽입 정렬에 관한 내용도 간단하게 아래로 알아 보고 오늘을 마무리 해 보자!
4. 삽입 정렬
삽입 정렬을 사용하는 방법에 대한 벤치마크 코드를 작성해 보았다.
성능이 얼마나 나오는지를 직접 확인할 수 있으며 경로는 자신이 파일 로그를 만들고 싶은 위치로 바꾸면 되며,
해당 파일의 iterator 값을 바꿈에 따라서 각각의 크기를 정할 수 있다.
또한 마지막으로 전체 프로그램의 동작 속도를 확인할 수 있으며, ms로 표시되므로, 1200ms == 1.2초라고 인지하면 된다. 즉 21000ms는 21초에 해당한다.
간단히 10개를 돌렸을 때의 txt 파일을 예시로 제공하며,
예시 코드의 System.out.println()을 통해 값을 직접 확인할 수도 있다.
import java.util.Random;
import java.io.PrintWriter;
import java.text.SimpleDateFormat;
import java.io.IOException;
import java.util.Date;
public class InsertionSortBenchmark {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int arraySize = 100000; // 배열 크기
// 현재 시간의 타임스탬프를 파일 이름에 추가
// 프로그램 시작 시간 측정
long programStartTime = System.currentTimeMillis();
//시작 시간 별로 각각의 데이터를 다르게 만들기 위한 formating
String timeStamp = new SimpleDateFormat("yyyyMMdd_HHmmss").format(new Date());
String fileName = "D:\\filelog\\results_" + timeStamp + ".txt";
try (PrintWriter writer = new PrintWriter(fileName, "UTF-8")) {
for (int iteration = 1; iteration <= 100; iteration++) {
int[] arr = new int[arraySize];
Random random = new Random();
// 무작위 값으로 배열 채우기
for (int i = 0; i < arraySize; i++) {
arr[i] = random.nextInt(1000000);
}
// 정렬 시작 시간 측정
long startTime = System.currentTimeMillis();
// 삽입 정렬 실행
insertionSort(arr);
// 정렬 종료 시간 측정
long endTime = System.currentTimeMillis();
// 결과를 파일에 기록
writer.println("횟수 : " + iteration + " 무작위 " + arraySize + " 크기 배열의 삽입 정렬 소요 시간은 " + (endTime - startTime) + " milliseconds 입니다.");
// 걸린 시간 출력
//System.out.println("횟수 : " + iteration + " 무작위 " + arraySize + " 크기 배열의 삽입 정렬 소요 시간은 " + (endTime - startTime) + " milliseconds 입니다.");
}
// 프로그램 종료 시간 측정
long programEndTime = System.currentTimeMillis();
// 프로그램 총 소요 시간 기록
writer.println("프로그램 총 소요 시간은 " + (programEndTime - programStartTime) + " milliseconds 입니다.");
} catch (IOException e) {
e.printStackTrace();
}
}
}iterator가 10인 경우와 100인 경우 확인하기
P.S. 파일 공유 방법을 찾지 못했을 뿐만 아니라, 이게 깨지는 오류가 있는 것으로 보여 아래와 같이 노션에 파일과 값 전체를 담은 토글을 첨부(아시는 분 댓글로 알려주세요. :) )
5. 참고 링크
