Searching and sorting techniques in data structures pdf

Introduction : Dynamic aspects of operations on data, Characteristics of data structures, Creation and manipulation of data structures, Operations on data structures, Types of data structures — linear and nonlinear. Introduction to algorithm: Asymptotic notations, Analysis of algorithms: Time and Space complexity.

Arrays and Linked Lists : Arrays: Dynamic memory allocation, one-dimensional arrays, multidimensional arrays, operations on arrays, storage — Row major order, Column major order. Linked lists: types of linked lists — singly, doubly and circularly linked lists, operations on linked lists.

Stacks and Queues : Stacks: Implementation of stacks— array and linked list, operations on stacks, Applications of Stacks, Notations — infix, prefix and postfix, Conversion and evaluation of arithmetic expressions using Stacks.

Queues: Implementation of queues— array and linked list, operations on queues, Types of queues — queue, double ended queue and priority queue. Union-find data structure and applications. Directed acyclic graphs; topological sort.

Algorithm design techniques: Divide and conquer, Greedy approach, dynamic programming. Data Structures are structures programmed to store ordered data so that various operations can be performed on it easily.

It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency.

Some of the data structures and algorithms interview questions are mentioned below. You can download the QnA in data structures and algorithms pdf form. It will help you to understand question paper pattern and type of data structures and algorithms questions and answers asked in B Tech, BCA, MCA, M Tech data structures and algorithms exam. Data Structure Lecture No. Doubly linked list. Related Books Free with a 30 day trial from Scribd. Uncommon Carriers John McPhee. The Art of War Sun Tsu.

Related Audiobooks Free with a 30 day trial from Scribd. Elizabeth Howell. Archana Baskar. So you do not need to waste the time on rewritings. Anurag Prasoon , human at skibud. Chinna Chinnu. Abhishek Rawat. Belal Noory , Student at University kabul. Show More. Views Total views. Actions Shares. No notes for slide. Searching and Sorting Techniques in Data Structure 1.

CO2 - Understand various searching and sorting algorithms and they will able to Choose the appropriate data structure and algorithm design method for a specified application. CO3 - Understand the abstract properties of various data structures such as stacks, queues.

Also they will able to choose appropriate data structure for specified application. CO4 - Understand the abstract properties of various data structures such as Lists. CO6 - Understand and apply fundamental algorithmic problems including Graph, Graph traversals and shortest paths Mr.

What is algorithm and Algorithm design? What is searching? Why do we need searching? That is, if the required element is found them the search is successful other wise it is unsuccessfully.

Hence constant time. Analysis of Linear Search How long will our search take? In the best case, the target value is in the first element of the array. So the search takes some tiny, and constant, amount of time. In the worst case, the target value is in the last element of the array.

So the search takes an amount of time proportional to the length of the array. Analysis of Linear Search In the average case, the target value is somewhere in the array. Questions such as these involve the computational complexity of the algorithm. An analysis of the time required to solve a problem of a particular size involves the time complexity of the algorithm.

An analysis of the computer memory required involves the space complexity of the algorithm. There are three types of time complexity — Best, average and worst case. In simple words for an algorithm, if we could perform and get what we want in just one eg. Below are some common time complexities with simple definitions.

Feel free to check out Wikipedia , though, for more in-depth definitions. Simple example with code -. So scenario on time complexity for this above given example would be -. The following 3 asymptotic notations are mostly used to represent time complexity of algorithms:. Big Omega is the opposite of Big Oh, if Big Oh was used to describe the upper bound worst-case of a asymptotic function, Big Omega is used to describe the lower bound of a asymptotic function.

In analysis algorithm, this notation is usually used to describe the complexity of an algorithm in the best-case, which means the algorithm will not be better than its best-case.

Space complexity deals with finding out how much extra space would be required by the algorithm with change in the input size. For e. I had written pseudocode and explanation in my personal notes images here. Search algorithms form an important part of many programs. Some searches involve looking for an entry in a database, such as looking up your record in the IRS database. Other search algorithms trawl through a virtual space, such as those hunting for the best chess moves.

Although programmers can choose from numerous search types, they select the algorithm that best matches the size and structure of the database to provide a user-friendly experience.

The general searching problem can be described as follows: Locate an element x in a list of distinct elements a1,a2, The solution to this search problem is the location of the term in the list that equals x and is 0 if x is not in the list.

The linear search algorithm looks at the first list item to see whether you are searching for it and, if so, you are finished. If not, it looks at the next item and on through each entry in the list. Linear search is the basic search algorithm used in data structures. It is also called as sequential search. Linear search is used to find a particular element in an array. It is not compulsory to arrange an array in any order Ascending or Descending as in the case of binary search.

Here is the pseudocode as divided into two images -. Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparison to Linear search.

The time complexity of above algorithm is O n. Simple code in python -. Binary Search is one of the most fundamental and useful algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.

Binary search is a popular algorithm for large databases with records ordered by numerical key. The algorithm starts at the middle of the database — if your target number is greater than the middle number, the search will continue with the upper half of the database. If your target number is smaller than the middle number, the search will continue with the lower half of the database. It keeps repeating this process, cutting the database in half each time until it finds the record.

This algorithm can be used when the list has terms occurring in order of increasing size. Binary Search is generally composed of 3 main sections:. In its simplest form, Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target or applies the search condition to the middle value of the collection; if the condition is unsatisfied or values unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.

If the search ends with an empty half, the condition cannot be fulfilled and target is not found. Given a sample array, first we find out midpoint and split it out.