UNIT-1-DS-PPT.pptx

Unit-1 Searching and Sorting Introduction to Data Structures  Array/List Representation and its operations Searching Techniques:  Linear Search  Binary search Introduction to Sorting:  Insertion sort  Selection Sort  Bubble Sort Merge Sort  Quick sort Introduction...

Unit-1 Searching and Sorting Introduction to Data Structures  Array/List Representation and its operations Searching Techniques:  Linear Search  Binary search Introduction to Sorting:  Insertion sort  Selection Sort  Bubble Sort Merge Sort  Quick sort Introduction to Data Structures  Data can be represented in the form of binary digits in memory. A binary digit can be stored using the basic unit of data called bit. A bit can represent either a zero or a one.  Data means value or set of values or Data is a collection of raw facts.  Data structure is a way of storing and organizing data in an efficient manner.  Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked in appropriate ways both effectively and efficiently. The main objective of the data structure is to store and retrieve the data in effectively and efficiently. Mathematically, a data structure D is a triplet, that is, D=(d, f, a) where D= data structure d= a set of variables (data objects) f= a set of functions a= set of rules to implement the functions.  Classification of Data Structures Several data structures are available in the computer science and used based on their applications. Data structures are classified into different types. Types Linear Data Structures Non Linear Data Structures Graphs Arrays Linked list stack queues Trees  Linear Data Structures: A data structure is said to be linear if its elements form a sequence or a linear list. Non-linear Data Structures: A data structure is said to be non linear if its elements are not in a sequence. The elements in the data structure are not arranged in a linear manner; rather it has a branched structure.  Searching Linear Search: Linear search algorithm finds given element in a list of elements with an O(n) time complexity where n is total number of elements in the list. This search process starts comparing of search element with the first element in the list. If both are matching then results with element found otherwise search element is compared with next element in the list. If both are matched, then the result is "element found". Otherwise, repeat the same with the next element in the list until search element is compared with last element in the list, if that last element also doesn't match, then the result is "Element not found in the list".  Linear search is implementation 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.  Example: Consider the following list of element and search element.. Binary Search Binary SEARCH ALGORITHM Explanation Binary Search Algorithm searches an element by comparing it with the middle most element of the array.Then, following three cases are possible- Case-01: If the element being searched is found to be the middle most element, its index is returned. Case-02 If the element being searched is found to be greater than the middle most element,then its search is further continued in the right sub array of the middle most element. Case-03 If the element being searched is found to be smaller than the middle most element,then its search is further continued in the left sub array of the middle most element. Note: This iteration keeps on repeating on the sub arrays until the Binary SEARCH ALGORITHM Explanation Binary Search Algorithm searches an element by comparing it with the middle most element of the array. Then, following three cases are possible- Case-01: If the element being searched is found to be the middle most element, its index is returned. Case-02 If the element being searched is found to be greater than the middle most element, then its search is further continued in the right sub array of the middle most element. Case-03 If the element being searched is found to be smaller than the middle most element, then its search is further continued in the left sub array of the middle most element. Note: This iteration keeps on repeating on the sub arrays until the desired element is found or size of the sub array reduces to zero.  Sorting A sorting algorithm is used to arrange elements of an array/list in a specific order. For example, Here, we are sorting the array in ascending order. 26 There are various sorting algorithms that can be used to complete this operation. And, we can use any algorithm based on the requirement. 1. Insertion sort, 2. selection sort, 3. bubble sort, 4. merge sort, 5. quick sort 27  Insertion Sort Idea: like sorting a hand of playing cards Start with an empty left hand and the cards facing down on the table. Remove one card at a time from the table, and insert it into the correct position in the left hand compare it with each of the cards already in the hand, from right to left The cards held in the left hand are sorted these cards were originally the top cards of the pile on the table 28 playing cards To insert 12, we need to make room for it by 6 10 24 36 moving first 36 and then 24. 12 29 Insertion Sort 6 10 24 36 12 30  Insertion Sort 6 10 24 3 6 12 Try with an example: A [ ] = { 7, 31 Example1 32 Example2 33 Algorithm: 34  Bubble sort Bubble sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order. Idea: Repeatedly pass through the array Swaps adjacent elements that are out of order Note: Easier to implement, but slower than Insertion sort 35 Example1 36  Algorithm: try to understand the pseudo code with an example: A [ ] = { 7, 4, 37 5, 2} 38  Selection sort The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array. Idea: Find the smallest element in the array Exchange it with the element in the first position Find the second smallest element and exchange it with the element in the second position Continue until the array is sorted 39 Example1 40  Algorithm: try to understand the pseudo code with an example: A [ ] = { 7, 4, 41 5, 2} 42  Merge sort Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. Idea: Divide the unsorted list into N sublists, each containing 1 element. Take adjacent pairs of two singleton lists and merge them to form a list of 2 elements. N will now convert into N/2 lists of size 2. 43 44 45 Example1 46 Algorithm: 47  Algorithm: (Cont..) try to understand the pseudo code with an example: A [ ] = { 7, 4, 48 5, 2}  Quick sort Quick sort is based on the divide-and-conquer approach. Idea: choosing one element as a pivot element and partitioning the array around it such that: Left side of pivot contains all the elements that are less than the pivot element Right side contains all elements greater than the pivot 49 Implementation : Select the first element of array as the pivot element First, we will see how the partition of the array takes place around the pivot. 50 Example1 51 Example1 52 Algorithm: 53  Algorithm: (Cont..) try to understand the pseudo code with an example: A [ ] = { 7, 4, 54 5, 2}