Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

116
LINES

< > BotCompany Repo | #1029416 // timSortIntArrayWithComparator

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (157L/2K).

scope timSortIntArrayWithComparator.

// not actually Timsort, but works well

// This code has been contributed by 29AjayKumar 
// from: https://www.geeksforgeeks.org/timsort/

static final int #RUN = 32; 

// this function sorts array from left index to  
// to right index which is of size atmost RUN  
svoid #insertionSort(int[] arr, IntComparator comparator, int left, int right) { 
    for (int i = left + 1; i <= right; i++)  
    { 
        int temp = arr[i]; 
        int j = i - 1; 
        while (j >= left && comparator.compare(arr[j], temp) > 0)
        { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = temp; 
    } 
} 

// merge function merges the sorted runs  
svoid #merge(int[] arr, IntComparator comparator, 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 (comparator.compare(left[i], right[j]) <= 0)
        { 
            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)  
svoid timSortIntArrayWithComparator(int[] arr, int n default lIntArray(arr), IntComparator comparator) { 
    // Sort individual subarrays of size RUN  
    for (int i = 0; i < n; i += RUN)  
    { 
        insertionSort(arr, comparator, i, Math.min((i + 31), (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)  
    { 
      ifdef timSort_debug
        print("size=" + size);
      endifdef
          
        // 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 = Math.min(left + size - 1, n - 1);
            int right = Math.min(left + 2 * size - 1, n - 1); 

            // merge sub array arr[left.....mid] &  
            // arr[mid+1....right]  
            merge(arr, comparator, left, mid, right); 
        } 
    } 
}

end scope

Author comment

Began life as a copy of #1029412

download  show line numbers  debug dex  old transpilations   

Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv

No comments. add comment

Snippet ID: #1029416
Snippet name: timSortIntArrayWithComparator
Eternal ID of this version: #1029416/4
Text MD5: 470ae87db6575130c460f5565e1af998
Transpilation MD5: 4d2ac067974fad06a7c423527e144db7
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2023-02-12 13:07:57
Source code size: 3286 bytes / 116 lines
Pitched / IR pitched: No / No
Views / Downloads: 225 / 496
Version history: 3 change(s)
Referenced in: [show references]