In this tutorial you will learn about the Tim Sort Algorithm and its application with practical example.
Tim Sort Program In C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include<stdio.h> const int run = 32; int minimum(int a, int b) { if(a<b) return a; else return b; } void insertion_sort(int a[], int beg, int end) { int temp, i, j; for (i = beg + 1; i <= end; i++) { temp = a[i]; j = i - 1; while (a[j] > temp && j >= beg) { a[j+1] = a[j]; j--; } a[j+1] = temp; } } void merge(int a[], int left, int mid, int right) { int len1 = mid - left + 1, len2 = right - mid; int beg[len1], end[len2]; int i,j,k; for (i = 0; i < len1; i++) beg[i] = a[left + i]; for (i = 0; i < len2; i++) end[i] = a[mid + 1 + i]; i = 0; j = 0; k = left; while (i < len1 && j < len2) { if (beg[i] <= end[j]) { a[k] = beg[i]; i++; } else { a[k] = end[j]; j++; } k++; } while (i < len1) { a[k] = beg[i]; k++; i++; } while (j < len2) { a[k] = end[j]; k++; j++; } } void tim_sort(int a[], int n) { int i,size,beg,mid,end; for (i = 0; i < n; i+=run) insertion_sort(a, i, minimum((i+31), (n-1))); for (size = run; size < n; size = 2*size) { for (beg = 0; beg < n; beg += 2*size) { mid = beg + size - 1; end = minimum((beg + 2*size - 1), (n-1)); merge(a, beg, mid, end); } } } int main() { int i, n, a[10]; printf("Enter number of elements: "); scanf("%d",&n); printf("Enter %d integer numbers\n", n); for(i = 0; i < n; i++) { scanf("%d",&a[i]); } tim_sort(a, n); printf("Elements after sorting: "); for (i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); return 0; } |
Output:-
