UNIT I- Sesgfnbghnghnghmghmhgmhmhsion 4.pptx

BBFGBFGNFGNc45yc65ccjj ghjeyj 56j 65 j6 j67jytjh6j6GFNBG

1. UNIT I INTRODUCTION TO DATA STRUCTURES

2. Syllabus Introduction – Basic terminology – Data structures – Data structure operations - ADT – Algorithms: Complexity, Time – Space trade off - Mathematical notations and functions - Asymptotic notations – Linear and Binary search - Bubble sort - Insertion sort

3. https://www.cs.usfca.edu/~galles/visualization/Search.html (Final) for linear search and binary search https://blog.penjee.com/binary-vs-linear-search-animated-gifs/ (for linear search and binary search comparisons) https://www.cs.usfca.edu/~galles/visualization/Algorithms.html http://www.cs.armstrong.edu/liang/animation/web/BubbleSort.html (Bubble Sort) http://www.ee.ryerson.ca/~courses/coe428/sorting/bubblesort.html ( bUBBLE SORT) https://courses.cs.vt.edu/csonline/Algorithms/Lessons/InsertionCardSort/insertioncardsort.swf (Insertion sort final) http://www.ee.ryerson.ca/~courses/coe428/sorting/insertionsort.html (INSERTION SORT ADDITIONAL)

4. SORTING: BUBBLE SORT Let A be a list of n numbers. Sorting A refers to the operation og rearranging the elements of A so that they are in increasing order: A[1]<A[2]<A[3]<………….A[N]

5. Bubble Sort Algorithm for( i =0; i <n; i ++) { for(j=0; j<n-i-1; j++) { if( a[j] > a[j+1]) temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } }

6. Bubble Sort Example

7. Time Comlexity Total number of comparison required to sort the array: =(N-1)+(N-2)+(N-3)+…2+1 =(N*(N-1))/2 So worst case complexity is O(N 2) HIGHEST ORDER IS N 2

8. Complexities

9. CONT.. Best Case Time Complexity:O (N) The best case occurs when the array is already sorted. Number f comparison required: N-1 Number of swap=0

10. Insertion Sort Insertion sort  is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is considered an ”  in-place  ” sorting algorithm, meaning it doesn’t require any additional memory space beyond the original array.

11. Insertion Algorithm Steps S tart with the second element of the array as the first element in the array is assumed to be sorted. Compare the second element with the first element, check if the second element is smaller, and swap them. Move to the third element and compare it with the second element, then the first element and swap as necessary to put it in the correct position among the first three elements. Continue this process, comparing each element with the ones before it and swapping as needed to place it in the correct position among the sorted elements. Repeat until the entire array is sorted.

12. Insertion Sort algorithm Sort(int a[],int n) { int i , j, key; for( i =1; i <n; i ++) { key = a[ i ]; j = i-1; while(j>=0 && key < a[j]) { a[j+1] = a[j]; j--; } a[j+1] = key; } }

13. Insertion Sort Example

14. Complexities

15. Complexities

16. Lets Practice

17. Sort this using Bubble Sort  8 12 5 4 6 9 3                                                        

18. Sort this using Bubble Sort  8 12 5 4 6 9 3  8 5 4 6 9 3 12 5 4 6 8 3 9 12 4  5 6 3 8 9 12  4 5 3 6 8 9 12

19. Sort this using Bubble Sort  4 3 5 6 8 9 12 3  4 5 6 8 9 12 3  4 5 6 8 9 12

20. Sort this using Insertion Sort  8 12 5 4 6 9 3                                                        

21. Sort this using Insertion Sort  8 12 5 4 6 9 3  8 12 5 4 6 9 3  8 12 5 4 6 9 3  8   12 4 6 9 3    8 12 4 6 9 3

22. Sort this using Insertion Sort  5  8 12 4 6 9 3  4 5 8 12 6 9 3  4 5 6 8 12 9 3 4  5 6 8 9 12 3  3 4 5 6 8 9 12

23. Work for you…. You have been given a pack of cards (Only Spades) numbered 1 to 13 (Ace, 2 to 10, Jack Queen, King) in random order. Write a program to sort these cards. Use Bubble sort and print each line of output after every iteration. For the same above problem, Write the program using Insertion sort and print each line of output after every iteration. Compare the number of steps for each sorting technique