TimSort

Опубликовано: 19 Января, 2022

TimSort - это алгоритм сортировки, основанный на сортировке вставкой и сортировке слиянием.

Стабильный алгоритм сортировки работает за время O (n Log n)
Используется в Java Arrays.sort (), а также в Python sorted () и sort ().
Сначала отсортируйте небольшие фрагменты с помощью сортировки вставкой, затем объедините фрагменты, используя сортировку слияния или слияния.

Мы делим массив на блоки, известные как Run . Мы сортируем эти прогоны, используя сортировку вставкой, один за другим, а затем объединяем эти прогоны, используя функцию объединения, используемую в сортировке слиянием. Если размер массива меньше размера run, то он сортируется только с помощью сортировки вставкой. Размер прогона может варьироваться от 32 до 64 в зависимости от размера массива. Обратите внимание, что функция слияния хорошо работает, когда размер подмассивов равен степени 2. Идея основана на том факте, что сортировка вставкой хорошо работает для небольших массивов.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Details of below implementation:

We consider size of run as 32.
We one by one sort pieces of size equal to run
After sorting individual pieces, we merge them one by one. We double the size of merged subarrays after every iteration.

C++

// C++ program to perform TimSort.
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32;
 
// This function sorts array from left index to
// to right index which is of size atmost RUN
void insertionSort(int arr[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        int temp = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > temp)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}
 
// Merge function merges the sorted runs
void merge(int arr[], int l, int m, int r)
{
     
    // Original array is broken in two parts
    // left and right array
    int len1 = m - l + 1, len2 = r - m;
    int left[len1], right[len2];
    for (int i = 0; i < len1; i++)
        left[i] = arr[l + i];
    for (int i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i];
 
    int i = 0;
    int j = 0;
    int k = l;
 
    // After comparing, we
    // merge those two array
    // in larger sub array
    while (i < len1 && j < len2)
    {
        if (left[i] <= right[j])
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
 
    // Copy remaining elements of left, if any
    while (i < len1)
    {
        arr[k] = left[i];
        k++;
        i++;
    }
 
    // Copy remaining element of right, if any
    while (j < len2)
    {
        arr[k] = right[j];
        k++;
        j++;
    }
}
 
// Iterative Timsort function to sort the
// array[0...n-1] (similar to merge sort)
void timSort(int arr[], int n)
{
     
    // Sort individual subarrays of size RUN
    for (int i = 0; i < n; i+=RUN)
        insertionSort(arr, i, min((i+RUN-1),
                                    (n-1)));
 
    // Start merging from size RUN (or 32).
    // It will merge
    // to form size 64, then 128, 256
    // and so on ....
    for (int size = RUN; size < n;
                             size = 2*size)
    {
         
        // pick starting point of
        // left sub array. We
        // are going to merge
        // arr[left..left+size-1]
        // and arr[left+size, left+2*size-1]
        // After every merge, we
        // increase left by 2*size
        for (int left = 0; left < n;
                             left += 2*size)
        {
             
            // find ending point of
            // left sub array
            // mid+1 is starting point
            // of right sub array
            int mid = left + size - 1;
            int right = min((left + 2*size - 1),
                                            (n-1));
 
            // merge sub array arr[left.....mid] &
            // arr[mid+1....right]
              if(mid < right)
                merge(arr, left, mid, right);
        }
    }
}
 
// Utility function to print the Array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d  ", arr[i]);
    printf("
");
}
 
// Driver program to test above function
int main()
{
    int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7,
                       -4, -13, 5, 8, -14, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Given Array is
");
    printArray(arr, n);
 
    // Function Call
    timSort(arr, n);
 
    printf("After Sorting Array is
");
    printArray(arr, n);
    return 0;
}

Java

// Java program to perform TimSort.
class GFG
{
 
    static int MIN_MERGE = 32;
 
    public static int minRunLength(int n)
    {
        assert n >= 0;
       
        // Becomes 1 if any 1 bits are shifted off
        int r = 0;
        while (n >= MIN_MERGE)
        {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }
 
    // This function sorts array from left index to
    // to right index which is of size atmost RUN
    public static void insertionSort(int[] arr, int left,
                                     int right)
    {
        for (int i = left + 1; i <= right; i++)
        {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }
 
    // Merge function merges the sorted runs
    public static void merge(int[] arr, int l,
                                 int m, int r)
    {
        // Original array is broken in two parts
        // left and right array
        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] = arr[l + x];
        }
        for (int x = 0; x < len2; x++)
        {
            right[x] = arr[m + 1 + x];
        }
 
        int i = 0;
        int j = 0;
        int k = l;
 
        // After comparing, we merge those two array
        // in larger sub array
        while (i < len1 && j < len2)
        {
            if (left[i] <= right[j])
            {
                arr[k] = left[i];
                i++;
            }
            else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
 
        // Copy remaining elements
        // of left, if any
        while (i < len1)
        {
            arr[k] = left[i];
            k++;
            i++;
        }
 
        // Copy remaining element
        // of right, if any
        while (j < len2)
        {
            arr[k] = right[j];
            k++;
            j++;
        }
    }
 
    // Iterative Timsort function to sort the
    // array[0...n-1] (similar to merge sort)
    public static void timSort(int[] arr, int n)
    {
        int minRun = minRunLength(MIN_MERGE);
       
        // Sort individual subarrays of size RUN
        for (int i = 0; i < n; i += minRun)
        {
            insertionSort(arr, i,
                          Math.min((i + MIN_MERGE - 1), (n - 1)));
        }
 
        // Start merging from size
        // RUN (or 32). It will
        // merge to form size 64,
        // then 128, 256 and so on
        // ....
        for (int size = minRun; size < n; size = 2 * size)
        {
 
            // Pick starting point
            // of left sub array. We
            // are going to merge
            // arr[left..left+size-1]
            // and arr[left+size, left+2*size-1]
            // After every merge, we
            // increase left by 2*size
            for (int left = 0; left < n;
                                 left += 2 * size)
            {
 
                // Find ending point of left sub array
                // mid+1 is starting point of right sub
                // array
                int mid = left + size - 1;
                int right = Math.min((left + 2 * size - 1),
                                     (n - 1));
 
                // Merge sub array arr[left.....mid] &
                // arr[mid+1....right]
                  if(mid < right)
                    merge(arr, left, mid, right);
            }
        }
    }
 
    // Utility function to print the Array
    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.print("
");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { -2, 7,  15,  -14, 0, 15,  0, 7,
                      -7, -4, -13, 5,   8, -14, 12 };
        int n = arr.length;
        System.out.println("Given Array is");
        printArray(arr, n);
 
        timSort(arr, n);
 
        System.out.println("After Sorting Array is");
        printArray(arr, n);
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to perform basic timSort
MIN_MERGE = 32
 
def calcMinRun(n):
    """Returns the minimum length of a
    run from 23 - 64 so that
    the len(array)/minrun is less than or
    equal to a power of 2.
 
    e.g. 1=>1, ..., 63=>63, 64=>32, 65=>33,
    ..., 127=>64, 128=>32, ...
    """
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r
 
 
# This function sorts array from left index to
# to right index which is of size atmost RUN
def insertionSort(arr, left, right):
    for i in range(left + 1, right + 1):
        j = i
        while j > left and arr[j] < arr[j - 1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1

                    
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИ
                                    