Unit-2 Searching-Sorting-Linked Lists PDF

Unit -II Searching, Sorting & Dynamic Data Structures (Linked Lists) Outline Searching & Sorting Linked Lists – Basic Concepts Representation of Linked Lists in Memory Traversing, Searching, Insertions & Deletions on Linked Lists Memory Allocation...

Unit -II Searching, Sorting & Dynamic Data Structures (Linked Lists) Outline Searching & Sorting Linked Lists – Basic Concepts Representation of Linked Lists in Memory Traversing, Searching, Insertions & Deletions on Linked Lists Memory Allocation Garbage Collection Header Linked Lists Two-Way Lists Implementation of Linked List in C 8/25/2023 Dr. Jahangir Alam 2 Searching Searching in data structure refers to the process of finding the required information from a collection of items stored as elements in the computer memory. These sets of items are in different forms, such as an array, linked list, graph, or tree. Searching could be done by applying searching algorithms to check for or extract an element from any form of stored data structure. These algorithms are classified according to the type of search operation they perform, and therefore fall in following categories: 8/25/2023 Dr. Jahangir Alam 3   Sequential Search: In this type of searching, the list or array (data structure) is traversed sequentially and every element is checked. For example: Linear Search.  Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search. These methods are evaluated based on the time taken by an algorithm to search an element. 8/25/2023 Dr. Jahangir Alam 4  Searching Sequential Interval  Linear Search  Binary Search  Jump Search  Interpolation Search  Exponential Search  Sublist Search  Fibonacci Search  Ubiquitous Binary Search  More.. 8/25/2023 Dr. Jahangir Alam 5  Searching a given item in a given collection of data is possible in following three cases,  The best possible time (Best case timing complexity)  The average time (Average case timing complexity)  The worst-case time (Worst case timing complexity) The primary concerns are with worst-case times, which provide guaranteed predictions of the algorithm’s performance and are also easier to calculate than average times. 8/25/2023 Dr. Jahangir Alam 6 Linear Search It is the simplest search algorithm in data structure and iteratively searches all elements of the array. It has the best execution time of one and the worst execution time of n, where n is the total number of items in the input array. It checks each item in the array keep matching the searched item with every array element. If it finds the given item within the array, the location of item is noted and search is declared successful. Otherwise “Unsuccessful Search” is the result. 8/25/2023 Dr. Jahangir Alam 7  When the given data is unsorted, a linear search algorithm is preferred over other search algorithms. Following is a simple procedure for Linear Search: procedure linear_search (list, value) begin for each item in the list if match item == value then: return the item's location end if end for end procedure 8/25/2023 Dr. Jahangir Alam 8  Binary Search The binary search is a divide and conquer algorithm and locates specific item by comparing the middle item in the data collection (array or list). When a match is found, it returns the index of the item (location) and the search is successful. When the middle item is greater than the searched item, it looks for a central item of the left sub-array. If, on the other hand, the middle item is smaller than the searched item, it explores for the middle item in the right sub- array. It keeps looking for an item until it finds it or the size of the sub-arrays reaches zero in which case search is “Unsuccessful”. Binary search needs sorted order of items of the array. It works faster than a linear search algorithm. 8/25/2023 Dr. Jahangir Alam 9  Complexities in binary search are as follows: The worst-case complexity in binary search is O(log2n). The average case complexity in binary search is O(log2n). Best case complexity = O(1) Formal procedure for binary search algorithm is as follows: 8/25/2023 Dr. Jahangir Alam 10 Procedure binary_search begin A ← sorted array n ← size of array ITEM ← value to be searched LOC ← Location of ITEM Set beg= 1 Set end= n Set mid=INT((beg+end)/2) while beg