Unit-V.pdf

UNIT-V : SEARCHING AND SORTING Searching It is the process of finding the specific data item or record in the list. If the item exist in the given list then the search is said to be successful and if the element is not found in the given list then the search is said to be unsucce...

UNIT-V : SEARCHING AND SORTING Searching It is the process of finding the specific data item or record in the list. If the item exist in the given list then the search is said to be successful and if the element is not found in the given list then the search is said to be unsuccessful. Basically, searching can be categorized as external and internal searching. External searching means searching the records stored on the disk whereas internal searching refers to searching the records stored within the computer’s main memory. There are many searching algorithms based on the way of arranging the data elements. They are linear or sequential search, binary search and interpolation search. The complexity of searching algorithm is measured in terms of number of comparisons required to find key element in the data/array. Linear/ sequential search  It is the simplest searching method.  It does not expect the list to be sorted.  The Key which to be searched is compared with each element of the list one by one.  If a match exists, the search is terminated.  If the end of the list is reached, it means that the search has failed and the Key has no matching element in the list.  Ex.: consider the Array A : 23 15 18 17 42 96 103. Now let us search for 17 by Linear search. The searching starts from the first position. Since A ≠17. The search proceeds to the next position i.e; second position A ≠17. The above process continuous until the search element is found such as A=17. Here the searching element is found in the position 4.  Advantages: o It is simplest known technique. o The elements in the list can be in any order.  Disadvantage: o It is very slow process. o It is used only for small amount of data. o It is very time consuming process.  Algorithm: 1 MRUNALI VAIDYA 4   Complexity: The worst and average case complexity of Linear search is O(n), where ‘n’ is the total number of elements present in the list. Binary search  Binary search is used when the array is sorted in ascending/descending order.  It is extremely efficient algorithm.  In binary search, first the key element (to be searched) is compared with item in the middle position of the array. If there is a match, we can return immediately.  If the key is less than middle element, then the item is searched in the lower half of the array otherwise upper half of the array is searched.  Advantages: When the number of elements in the list is large, Binary Search executed faster than linear search. Hence this method is efficient when number of elements is large.  Disadvantages: To implement Binary Search method the elements in the list must be in sorted order, otherwise it fails.  Algorithm:  Complexity: In each comparison the size of the search area is reduced to half. So, the worst case time complexity is O(log2n+1).  Ex. 1 MRUNALI VAIDYA 5 Sorting Arranging the elements in the list in some specific (ascending/descending) order is called as sorting. The main properties of sorting techniques are -  Stable: If the sorting algorithm preserves the relative order of any two equal elements, then the sorting algorithm is stable.  In place: If an algorithm does not require an extra memory space except for few memory units, then algorithm is said to be in place. There are two basic categories of sorting methods  Internal sorting: sorting data items in main memory.  External sorting: sorting large data. Some may be present in main memory and some kept in auxiliary memory. Difference between internal and external sort Insertion sort  It is a simple sorting algorithm that works by building a sorted array one element at a time.  It is considered an” in-place” sorting algorithm, meaning it doesn’t require any additional memory space beyond the original array.  Following are the steps to use insertion sort 1 MRUNALI VAIDYA 6   We start with second element of the array as first element in the array is assumed to be sorted.  Compare second element with the first element and check if the second element is smaller then 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.  Working of the insertion sort – consider an array { 23,110,5,2}  Algorithm 1 MRUNALI VAIDYA 7   Complexity: O(n2 ).  Advantages o It is simple sorting algorithm, in which the elements are sorted by considering one item at a time. The implementation is simple. o It is efficient for smaller data set and for data set that has been substantially sorted before. o It does not change the relative order of elements with equal keys o It reduces unnecessary travels through the array o It requires constant amount of extra memory space.  Disadvantages o It is less efficient on list containing more number of elements. o As the number of elements increases the performance of program would be slow Selection sort  The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted part. This process is repeated for the remaining unsorted portion until the entire list is sorted.  Example: Consider the following array with 6 elements. Sort the elements of the array by using selection sort. A = {10, 2, 3, 90, 43, 56}.  Algorithm 1 MRUNALI VAIDYA 8   Complexity: O(n2)  Advantage o Simple and easy to understand. o Works well with small datasets.  Disadvantage  Selection sort has a time complexity of O(n^2) in the worst and average case.  Does not work well on large datasets.  Does not preserve the relative order of items with equal keys which means it is not stable. Radix sort  Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys.  Rather than comparing elements directly, Radix Sort distributes the elements into buckets based on each digit’s value.  By repeatedly sorting the elements by their significant digits, from the least significant to the most significant, Radix Sort achieves the final sorted order.  Algorithm 1 MRUNALI VAIDYA 9   Complexity: O(n)  Example Skip list  A skip list is a probabilistic data structure. The skip list is used to store a sorted list of elements or data with a linked list.  It allows the process of the elements or data to view efficiently.  In one single step, it skips several elements of the entire list, which is why it is known as a skip list.  It is built in two layers: The lowest layer and Top layer.  The lowest layer of the skip list is a common sorted linked list, and the top layers of the skip list are like an "express line" where the elements are skipped. 2 MRUNALI VAIDYA 0   Advantages o The skip list is solid and trustworthy. o To add a new node to it, it will be inserted extremely quickly. o Easy to implement compared to the hash table and binary search tree o The number of nodes in the skip list increases, and the possibility of the worst-case decreases o Finding a node in the list is relatively straightforward.  Disadvantages o It needs a greater amount of memory than the balanced tree. o Reverse search is not permitted. o Searching is slower than a linked list Questions 1. Explain the difference between linear and binary search 2. Difference between external and internal sort 3. What is selection sort? Sort the following items using selection sort. State its complexity. 5 80 45 63 15 84 7 52 4. What do you mean by sorting? List different types of sorting techniques. 5. Sort following using selection, insertion sort 25 30 59 10 92 85 30 6. Short note on skip list. 2 MRUNALI VAIDYA 1