TimSort 정렬 알고리즘의 간단한 버전

1. TimSort 정렬 알고리즘의 단순 버전의 원리와 구현

TimSort 정렬 알고리즘은 Python 및 Java의 객체 배열에 대한 기본 정렬 알고리즘입니다. TimSort 정렬 알고리즘의 본질은 병합 정렬 알고리즘이지만 병합 정렬 알고리즘에 대한 많은 최적화가 이루어졌습니다. 우리가 일상생활에서 정렬해야 하는 데이터는 대개 완전히 무작위가 아닌 부분적으로 정렬되거나 부분적으로 반전되어 있으므로 TimSort는 정렬된 부분을 병합 정렬에 최대한 활용합니다. 이제 우리는 주로 다음과 같은 최적화를 수행하는 간단한 버전의 TimSort 정렬 알고리즘을 제공합니다.

1.1 원래 정렬된 조각 활용

먼저 최소 병합 길이를 지정합니다. 배열에서 원래 정렬된 조각을 확인합니다. 정렬된 길이가 지정된 최소 병합 길이보다 작으면 삽입 정렬을 통해 정렬된 조각을 확장합니다(이유는 효율성이 상대적으로 낮기 때문에 더 작은 길이의 조각을 병합하는 것을 피하기 위한 것입니다). . 정렬된 조각의 시작 인덱스 위치와 정렬된 길이를 스택에 푸시합니다.

1.2 더 긴 순서의 조각을 더 작은 순서의 조각과 병합하지 마십시오. 이는 효율성이 떨어지기 때문입니다.

(1) 스택에 순서가 지정된 조각이 있는 경우 최소한 세 개의 시퀀스를 사용합니다. X, Y, Z는 스택 맨 위에서 아래로 3개의 기존 시퀀스 조각을 나타내고 3개의 길이가 만족할 때 병합합니다.

(1.1) If Stack

(1.2) 그렇지 않으면 스택에서 X와 Y를 팝하고 병합된 결과를 스택에 푸시합니다. 실제로 스택을 실제로 팝하지는 않을 것입니다. 동일한 효과를 달성하고 더 효율적으로 코드를 작성할 수 있는 몇 가지 기술이 있습니다.

(2) X+Y>=Z 조건이 충족되지 않거나 스택에 시퀀스가 ​​2개만 있는 경우 X와 Y를 사용하여 위에서부터 기존 두 시퀀스의 길이를 나타냅니다. 스택을 아래로 내려갑니다. X>=Y인 경우 병합한 다음 병합된 정렬된 조각 결과를 스택에 푸시합니다.

1.3 이미 정렬된 두 개의 조각을 병합할 때 소위 갤럽 모드가 사용되며, 이는 병합에 관련된 데이터 길이를 줄일 수 있습니다.

이미 정렬된 두 개의 조각을 병합해야 한다고 가정합니다. 순서가 지정된 조각은 각각 X와 Y입니다. 위치의 첫 번째 m 요소입니다. 마찬가지로, Y 조각의 마지막 n 요소가 X의 마지막 요소보다 크면 Y의 마지막 n 요소는 병합에 참여할 필요가 없습니다. 이렇게 하면 병합된 배열의 길이가 줄어들고(간단한 버전에서는 이 작업이 수행되지 않음) 정렬할 배열과 보조 배열 사이를 오가며 복사되는 데이터의 길이도 줄어들어 병합 효율성이 향상됩니다.

2. Java 소스 코드

package datastruct;
 
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
 
public class SimpleTimSort<T extends Comparable<? super T>>{
    //最小归并长度
    private static final int MIN_MERGE = 16;
    //待排序数组
    private final T[] a;
    //辅助数组
    private T[] aux;
    //用两个数组表示栈
    private int[] runsBase = new int[40];
    private int[] runsLen = new int[40];
    //表示栈顶指针
    private int stackTop = 0;
     
    @SuppressWarnings("unchecked")
    public SimpleTimSort(T[] a){
        this.a = a;
        aux = (T[]) Array.newInstance(a[0].getClass(), a.length);
    }
     
    //T[from, to]已有序，T[to]以后的n元素插入到有序的序列中
    private void insertSort(T[] a, int from, int to, int n){
        int i = to + 1;
        while(n > 0){
            T tmp = a[i];
            int j;
            for(j = i-1; j >= from && tmp.compareTo(a[j]) < 0; j--){
                a[j+1] = a[j];
            }
            a[++j] = tmp;
            i++;
            n--;
        }
    }
     
    //返回从a[from]开始，的最长有序片段的个数
    private int maxAscendingLen(T[] a, int from){
        int n = 1;
        int i = from;
         
        if(i >= a.length){//超出范围
            return 0;
        }
         
        if(i == a.length-1){//只有一个元素
            return 1;
        }
         
        //至少两个元素
        if(a[i].compareTo(a[i+1]) < 0){//升序片段
            while(i+1 <= a.length-1 && a[i].compareTo(a[i+1]) <= 0){
                i++;
                n++;
            }
            return n;
        }else{//降序片段，这里是严格的降序，不能有>=的情况，否则不能保证稳定性
            while(i+1 <= a.length-1 && a[i].compareTo(a[i+1]) > 0){
                i++;
                n++;
            }
            //对降序片段逆序
            int j = from;
            while(j < i){
                T tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                j++;
                i--;
            }
            return n;
        }
    }
     
    //对有序片段的起始索引位置和长度入栈
    private void pushRun(int base, int len){
        runsBase[stackTop] = base;
        runsLen[stackTop] = len;
        stackTop++;
    }
     
    //返回-1表示不需要归并栈中的有序片段
    public int needMerge(){
        if(stackTop > 1){//至少两个run序列
            int x = stackTop - 2;
            //x > 0 表示至少三个run序列
            if(x > 0 && runsLen[x-1] <= runsLen[x] + runsLen[x+1]){
                if(runsLen[x-1] < runsLen[x+1]){
                    //说明 runsLen[x+1]是runsLen[x]和runsLen[x-1]中最大的值
                    //应该先合并runsLen[x]和runsLen[x-1]这两段run
                    return --x;
                }else{
                    return x;
                }
            }else
            if(runsLen[x] <= runsLen[x+1]){
                return x;
            }else{
                return -1;
            }
        }
        return -1;
    }
     
    //返回后一个片段的首元素在前一个片段应该位于的位置
    private int gallopLeft(T[] a, int base, int len, T key){
        int i = base;
        while(i <= base + len - 1){
            if(key.compareTo(a[i]) >= 0){
                i++;
            }else{
                break;
            }
        }
        return i;
    }
     
    //返回前一个片段的末元素在后一个片段应该位于的位置
    private int gallopRight(T[] a, int base, int len, T key){
        int i = base + len -1;
        while(i >= base){
            if(key.compareTo(a[i]) <= 0){
                i--;
            }else{
                break;
            }
        }
        return i;
    }
     
    public void mergeAt(int x){
        int base1 = runsBase[x];
        int len1 = runsLen[x];
         
        int base2 = runsBase[x+1];
        int len2 = runsLen[x+1];
         
        //合并run[x]和run[x+1],合并后base不用变,长度需要发生变化
        runsLen[x] = len1 + len2; 
        if(stackTop == x + 3){
            //栈顶元素下移，省去了合并后的先出栈，再入栈
            runsBase[x+1] = runsBase[x+2];
            runsLen[x+1] = runsLen[x+2];
        }
        stackTop--;
         
        //飞奔模式，减小归并的长度
        int from = gallopLeft(a, base1, len1, a[base2]);
        if(from == base1+len1){
            return;
        }
        int to = gallopRight(a, base2, len2, a[base1+len1-1]);
         
        //对两个需要归并的片段长度进行归并
        System.arraycopy(a, from, aux, from, to - from + 1);
        int i = from;
        int iend = base1 + len1 - 1;
         
        int j = base2;
        int jend = to;
         
        int k = from;
        int kend = to;
         
        while(k <= kend){
            if(i > iend){
                a[k] = aux[j++];
            }else
            if(j > jend){
                a[k] = aux[i++];
            }else
            if(aux[i].compareTo(aux[j]) <= 0){//等号保证排序的稳定性
                a[k] = aux[i++];
            }else{
                a[k] = aux[j++];
            }
            k++;
        }
    }
     
    //强制归并已入栈的序列
    private void forceMerge(){
        while(stackTop > 1){
            mergeAt(stackTop-2);
        }
    }
     
    //timSort的主方法
    public void timSort(){
        //n表示剩余长度
        int n = a.length; 
         
        if(n < 2){
            return;
        }
         
        //待排序的长度小于MIN_MERGE,直接采用插入排序完成
        if(n < MIN_MERGE){
            insertSort(a, 0, 0, a.length-1);
            return;
        }
         
        int base = 0;
        while(n > 0){
            int len = maxAscendingLen(a, base);
            if(len < MIN_MERGE){
                int abscent = n > MIN_MERGE ?  MIN_MERGE - len : n - len;
                insertSort(a, base, base + len-1, abscent);
                len = len + abscent;
            }
            pushRun(base, len);
            n = n - len;
            base = base + len;
             
            int x;
            while((x  = needMerge()) >= 0 ){
                mergeAt(x);
            }
        }
        forceMerge();
    }
     
    public static void main(String[] args){
         
        //随机产生测试用例
        Random rnd = new Random(System.currentTimeMillis());
        boolean flag = true;
        while(flag){
             
            //首先产生一个全部有序的数组
            Integer[] arr1 = new Integer[1000];
            for(int i = 0; i < arr1.length; i++){
                arr1[i] = i;
            }
             
            //有序的基础上随机交换一些值
            for(int i = 0; i < (int)(0.1*arr1.length); i++){
                int x,y,tmp;
                x = rnd.nextInt(arr1.length);
                y = rnd.nextInt(arr1.length);
                tmp = arr1[x];
                arr1[x] = arr1[y];
                arr1[y] = tmp;
            }
             
            //逆序部分数据
            for(int i = 0; i <(int)(0.05*arr1.length); i++){
                int x = rnd.nextInt(arr1.length);
                int y = rnd.nextInt((int)(arr1.length*0.01)+x);
                if(y >= arr1.length){
                    continue;
                }
                while(x < y){
                    int tmp;
                    tmp = arr1[x];
                    arr1[x] = arr1[y];
                    arr1[y] = tmp;
                    x++;
                    y--;
                }
            }
             
            Integer[] arr2 = arr1.clone();
            Integer[] arr3 = arr1.clone();
            Arrays.sort(arr2);
             
            SimpleTimSort<Integer> sts = new SimpleTimSort<Integer>(arr1);
            sts.timSort();
             
            //比较SimpleTimSort排序和库函数提供的排序结果比较是否一致
            //如果没有打印任何结果，说明排序结果正确
            if(!Arrays.deepEquals(arr1, arr2)){
                for(int i = 0; i < arr1.length; i++){
                    if(!arr1[i].equals(arr2[i])){
                        System.out.printf("%d: arr1 %d  arr2 %d\n",i,arr1[i],arr2[i]);
                    }
                }
                System.out.println(Arrays.deepToString(arr3));
                flag = false;
            }
        }
    }
}

3. TimSort 알고리즘이 주의해야 할 문제

TimSort 알고리즘은 두 개의 연속된 조각만 병합합니다. 알고리즘 안정성을 보장합니다.

최소 병합 길이와 스택 길이 사이에는 일정한 관계가 있습니다. 최소 병합 길이를 늘리면 스택 길이도 늘려야 합니다. 그렇지 않으면 스택이 발생할 위험이 있습니다. 범위를 벗어났습니다(코드의 스택은 배열을 사용하여 구현된 길이 40으로 전달됨).

4. TimSort 알고리즘의 정식 버전

사실 TimSort 알고리즘의 정식 버전은 위에서 언급한 간단한 TimSort 알고리즘에 대해 많은 최적화가 이루어졌습니다. 예를 들어, 정렬된 시퀀스가 ​​최소 병합 길이보다 작은 경우 이진 검색과 유사한 방법을 사용하여 배열 길이를 확장하기 위해 삽입해야 하는 위치를 찾을 수 있습니다. 또 다른 예는 갤로핑 모드에서 이진 검색을 사용하여 첫 번째 시퀀스에서 두 번째 시퀀스의 첫 번째 요소 위치를 찾는 동시에 더 작은 보조 공간을 사용하여 병합을 완료할 수 있다는 것입니다. Java의 소스 코드 보기 와서 배워보세요.