Selection sort and insertion sort

365 IT ELECTIVE-4 PROJECT

1. SELECTION SORT AND INSERTION SORT

2. SELECTION SORT › The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

3. COMPLEXITY Selecting the minimum requires scanning {\ displaystyle n}  elements (taking {\ displaystyle n-1}  comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining {\ displaystyle n-1}  elements and so on.

4. How Selection Sort Works? Consider the following depicted array as an example.

5. For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is stored presently, we search the whole list and find that 10 is the lowest value.

6. So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list, appears in the first position of the sorted list.

7. For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner.

8. We find that 14 is the second lowest value in the list and it should appear at the second place. We swap these values.

9. After two iterations, two least values are positioned at the beginning in a sorted manner . The same process is applied to the rest of the items in the array.

10. Following is a depiction of the entire sorting process − SORTED ARRAY

11. PROGRAM #include< iostream > u sing namespace std ; i nt main() { int elements, arr [10], input, j, temp; c out <<“How many elements?:”; cin >>elements; cout <<“Enter Array Elements:\n”;

12. for(input=0;input< elements;input ++) { for(j=input+1;j< elements;j ++) { if( arr [input]> arr [j]; { temp= arr [input] arr [input]= arr [j] arr [j]=temp; } } } Cout <<“\ nThe sorted array is:\n”; For(input=0;input< elements;input ++) { cout << arr [input]<<“ “; } Cout <<“\n”; }

13. OUTPUT

14. OUTPUT

15. OUTPUT

16. INSERTION SORT It is a simple Sorting algorithm which sorts the array by shifting elements one by one. In 2006 Bender,  Martin Farach -Colton , and Mosteiro published a new variant of insertion sort called library sort or  gapped insertion sort  that leaves a small number of unused spaces (i.e., "gaps") spread throughout the array.

17. The benefit is that insertions need only shift elements over until a gap is reached. The authors show that this sorting algorithm runs with high probability in O( n  log  n ) time.

18. ADVANATAGES OF INSERTION SORT Simple implementation:  Jon Bentley  shows a three-line  C  version, and a five-line optimized  version Efficient for (quite) small data sets, much like other quadratic sorting algorithms More efficient in practice than most other simple quadratic (i.e.,  O ( n 2 )) algorithms such as  selection sort  or bubble sort.

19. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is  O ( nk ) when each element in the input is no more than  k  places away from its sorted position Stable; i.e., does not change the relative order of elements with equal keys In-place; i.e., only requires a constant amount O(1) of additional memory space Online; i.e., can sort a list as it receives it

20. CHARACTERISTICS OF INSERTION SORT It has one of the simplest implementation It is efficient for smaller data sets, but very inefficient for larger lists. Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency .

21. It is better than Selection Sort and Bubble Sort algorithms. Its space complexity is less. Like Bubble Sorting, insertion sort also requires a single additional memory space. It is a  Stable  sorting, as it does not change the relative order of elements with equal keys.

22. How Insertion Sorting Works

23. Consider the following depicted array as an example.

24. Insertion sort compares the first two elements . It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.

25. Insertion sort moves ahead and compares 33 with 27 . And finds that 33 is not in the correct position . It swaps 33 with 27

26. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping .

27. Next , it compares 33 with 10 . These values are not in a sorted order.

28. So we swap them . However, swapping makes 27 and 10 unsorted. Hence, we swap them too.

29. Again we find 14 and 10 in an unsorted order . We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items. This process goes on until all the unsorted values are covered in a sorted sub-list.

30. SIMPLE STEPS OF INSERTION Step 1 − If it is the first element, it is already sorted. return 1 ; Step 2 − Pick next element Step 3 − Compare with all elements in the sorted sub-list Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step 5 − Insert the value Step 6 − Repeat until list is sorted

31. { 3, 7, 4, 9, 5, 2, 6, 1 } 3  7 4 9 5 2 6 1 3   7  4 9 5 2 6 1 3   7   4  9 5 2 6 1 3   4  7  9  5 2 6 1 3 4 7  9   5  2 6 1 3 4  5  7 9  2  6 1 2  3 4 5 7 9  6  1 2 3 4 5  6  7 9  1 1  2 3 4 5 6 7 9

32. PROGRAM #include< iostream > Using namespace std ; Int main() { int i,j,n,temp,a [30]; cout << “Enter the number of elements:” cin >>n; cout <<“\Enter the element\n”; for( i -=1;i< n;i ++) { cin >>a[ i ]; }

33. for( i =1;i<=n-1;i++) { temp=a[ i ]; j=i-1; while((temp<a[j])&&(j>=0)) { a[j+1]=a[j]; //moves element forward j=j-1; } a[j+1]=temp; //insert element forward } Cout << “\ nThe sorted array is:”; For( i =0;i< n;i ++) { cout << a[ i ]<<“ “; } Return 0; }

34. OUTPUT

35. OUTPUT

36. OUTPUT