PPT.pptx Searching and Sorting Techniques

PPT.pptx Searching and Sorting Techniques

1. Searching 1. Searching is the process to find the given element in the list with its position. 2. Searching technique should be able to locate the element to be searched as quickly as possible. 3. The search is said to be successful if the given element is found i.e. the element does exist in the collection such as an array; other wise it is unsuccessful .

2. Linear / Sequential Search 1. In Linear Search we start searching – sequentially starting from the first element and continue until we find the target [ element ] or we are sure that it is not in the list. 2. This approach gives us 2 possibility – i> either we find it ii> as we reach the end of the list end of the list

3. Algorithm Read the total number of array elements in ‘n’, Set flag = o. Read the ‘n’ array elements in array ‘a’ as – a [o] … a [ n]. Read the target to be searched in variable ‘Key’. For i = o to n. Compare each element of array with ‘Key’ => If (a [i] = = Key ) If true then set flag = 1, a nd close the loop.

4. 5. Now, if ( flag = = 1) means target found, so print the location at which target is found. 6. Stop Program:- # include < stdio.h > i nt main () { i nt a[20], n,i , Key , pos , flag = o; c lrser ();

5. p rintf (“\n Enter the number of elements in array : \n”); s canf (“% d”, &n); p rintf (“\n Enter Array element = “); For (i = o; i < n; i + +) s canf (“%d”, &a[i]); printf (“\n Enter the number to search “); s canf (“%d”, &Key);

6. For (i =o; i <n; i + +) { if (a[i] == Key) { pos = i‘; flag = 1; break ; } }

7. i f (flag == 1 ) printf (“\n Element located as %d “\n”, pos ); e lse [ printf “\n Element not present “); g etch (); } The complexity of any searching algorithm depends on number of comparisons required to find the element.

8. Performance of searching algorithm can be found by counting the number of comparisons in order to find the given element.

9. Advantages & disadvantages Simple and easy method. Efficient for only small lists. Better for unsorted data. Highly inefficient for large data. Suitable for storage structure, which do not support direct access to data. eg – magnetic tape. 6. Best case = 1 comparison Worst case = 1 n Average case = (n+1)/2

10. 7. Complexity = o (n)

11. Binary Search The linear search algorithm is very slow. If we have an array of 1000 elements, we must make 1000 comparisons in the worst case. If the array is not sorted, the linear search is the only solution. However, if the array is sorted, we can use a more efficient algorithm called the binary search. So for binary search, the array should be sorted before searching any target in it.

12. 2. In this, the Key element is compared with the middle element of the list. If they are equal, the search is successful. 3. If the middle element is greater than the Key, the search process is repeated with the lower half of the list; otherwise the process is repeated with the upper half of the list.

13. 4. Thus every time the comparison is made the number of elements yet to be searched are reduced by half. 5. The search is terminated when either the Key element is found or determine that it is not in the list. 6. The list is divided into two equal parts for searching the method is called the Binary search.

14. 7. The efficiency of the searching method can be improved by using the sorted list. This will reduce the searching time.

15. #include < stdio.h > i nt main() { i nt first, last, middle, array [20], i, n, search; printf (“\n Enter the number of elements in \ n”); scanf (“% d”, &n); printf (“\n Enter %d numbers :\n”, n ); For (i = o; i < n; i + +) scanf (“%d”, & array [i ]); printf (“ Enter the value to find \n” ); scanf (“%d”, &search );

16. f or =o; Last = n-1 Middle= (first + last ) \2; While = (first < = last ) { if (array [middle ] < search ) f irst = middle + 1 ; e lse if (array [middle]==search ) {

17. p rintf (“%d found at %d \n”, search, middle + 1); break; } e lse last = middle – 1; m iddle = (first + last )/2; }

18. if (first > last) printf (“ Not found ! %d is not present in the list \n “, search); g etch (); }

19. Advantages & Disadvantages Suitable for sorted data. Not suitable for unsorted data. Efficient for large list.

20. Sorting It refers to the operation of arranging data in the some given order. i.e either ascending order or descending order. When elements are to be arranged in ascending order, they are in increasing order i.e arr [1] < arr [2] < arr [3] <………> arr [N] And in descending order, they are in decreasing order. i.e arr [1] < arr [2] < arr [3] <………> arr [N]

21. e g – Suppose the list is as follows- 8,4,19,2,7,13,5,16 Ascending order = 2,4,5,7,8,13,16,19 Descending order = 19,16,13,8,7,5,4,2 Sorting is divided into 2 categories Internal sort External sort

22. In an internal sort, all the data are held in primary memory during sorting process. External sorting is carried on Secondary storage. External sort uses primary memory for the data currently being sorted and secondary storage for any data that does not fit in primary memory. For eg :- A file of 20,000 records may be sorted using an array that holds only 1000 records. During the sorting process, only 1000 records are therefore in memory of one time, the other 19,000 are kept in a file in secondary storage.

23. Sorting Techniques Bubble Sort In this sorting method, to arrange elements in ascending order. We begin with 0 th element is compared with the 1 st element. If it is found to be greater than 1 st element, then they are interchanged. Then the 1 st element is compared with the 2 nd element, if it is found to be greater, then they are interchanged.

24. 4. In the same way all the elements [excluding last] are compared with their next element and are interchanged if required. 5. On completing the 1 st iteration, the largest element gets placed at the last position. 6. Similarly, in the second iteration, second largest element gets placed at the second last position, and so on. 7. As a result, after all the iterations, the list become as a sorted list.

25. BUBBLE SORT ALGORITHM Read the total number of elements / numbers in a variable ‘n’. Enter that many numbers and store them in an array ‘a’. Take for loop of ‘I’ as - i = o to n 4. Take a for loop of ‘j’ in I’ s loop. ‘j’ = o to n- I

26. 5. Compare a[j] and a[j+1] 6. If a[j] > a[j+1] then interchange a [j] with a[j+1] 7. Close the for loop. 8. Print the array. 9. Exit.

27. PROGRAM v oid main () { int a [ 20 ] i nt n, i, j, temp printf (“\n Enter total no . o f elements” ); scanf (“% d”, &n); printf (“\n Enter the array elements:” ); for (i = o; i < n; i + +) scanf (“%d”, & a[i ]); for (i = o; i < n; i + +)

28. { for (j = o; j<n-I; j++) { if (a[j] > a [j +1]) { temp = a[ j ]; a [ j + 1] = temp; } } } p rintf (“\n\n Array after Sorting :\n”); f or (I = o; i<n; i++); p rintf (“%d”, a[i]); g etch (); }

29. ADVANTAGES AND DISADVANTAGE Simple and easy to implement. Slow process. Inefficient for large sorting list.

30. SELECTION SORT Selection sort is more efficient than bubble sort and insertion sort. Suppose ‘x’ is an array of size ‘n’ stored in memory. The selection sort algorithm first selects the smallest element in the array x and place it at array position o. Then it selects the next smallest element in the array x and place it at array position 1.

31. 5. It simply continues this procedure until it places the biggest element in the last position of the array.

32. SELECTION SORT ALGORITHM Read the total number of array element in variable ‘n’ Enter the array elements and store them in array ’a’. Take for loop for ‘I’ running from o to n-1. Assign ‘I’ to minimum (variable ‘min’) Take a for loop for ‘j’ running from i +1 to n.

33. 6. Check if a[j]< a[in] If true, then assign ‘j’ to min ; close j loop. 7. Now swap the two elements, so that we get smallest element on its right position. i.e temp = a [i] a [i] = a [min] a [min] = temp c lose ‘I’ loop

34. 8. Printf the sorted array. 9. stop.

35. PROGRAM void main() { int a [ 20 ] i, j, n, temp printf (“\n Enter total no . of elements” ); scanf (“% d”, &n); printf (“\n Enter the array elements:” ); for (i = o; i < n; i + +) scanf (“%d”, & a[i]); for (i = o ; i < n-1 ; i + + )

36. { min = i; for ( j= I +1; j <n; j + +) { if (a [j] < a[min] min = j ; } temp = a [i] a [i] = a [min] a [min] = temp }

37. Printf (“\n The sorted array is =“); For (I = o; I <n ; I + +) printf (“%d”, a [i]); Getch (); }

38. Complexity - Worst case Average case Best case 0(n 2 ) 0(n 2 ) 0(n 2 )

39. INSERTION SORT The insertion sort works just like its name suggests – it inserts each item into its proper place. In the first iteration, second element A[1] is compared with the first element A[o] in the second iteration, third element is compared with first and second element. In general, in every iteration, an element is compared with all the elements before it.

40. 4. During comparison if it is found that the element can be inserted at a suitable position, then space is created for it by shifting the other elements one position to the right and inserting the element at the suitable position. 5. This procedure is repeated for all the elements in the list

41. PROGRAM #include < conio.h > #include< stdio.h > v oid main () { int a[20], I, j, n, temp; c lrscr (); p rintf (“\ Enter total no. of elements in array “); s canf (“\%d”, &n)

42. p rintf (“\n The Array elements:”); for (i = o; i<n; i + + ) { temp = a [i]; j = i-1; while ( ( temp < a [j] ) & (j>=o) ) { a [j + 1 ] = a [j];

43. J = j-1; } a [j +1] = temp; } p rintf (“\n Array after Sorting”); f or (i = o; i < n; i + +) printf (“%d”, a[i]); g etch (); }

44. MERGE SORT Merge sort is a well-known example of divide and conquer method. Here, the elements are to be sorted in ascending order. Merging means combining two sorted lists into one sorted list. for this the element from both the sorted lists are compared the smaller of both the elements is then stored in the third array.

45. 4. The sorting is complete when all the elements from both the lists are placed in the third list.

46. RADIX SORT 1. Radix sort is also known as – digit, pocket and bucket sorting. 2. Radix sort puts the elements in order by comparing the digits of the numbers. 3. It is based on the values of the actual digits in the positional representation. 4. For example- the number 235 in decimal notation is written with – 2 in a hundreds position.

47. - 3 in a ten’s position. 5 in the units position. 5. In this, each pass through the list orders the data one digit at a time. 6. At the end of every pass, numbers in buckets are merged to produce a common list. 7. Number of passes depends on the range of numbers being sorted.

48. ALGORITHM FOR RADIX SORT Declare the radix function above main() with two parameter 1> array ‘a’ 2> no. of array elements ‘n’ 2. In the function main(), declare the required variables as a [15], n, i 3. Read the total number of elements in variable ’n’.

49. 4. Read the ‘n’ elements in array a[i]. 5. Call the radix function as - radix ( a, n); 6. Print the sorted array. 7. Close function main(). 8. Void radix ( int a[ ], int n) {

50. Declare its required variables as – Buckets [10] [10], count [10], passes, large, d iv, bucket no, i, j, k. 9. Now, find the largest number in a[ ]- l arge = a[o] // first element assigned to large f or (i = 1 to n) if a[i] > large assign a[i] to large.

51. 10. Find the number of digits in large and store the count in passes- passes = o while (large >o) { passes ++ large = large / 10 }

52. 11. Perform radix sort as- div = 1 f or (i =1 to passes) { first initialize buckets – for (j = o to 9) count [j] = o Insert elements in respective buckets – f or (j= o to n) {

53. bucket no = (a [j] / div) % 10; buckets [ bucket no ] [count [ bucket no ] ] = a[j] count [bucket no ] ++ }

54. 12. Merge elements of buckets and store them in a[o] … a[n-1] j=o for ( bucketno = o to 9) for ( K=o to count [ bucketno ]) a[j ++] = buckets [bucket no] [K]; div = div * 10

55. 13 . Close function radix.