Data structure Unit - II Searching and Sorting.pptx

Use the PPT for searching and sorting

1. Unit - II Searching and Sorting

2. Theory Learning Outcomes (TLO's)aligned to CO's TLO 2.1 Develop algorithm to search the given key using different Searching Techniques . TLO 2.2 Create algorithm to sort data using a given method . 2.1 Searching: Searching for an item in a data set using the following methods: ( i ) Linear Search (ii) Binary Search 2.2 Sorting: Sorting of data set in an order using the following methods: ( i ) Bubble Sort (ii)Selection Sort (iii) Insertion Sort (iv) Quick Sort (v) Merge Sort

3. Practical's Write a ‘C’ Program to Search a particular data from the given Array of numbers using: Linear Search Method * Write a ‘C’ Program to Search a particular data from the given Array of Stringsusing Linear Search Method * Write a ‘C’ program to Search a particular data from the given Array of numbersusing Binary Search Method. Write a ‘C’ Program to Search a particular data from the given Array of Stringsusing Binary Search Method. * Write a ‘C’ Program to Sort an Array of numbers using Bubble Sort Method. Write a ‘C’ Program to Sort an Array of Strings using Bubble Sort Method. * Write a ‘C’ Program to Sort an Array of numbers using Selection Sort Method. Write a ‘C’ Program to Sort an Array of Strings using Selection Sort Method. * Write a ‘C’ Program to Sort an Array of numbers using Insertion Sort Method. Write a ‘C’ Program to Sort an Array of Strings using Insertion Sort Method.

4. Searching Searching is an operation or a technique that helps finds the place of a given element or value in the list . Any search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not .  Some of the standard searching technique that is being followed in the data structure is listed below: Linear Search or Sequential Search Binary Search

5. Linear Search or Sequential Search This is the simplest method for searching. In this technique of searching, the element to be found is searched sequentially in the list . This method can be performed on a sorted or an unsorted list (usually arrays). In case of a sorted list searching starts from th  element and continues until the element is found from the list or the element whose value is greater than (assuming the list is sorted in ascending order), the value being searched is reached. As against this, searching in case of unsorted list also begins from the th  element and continues until the element or the end of the list is reached .

6. The list given below is the list of elements in an unsorted array . The array contains seven elements. Suppose the element to be searched is '46' , so 46 is compared with all the elements starting from the th  element, and the searching process ends where 46 is found, or the list ends. The performance of the linear search can be measured by counting the comparisons done to find out an element. The number of comparison is 0(n).

7. Algorithm Step 1: Read the search element from the user. Step 2: Compare, the search element with the first element in the list. Step 3: If both are matching, then display "Given element found!!!" and terminate the function. Step 4: If both are not matching, then compare search element with the next element in the list. Step 5: Repeat steps 3 and 4 until the search element is compared with the last element in the list. Step 6: If the last element in the list is also doesn't match, then display "Element not found!!!" and terminate the function.

8. OR Linear Search ( Array Arr , Value a ) // Arr is the name of the array, and a is the searched element. Step 1: Set i to 0 // i is the index of an array which starts from 0 Step 2: if i > n then go to step 7 // n is the number of elements in array Step 3: if Arr [ i ] = a then go to step 6 Step 4: Set i to i + 1 Step 5 : Go to step 2 Step 6: Print element a found at index i and go to step 8 Step 7: Print element not found Step 8: Exit

9. Binary Search Binary search is a very fast and efficient searching technique. It requires the list to be in sorted order . In this method, to search an element you can compare it with the present element at the center of the list . If it matches , then the search is successful otherwise the list is divided into two halves : one from the 0 th  element to the middle element which is the center element (first half) another from the center element to the last element (which is the 2 nd  half) where all values are greater than the center element. The searching mechanism proceeds from either of the two halves depending upon whether the target element is greater or smaller than the central element .

10. If the element is small er than the central element, then searching is done in the first half , otherwise searching is done in the second half . The process of comparing the required element with the center element and if not found then dividing the elements into two halves is repeated till the element is found or the division of half parts gives one element.

11. Algorithm Binary search is implemented using following steps... Step 1: Read the search element from the user Step 2: Find the middle element in the sorted list Step 3: Compare, the search element with the middle element in the sorted list. Step 4: If both are matching, then display "Given element found!!!" and terminate the function Step 5: If both are not matching, then check whether the search element is smaller or larger than middle element. Step 6: If the search element is smaller than middle element, then repeat steps 2, 3, 4 and 5 for the left sublist of the middle element. Step 7: If the search element is larger than middle element, then repeat steps 2, 3, 4 and 5 for the right sublist of the middle element. Step 8: Repeat the same process until we find the search element in the list or until sublist contains only one element. Step 9: If that element also doesn't match with the search element, then display "Element not found in the list!!!" and terminate the function.

12. Let's suppose we need to find the element 17 i.e. key=17 in the given array or list. We will work according to the above-given algorithm. 1. Set two pointers low and high at the lowest and the highest positions, respectively. 2. Find the middle element mid of the array ie . arr [(low + high)/2] = arr [(0+6)]/2] = arr [3] = 44

13. 3. If the element key == mid , return the index of mid. Otherwise, compare the element to be searched with mid. If key > mid , compare the key with the middle element of the elements on the right side of mid. This is done by setting low to low = mid+1. Otherwise, compare the key with the middle element of the elements on the left side of mid. This is done by setting high to high = mid-1.

14. 4. Repeat steps 2 to 3 until low meets high. 5. key = 17 is found