Tim sort presentation.pdf

This is a tim sort presentation slide. Hopefully this will help you.

1. Course Title: Data Structure Lab
Course Code: ICT-1206
Presentation By:
Misu Das Partha
IT20007
ShouvikDatta
IT20023
Dept. of ICT, MBSTU
Presentation To:
BikashKumar Paul
Lecturer,
Dept. of ICT, MBSTU
Date: 1/10/2022

2. TOPIC NAME : TIM SORT
1

3. CONTENTS
TOPIC
INTRODUCTION
PRESENTATION
CODE
2

4. INTRODUCTION
TIM SORT IS A DATA SORTING ALGORITHM.
THIS SORTING STRATEGY IS TO IDENTIFY DATA MEMBERS AND
SORT THEM FURTHER USING BOTH MERGE AND INSERT METHODS.
TIM SORT IS ONE OF THE BEST SORTING ALGORITHMS IN TERMS
OF COMPLEXITY AND STABILITY.
3

5. TIM SORT WORKING WITH EXAMPLES
14 15 454 3029 33 4027 28
4

6. TIM SORT WORKING WITH EXAMPLES
14 15
45
4
3029 33 40
27 28
Run = 5
Part-1
Part-2
5

7. FIRSTLY WE ARE SORTING PART-1 ELEMENTS
6

8. TIM SORT WORKING WITH EXAMPLES
14 15 427 28
27 15 414 28
1
st
iteration
7

9. TIM SORT WORKING WITH EXAMPLES
14 15 427 28
14 15 427 28
2
nd
iteration
8

10. TIM SORT WORKING WITH EXAMPLES
27 15 414 28
14 15 427 28
3
rd
iteration
9

11. TIM SORT WORKING WITH EXAMPLES
27 15 414 28
14 28 415 27
4
th
iteration
10

12. TIM SORT WORKING WITH EXAMPLES
15 28 414 27
4 27 2814 15
5
th
iteration
11

13. PART-1 ELEMENTS SORTED
12

14. NOW WE ARE SORTING PART-2 ELEMENTS
13

15. TIM SORT WORKING WITH EXAMPLES
29 33 4045 30
29 33 4045 30
1
st
iteration
14

16. TIM SORT WORKING WITH EXAMPLES
29 33 4045 30
45 33 4029 30
2
nd
iteration
15

17. TIM SORT WORKING WITH EXAMPLES
45 33 4029 30
30 33 4029 45
3
rd
iteration
16

18. TIM SORT WORKING WITH EXAMPLES
30 33 4029 45
30 45 4029 33
4
th
iteration
17

19. TIM SORT WORKING WITH EXAMPLES
30 45 4029 33
30 40 4529 33
5
th
iteration
18

20. PART-2 ELEMENTS SORTED
19

21. NOW WE HAVE TO MERGE PART-1 ELEMENTS
& PART-2 ELEMENTS
20

22. 4 27 2814 15 30 40 4529 33
Merged Array
4
21

23. 27 2814 15 30 40 4529 33
Merged Array
4 14
22

24. 27 2815 30 40 4529 33
Merged Array
4 14 15
23

25. 27 28 30 40 4529 33
Merged Array
4 14 15 27
24

26. 28 30 40 4529 33
Merged Array
4 14 15 27 28
25

27. 30 40 4529 33
Merged Array
4 14 15 27 28
26
30 33 4029 45

28. Merged Array
4 14 15 27 28 30 33 4029 45
27

29. 28
Code
void timSort(intarr[ ], intn){
for (inti= 0; i< n; i+=RUN)
insertionSort(arr, i, min((i+31), (n-1)));
for (intsize = RUN; size < n; size = 2*size) {
for (intleft = 0; left < n; left += 2*size) {
intmid = left + size -1;
intright = min((left + 2*size -1), (n-1));
merge(arr, left, mid, right); }
}
}
intmain( ){
intarr[ ] = {27, 14, 28, 15, 4, 45, 29, 30, 33, 40};
intn = 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;}

30. COMPLEXITY OF TIMSORT
Case Time complexity
Best Case O(n)
Average Case O(nlogn)
Worst Case O(nlogn)
SpaceComplexity O(n)
29

31. THANK YOU FOR WATCHING THIS
PRESENTATION