Рубрики

TimSort

TimSort является алгоритмом сортировки на основе вставки Сортировки и Merge Сортировки .

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

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

Подробности ниже реализации:

  • Мы считаем размер пробега 32.
  • Мы один за другим сортируем кусочки размером, равным пробегу
  • После сортировки отдельных частей мы объединяем их одну за другой. Мы удваиваем размер объединенных подмассивов после каждой итерации.

C ++

// C ++ программа для выполнения TimSort.
#include<bits/stdc++.h>

using namespace std;

const int RUN = 32;

  
// эта функция сортирует массив из левого индекса в
// к правому индексу, размер которого не превышает 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 (arr[j] > temp && j >= left)

        {

            arr[j+1] = arr[j];

            j--;

        }

        arr[j+1] = temp;

    }

}

  
// функция слияния объединяет отсортированные прогоны

void merge(int arr[], int l, int m, int r)

{

    // исходный массив разбит на две части

    // левый и правый массив

    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;

  

    // после сравнения мы объединяем эти два массива

    // в большем подмассиве

    while (i < len1 && j < len2)

    {

        if (left[i] <= right[j])

        {

            arr[k] = left[i];

            i++;

        }

        else

        {

            arr[k] = right[j];

            j++;

        }

        k++;

    }

  

    // копируем оставшиеся элементы left, если есть

    while (i < len1)

    {

        arr[k] = left[i];

        k++;

        i++;

    }

  

    // копируем оставшийся элемент right, если есть

    while (j < len2)

    {

        arr[k] = right[j];

        k++;

        j++;

    }

}

  
// итеративная функция Timsort для сортировки
// массив [0 ... n-1] (аналог сортировки слиянием)

void timSort(int arr[], int n)

{

    // Сортировка отдельных подмассивов по размеру RUN

    for (int i = 0; i < n; i+=RUN)

        insertionSort(arr, i, min((i+31), (n-1)));

  

    // начинаем слияние с размера RUN (или 32). Будет сливаться

    // сформировать размер 64, затем 128, 256 и т. д.

    for (int size = RUN; size < n; size = 2*size)

    {

        // выбрать начальную точку левого подмассива. Мы

        // собираемся объединить arr [left..left + size-1]

        // и arr [left + size, left + 2 * size-1]

        // После каждого слияния мы увеличиваем влево на 2 * размер

        for (int left = 0; left < n; left += 2*size)

        {

            // найти конечную точку левого подмассива

            // середина + 1 - начальная точка правого подмассива

            int mid = left + size - 1;

            int right = min((left + 2*size - 1), (n-1));

  

            // объединить подмассив arr [left ..... mid] &

            // arr [mid + 1 .... right]

            merge(arr, left, mid, right);

        }

    }

}

  
// утилита для печати массива

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        printf("%d  ", arr[i]);

    printf("\n");

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {5, 21, 7, 23, 19};

    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Given Array is\n");

    printArray(arr, n);

  

    timSort(arr, n);

  

    printf("After Sorting Array is\n");

    printArray(arr, n);

    return 0;

}

Джава

// Java-программа для выполнения TimSort.

class GFG 

{

  

    static int RUN = 32;

  

    // эта функция сортирует массив из левого индекса в

    // к правому индексу, размер которого не превышает 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 (arr[j] > temp && j >= left)

            {

                arr[j + 1] = arr[j];

                j--;

            }

            arr[j + 1] = temp;

        }

    }

  

    // функция слияния объединяет отсортированные прогоны

    public static void merge(int[] arr, 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] = 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;

  

        // после сравнения мы объединяем эти два массива

        // в большем подмассиве

        while (i < len1 && j < len2) 

        {

            if (left[i] <= right[j]) 

            {

                arr[k] = left[i];

                i++;

            }

            else 

            {

                arr[k] = right[j];

                j++;

            }

            k++;

        }

  

        // копируем оставшиеся элементы left, если есть

        while (i < len1)

        {

            arr[k] = left[i];

            k++;

            i++;

        }

  

        // копируем оставшийся элемент right, если есть

        while (j < len2) 

        {

            arr[k] = right[j];

            k++;

            j++;

        }

    }

  

    // итеративная функция Timsort для сортировки

    // массив [0 ... n-1] (аналог сортировки слиянием)

    public static void timSort(int[] arr, int n) 

    {

          

        // Сортировка отдельных подмассивов по размеру RUN

        for (int i = 0; i < n; i += RUN) 

        {

            insertionSort(arr, i, Math.min((i + 31), (n - 1)));

        }

  

        // начинаем слияние с размера RUN (или 32). Будет сливаться

        // сформировать размер 64, затем 128, 256 и т. д.

        for (int size = RUN; size < n; size = 2 * size) 

        {

              

            // выбрать начальную точку левого подмассива. Мы

            // собираемся объединить arr [left..left + size-1]

            // и arr [left + size, left + 2 * size-1]

            // После каждого слияния мы увеличиваем влево на 2 * размер

            for (int left = 0; left < n; left += 2 * size) 

            {

                  

                // найти конечную точку левого подмассива

                // середина + 1 - начальная точка правого подмассива

                int mid = left + size - 1;

                int right = Math.min((left + 2 * size - 1), (n - 1));

  

                // объединить подмассив arr [left ..... mid] &

                // arr [mid + 1 .... right]

                merge(arr, left, mid, right);

            }

        }

    }

  

    // утилита для печати массива

    public static void printArray(int[] arr, int n)

    {

        for (int i = 0; i < n; i++)

        {

            System.out.print(arr[i] + " ");

        }

        System.out.print("\n");

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int[] arr = {5, 21, 7, 23, 19};

        int n = arr.length;

        System.out.print("Given Array is\n");

        printArray(arr, n);

  

        timSort(arr, n);

  

        System.out.print("After Sorting Array is\n");

        printArray(arr, n);

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для выполнения TimSort.

RUN = 32 

    
# Эта функция сортирует массив из левого индекса в
# к правому индексу, который имеет размер не более RUN

def insertionSort(arr, left, right): 

   

    for i in range(left + 1, right+1): 

       

        temp = arr[i] 

        j = i - 1 

        while arr[j] > temp and j >= left: 

           

            arr[j+1] = arr[j] 

            j -= 1

           

        arr[j+1] = temp 

    
# функция слияния объединяет отсортированные прогоны

def merge(arr, l, m, r):

   

    # оригинальный массив разбит на две части

    # левый и правый массив

    len1, len2 =  m - l + 1, r -

    left, right = [], [] 

    for i in range(0, len1): 

        left.append(arr[l + i]) 

    for i in range(0, len2): 

        right.append(arr[m + 1 + i]) 

    

    i, j, k = 0, 0, l

    # после сравнения мы объединяем эти два массива

    # в большем подмассиве

    while i < len1 and j < len2: 

       

        if left[i] <= right[j]: 

            arr[k] = left[i] 

            i += 1 

           

        else:

            arr[k] = right[j] 

            j += 1 

           

        k += 1

       

    # копировать оставшиеся элементы left, если есть

    while i < len1: 

       

        arr[k] = left[i] 

        k += 1 

        i += 1

    

    # скопировать оставшийся элемент right, если есть

    while j < len2: 

        arr[k] = right[j] 

        k += 1

        j += 1

      
# итеративная функция Timsort для сортировки
# array [0 ... n-1] (аналог сортировки слиянием)

def timSort(arr, n): 

   

    # Сортировать отдельные подмассивы размера RUN

    for i in range(0, n, RUN): 

        insertionSort(arr, i, min((i+31), (n-1))) 

    

    # начать слияние с размером RUN (или 32). Будет сливаться

    # чтобы сформировать размер 64, затем 128, 256 и так далее ....

    size = RUN

    while size < n: 

       

        # выбрать начальную точку левого подмассива. Мы

        # собираемся объединить arr [left..left + size-1]

        # и arr [слева + размер, слева + 2 * размер-1]

        # После каждого слияния мы увеличиваем оставленный размер на 2 *

        for left in range(0, n, 2*size): 

           

            # найти конечную точку левого подмассива

            # mid + 1 - начальная точка правого подмассива

            mid = left + size - 1 

            right = min((left + 2*size - 1), (n-1)) 

    

            # объединить подмассив arr [left ..... mid] &

            # обр [середина + 1 .... справа]

            merge(arr, left, mid, right) 

          

        size = 2*size

           
# служебная функция для печати массива

def printArray(arr, n): 

   

    for i in range(0, n): 

        print(arr[i], end = " "

    print() 

   

    
# Программа драйвера для проверки вышеуказанной функции

if __name__ == "__main__":

   

    arr = [5, 21, 7, 23, 19

    n = len(arr) 

    print("Given Array is"

    printArray(arr, n) 

    

    timSort(arr, n) 

    

    print("After Sorting Array is"

    printArray(arr, n) 

      
# Этот код предоставлен Rituraj Jain

C #

// C # программа для выполнения TimSort.

using System; 

   

class GFG 

    public const int RUN = 32;

      

    // эта функция сортирует массив из левого индекса в

    // к правому индексу, размер которого не превышает 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 (arr[j] > temp && j >= left) 

            

                arr[j+1] = arr[j]; 

                j--; 

            

            arr[j+1] = temp; 

        

    

        

    // функция слияния объединяет отсортированные прогоны

    public static void merge(int[] arr, 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] = 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; 

        

        // после сравнения мы объединяем эти два массива

        // в большем подмассиве

        while (i < len1 && j < len2) 

        

            if (left[i] <= right[j]) 

            

                arr[k] = left[i]; 

                i++; 

            

            else

            

                arr[k] = right[j]; 

                j++; 

            

            k++; 

        

        

        // копируем оставшиеся элементы left, если есть

        while (i < len1) 

        

            arr[k] = left[i]; 

            k++; 

            i++; 

        

        

        // копируем оставшийся элемент right, если есть

        while (j < len2) 

        

            arr[k] = right[j]; 

            k++; 

            j++; 

        

    

        

    // итеративная функция Timsort для сортировки

    // массив [0 ... n-1] (аналог сортировки слиянием)

    public static void timSort(int[] arr, int n) 

    

        // Сортировка отдельных подмассивов по размеру RUN

        for (int i = 0; i < n; i+=RUN) 

            insertionSort(arr, i, Math.Min((i+31), (n-1))); 

        

        // начинаем слияние с размера RUN (или 32). Будет сливаться

        // сформировать размер 64, затем 128, 256 и т. д.

        for (int size = RUN; size < n; size = 2*size) 

        

            // выбрать начальную точку левого подмассива. Мы

            // собираемся объединить arr [left..left + size-1]

            // и arr [left + size, left + 2 * size-1]

            // После каждого слияния мы увеличиваем влево на 2 * размер

            for (int left = 0; left < n; left += 2*size) 

            

                // найти конечную точку левого подмассива

                // середина + 1 - начальная точка правого подмассива

                int mid = left + size - 1; 

                int right = Math.Min((left + 2*size - 1), (n-1)); 

        

                // объединить подмассив arr [left ..... mid] &

                // arr [mid + 1 .... right]

                merge(arr, left, mid, right); 

            

        

    

        

    // утилита для печати массива

    public static void printArray(int[] arr, int n) 

    

        for (int i = 0; i < n; i++) 

            Console.Write(arr[i] + " "); 

        Console.Write("\n"); 

    

        

    // Программа драйвера для проверки вышеуказанной функции

      

    public static void Main()

    {

        int[] arr = {5, 21, 7, 23, 19}; 

        int n = arr.Length;

        Console.Write("Given Array is\n"); 

        printArray(arr, n); 

        

        timSort(arr, n); 

        

        Console.Write("After Sorting Array is\n"); 

        printArray(arr, n); 

    }

      

    // Этот код предоставлен DrRoot_

}

Выход:

Given Array is
5  21  7  23  19
After Sorting Array is
5  7  19  21  23

Ссылки :
https://svn.python.org/projects/python/trunk/Objects/listsort.txt
https://en.wikipedia.org/wiki/Timsort#Minimum_size_.28minrun.29

Эта статья предоставлена Адитьей Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

TimSort

0.00 (0%) 0 votes