Introduction to data structure

DATA STRUCTURE

1. Introduction to Data Structure Prof. sunil d. chute Dept. of computer science m.g. arts science and late n.p. commerce college armori

2. A data structure is a way of storing data in a computer so that it can be used efficiently and it will allow the most efficient algorithm to be used. The choice of the data structure begins from the choice of an abstract data type (ADT). A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structure introduction refers to a scheme for organizing data, or in other words it is an arrangement of data in computer's memory in such a way that it could make the data quickly available to the processor for required calculations. A data structure should be seen as a logical concept that must address two fundamental concerns. 1. First, how the data will be stored, and 2. Second, what operations will be performed on it

3. Fundamental of the Data Structure A data structure is a specialized format of data for arranging and storing data so that any user can easily access and worked within an appropriate data to run a program efficiently. Computer memory data can be organized logically or mathematically, and this process is known as a  data structure . In general, selecting a particular format of data depends on two factors. The data must be rich enough to satisfy the real relationships of the data in the real world. And on the other hand, the  data structure  should be so simple that one can easily process the data when it needs to be used.

4. Characteristics of data structures Following are the characteristics of the data structures as follows: Linear:  A linear describes data characteristics whether the data items are arranged in sequential form like an array. Non-Linear:  A Non-Linear data structure describes the characteristics of data items that are not in sequential form like a tree, graph. Static:  It is a static data structure that describes the size and structures of a collection of data items associated with a memory location at compile time that are fixed. Example - Array. Homogenous:  It is a characteristic of data structures representing whether the data type of all elements is the same. Example- Array. Non-Homogenous:  It is a characteristic of data structures representing whether the data type elements may or may not be the same.

5. Characteristics of data structures Dynamic:  It is a dynamic data structure that defines the shrinking and expanding of data items at the run time or the program's execution. It is also related to the utilization of memory location that can be changed at the program's run time. Example: Linked list. It has some rules that define how the data items are related to each other. It defines some rules to display the relationship between data items and how they interact with each other. It has some operations used to perform on data items like insertion, searching, deletion, etc. It helps in reducing the usage of memory resources. Time Complexity:  The execution time of a program in a data structure should be minimum as possible. Space Complexity:  The memory usage through all data items in a data structure should be less possible.

6. Basic Operations of Data Structures Traversing:  It is used to visit each variable once. It is also referred to as visiting elements in the data structure. Searching:  It is used to find the location of a given element in the whole data structure. Example, an array. Insertion:  It is used to insert an element at the specified position in data elements. Deletion:  A deletion operation is used to delete an element from the specified location. Sorting:  It is used to arrange or sort the data elements in ascending or descending order. However, the data items are arranged in some logical order, such as Name key, account number, etc. Merging:  The Merge operation is used to join two or more sorted data elements to a data structure.

7. SORTING METHODS BUBBLE SORT INSERTION SORT SELECTION SORT MERGE SORT

8. What is sorting? Sorting refers to the operation or technique of arranging and rearranging sets of data in some specific order. A collection of records called a list where every record has one or more fields. The fields which contain a unique value for each record is termed as the key field. For example, a phone number directory can be thought of as a list where each record has three fields - 'name' of the person, 'address' of that person, and their 'phone numbers'. Being unique phone number can work as a key to locate any record in the list. Sorting is the operation performed to arrange the records of a table or list in some order according to some specific ordering criterion. Sorting is performed according to some key value of each record. The records are either sorted either numerically or alphanumerically. The records are then arranged in ascending or descending order depending on the numerical value of the key. Here is an example, where the sorting of a lists of marks obtained by a student in any particular subject of a class

9. Categories of Sorting The techniques of sorting can be divided into two categories. These are: Internal Sorting External Sorting Internal Sorting : If all the data that is to be sorted can be adjusted at a time in the main memory, the internal sorting method is being performed. External Sorting : When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, then external sorting methods are performed.

10. complexity of sorting algorithm The complexity of sorting algorithm calculates the running time of a function in which 'n' number of items are to be sorted. The choice for which sorting method is suitable for a problem depends on several dependency configurations for different problems. The most noteworthy of these considerations are: The length of time spent by the programmer in programming a specific sorting program Amount of machine time necessary for running the program The amount of memory necessary for running the program

11. Efficiency of sorting Techniques To get the amount of time required to sort an array of 'n' elements by a particular method, the normal approach is to analyze the method to find the number of comparisons (or exchanges) required by it. Most of the sorting techniques are data sensitive, and so the metrics for them depends on the order in which they appear in an input array. Various sorting techniques are analyzed in various cases and named these cases as follows: Best case Worst case Average case Hence, the result of these cases is often a formula giving the average time required for a particular sort of size 'n.' Most of the sort methods have time requirements that range from O( nlog n) to O(n 2 ).