Insertion sort and shell sort

Sorting
Performance parameters
Insertion Sort
Technique
Algorithm
Performance with examples
Applications
Example Program
Shell Sort
Technique
Algorithm
Performance with examples
Applications
Example Program

1. Insertion Sort and Shell Sort Done by, C.Balaji 15E105 S.Deepak Arumugam 15E108 J.Karthickraja 15E117 S.Praveenkumar 15E137 Dhineshkumar 16E404 Y.Elangovan 16E501 1

2. Overview Sorting Performance parameters Insertion Sort Technique Algorithm Performance with examples Applications Example Program Shell Sort Technique Algorithm Performance with examples Applications Example Program 2

3. Sorting Sorting refers to arranging things according to different classes. In computer science, sorting deals with arranging elements of a list or a set of records of a file in the ascending order or descending order. There are two types of sorting based on the size of list Internal Sorting, when the size of list is small External Sorting, when the size is voluminous The internal sorting algorithms are grouped into one of these families Sorting by exchange Sorting by distribution Sorting by selection Sorting by insertion 3

4. Performance parameters Time Complexity Best Case , when the list is sorted already Average Case Worst Case , when the list is in the reverse order Stability 4

5. Time Complexity The time complexity of an algorithm is a function of the running time of the algorithm. It is computed using apriori analysis, where the total frequency count is only taken into account. The frequency count f i of each statement of the algorithm is computed and summed up to obtain the total frequency count T = I . The time complexity is represented using asymptotic notations.   5

6. Stability When the relative positions of the key with the same value in the ordered list is maintained in the sorted list, the algorithm is said to be stable. 6

7. Insertion Sort As the name indicates, this algorithm belongs to the family of sorting by insertion. This algorithm sorts a set of keys by inserting keys into an sorted sub list. The keys are considered one at a time, and each new key is inserted into the appropriate position relative to the previously sorted keys. Online ; i.e., can sort a list as it receives it 7

8. Technique Consider an unordered list { K 1 , K 2 , K 3 ,… , K n }. In the first pass, K 2 is compared with its sorted sublist of predecessors, i.e., {K 1 }, and K 2 inserts itself at the position to give the list {K 1 ,K 2 }. In the next pass, K 3 is compared with its sorted sublist of predecessors, i.e., {K 1 ,K 2 }, and K 3 is inserted at the appropriate position to give the list { K 1 ,K 2 ,K 3 }. In the (n-1) th pass, K n is compared with its sorted sublist of predecessors, i.e., { K 1 ,K 2 ,K 3 ,…,K n-1 }, and K n is inserted at the appropriate position to give the list { K 1 ,K 2 ,K 3 ,…,K n-1 ,K n }. This technique is referred as sinking or sifting 8

9. Algorithm 9

10. Example 1 10

11. 11

12. 12

13. 13

14. Example 2 14

15. Time Complexity For the best case, the list is already sorted. Therefore, there will be (n-1) passes each with 1 comparison, i.e., (n-1) comparisons in total. Therefore, the time complexity for the best case is O(n). For the worst case, in the first pass, there will be one comparison and in the second pass, there will be two comparisons and so on. For the (n-1) th pass, there will be (n-1) comparisons. The total number of comparisons = 1+2+…+(n-1) = = O(n 2 ) The average time complexity is also reported to be O(n 2 ).   15

16. Stability The insertion sort is a stable sort. The relative position of the keys with same value are retained. 16

17. Code: #include< iostream > using namespace std ; class array { int arr [100],size,j,k,sort1; public: array( int i ) { size= i ; cout <<"enter the elements \n"; for(j=0;j< size;j ++) { cout <<"enter the next element\n"; cin >>k; arr [j]=k; } } 17

18. void initialize() { cout <<"enter the array size \n"; cin >>size; cout <<"enter the elements\n"; for(j=0;j< size;j ++) { cout <<"enter the next element\n"; cin >>k; arr [j]=k; } } 18

19. void sort() { int i ; int key; for ( i = 1; i < size; i ++) { key = arr [ i ]; j = i-1; while (j >= 0 && arr [j] > key) { arr [j+1 ] = arr [j]; j = j-1 ; } arr [j+1 ] = key; for(j=0;j< size;j ++) { cout << arr [j ]<<";";} cout <<"\n"; }} 19

20. void print() { cout <<"the elements of the array are \n"; for(j=0;j< size;j ++) { cout << arr [j]<<";"; } } }; 20

21. int main() { int temp,size,con,exit ; cout <<"enter the number of elements \n"; cin >>size; array array1(size); array1.sort(); array1.print(); while(exit==0) { cout <<"do you want to continue enter \n 1 for exit \n 2 for continue"; cin >>con; switch(con) {case 1: default: exit=1; break; case 2: array1.initialize(); array1.sort(); array1.print(); break; }} return ; } 21

22. 22

23. Shell Sort Shell sort a lgorithm also belongs to the family of sorting by insertion. It was proposed by David L Shell in 1959. It is a substantial improvement over insertion sort in the sense that elements move in long strides rather than single steps, thereby yielding a well ordered sub file which quickens the sorting process. 23

24. Technique The general idea behind the method is to choose an increment h t , and divide the unordered list into sub lists of keys that are h t units apart. Then, each sub list is then sorted(using insertion sort) and gathered to form a list. This is known as pass. The pass is repeated for any sequence of increments {h t-1 , h t-2 ,… h 1 ,h } where h must be equal to 1. The increments are kept in the diminishing order and hence shell sort is also referred as diminishing increment sort. 24

25. Algorithm 25

26. Example 1 26

27. 27

28. Example 2 28

29. 29

30. Time Complexity The running time of the algorithm is dependant on the set of increment values. Since there is no best possible set of increments that has been formulated, the time complexity of shell sort is not completely resolved yet. On an average, it is faster than all O(n 2 ) sorting algorithms. 30

31. Dependency on the value of increments 31 General Term Time Complexity Ceil( ) O(N 2 ) 2 * Ceil ( ) + 1 O( ) O( ) O( ) O(N log 2 N ) O( ) General Term Time Complexity O(N 2 ) O(N log 2 N )

32. Stability The stability also depends on the choice of increments. 32

33. 33

34. 34

35. Applications of Insertion sort and Shell sort Practically used in applications where the no. of elements is small It is also used when the sequence is almost sorted. It can be used when not all the inputs are available initially. Consider an examination hall. The students are handing over the papers to the invigilator. The invigilator arranges (sorts) the papers using insertion sort. 35

36. Code: # include< stdio.h > int array[100],n; void get_size (); void get_array (); void shell_sort_ascending (); void shell_sort_descending (); void print_array (); int main() { get_size (); get_array (); shell_sort_ascending (); shell_sort_descending (); return 0; } 36

37. void shell_sort_ascending () { int i,h ; for(h=n/2;h>0;h/=2) {for( i = h;i < n;i ++) { int key,j ; key=array[ i ]; j= i ; while((j>=h) && (array[j-h]>key)) { array[j]=array[j-h]; j=j-h; array[j]=key ;}} printf ("\n\n The Sorting in Ascending order "); print_array ();} printf ("\n\n The sorted elements in ascending order "); print_array (); } 37

38. void shell_sort_descending () { int i,h ; for(h=n/2;h>0;h/=2) {for( i = h;i < n;i ++) { int key,j ; key=array[ i ]; j= i ; while((j>=h) && (array[j-h]<key)) {array[j ]=array[j-h]; j=j-h; array[j]=key ; }} printf ("\n\n The Sorting in Descending order "); print_array (); } printf ("\n\n The sorted elements in descending order "); print_array (); } 38

39. 39

40. References “Data Structures And Algorithms” by G A V Pai . “The Art of Computer Programming Vol.3” by Donald E.Kruth 40

41. Thank You!!! 41