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

117
LINES

< > BotCompany Repo | #1029412 // timSortIntArray

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

Transpiled version (188L) is out of date.

1  
scope timSortIntArray.
2  
3  
// not actually Timsort, but works well
4  
5  
// This code has been contributed by 29AjayKumar 
6  
// from: https://www.geeksforgeeks.org/timsort/
7  
8  
static final int #RUN = 32; 
9  
10  
// this function sorts array from left index to  
11  
// to right index which is of size atmost RUN  
12  
svoid #insertionSort(int[] arr, int left, int right) { 
13  
    for (int i = left + 1; i <= right; i++)  
14  
    { 
15  
        int temp = arr[i]; 
16  
        int j = i - 1; 
17  
        while (j >= left && arr[j] > temp) 
18  
        { 
19  
            arr[j + 1] = arr[j]; 
20  
            j--; 
21  
        } 
22  
        arr[j + 1] = temp; 
23  
    } 
24  
} 
25  
26  
// merge function merges the sorted runs  
27  
svoid #merge(int[] arr, int l,  
28  
                            int m, int r) { 
29  
    // original array is broken in two parts  
30  
    // left and right array  
31  
    int len1 = m - l + 1, len2 = r - m; 
32  
    int[] left = new int[len1]; 
33  
    int[] right = new int[len2]; 
34  
    for (int x = 0; x < len1; x++)  
35  
    { 
36  
        left[x] = arr[l + x]; 
37  
    } 
38  
    for (int x = 0; x < len2; x++)  
39  
    { 
40  
        right[x] = arr[m + 1 + x]; 
41  
    } 
42  
43  
    int i = 0; 
44  
    int j = 0; 
45  
    int k = l; 
46  
47  
    // after comparing, we merge those two array  
48  
    // in larger sub array  
49  
    while (i < len1 && j < len2)  
50  
    { 
51  
        if (left[i] <= right[j])  
52  
        { 
53  
            arr[k] = left[i]; 
54  
            i++; 
55  
        } 
56  
        else 
57  
        { 
58  
            arr[k] = right[j]; 
59  
            j++; 
60  
        } 
61  
        k++; 
62  
    } 
63  
64  
    // copy remaining elements of left, if any  
65  
    while (i < len1) 
66  
    { 
67  
        arr[k] = left[i]; 
68  
        k++; 
69  
        i++; 
70  
    } 
71  
72  
    // copy remaining element of right, if any  
73  
    while (j < len2)  
74  
    { 
75  
        arr[k] = right[j]; 
76  
        k++; 
77  
        j++; 
78  
    } 
79  
} 
80  
81  
// iterative Timsort function to sort the  
82  
// array[0...n-1] (similar to merge sort)  
83  
svoid timSortIntArray(int[] arr, int n default lIntArray(arr)) { 
84  
    // Sort individual subarrays of size RUN  
85  
    for (int i = 0; i < n; i += RUN)  
86  
    { 
87  
        insertionSort(arr, i, Math.min((i + 31), (n - 1))); 
88  
    } 
89  
90  
    // start merging from size RUN (or 32). It will merge  
91  
    // to form size 64, then 128, 256 and so on ....  
92  
    for (int size = RUN; size < n; size = 2 * size)  
93  
    { 
94  
      ifdef timSort_debug
95  
        print("size=" + size);
96  
      endifdef          
97  
        // pick starting point of left sub array. We  
98  
        // are going to merge arr[left..left+size-1]  
99  
        // and arr[left+size, left+2*size-1]  
100  
        // After every merge, we increase left by 2*size  
101  
        for (int left = 0; left < n; left += 2 * size)  
102  
        { 
103  
              
104  
            // find ending point of left sub array  
105  
            // mid+1 is starting point of right sub array  
106  
            int mid = min(left + size - 1, n - 1);
107  
            int right = Math.min(left + 2 * size - 1, n - 1); 
108  
            //if (right < mid || mid < left) fail("Overflow at " + n2(left) + "/" + size + ". mid=" + n2(mid) + ", right=" + n2(right));
109  
110  
            // merge sub array arr[left.....mid] &  
111  
            // arr[mid+1....right]  
112  
            merge(arr, left, mid, right); 
113  
        } 
114  
    } 
115  
}
116  
117  
end scope

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: #1029412
Snippet name: timSortIntArray
Eternal ID of this version: #1029412/12
Text MD5: 140490b9181fbcfd63a31dad151bd59a
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-03-25 20:35:14
Source code size: 3275 bytes / 117 lines
Pitched / IR pitched: No / No
Views / Downloads: 221 / 398
Version history: 11 change(s)
Referenced in: [show references]