Prepared By : Uday Shah (HOD-IT)
E-Mail : ruparleeducation@gmail.com
Contact No : 7600044051
Introduction
to Data Structure
Data Management Concept
· Data Structure Management
are method of representing a logical relationship between individual data
element a related to the solution of given problem.
· Data Structure Management
are the most convenient way to handle data of different types including
abstract data type.
· Data Structure Management
provide a meaningful way to manage a large amount of data efficiently such as
large data base and internet indexing services.
· Data Structure Management
is a structure set of variable associated with one another in a different ways.
· Data Structure Management
are the basic of programming tolls to define a large amount of data.
· Data Structure Management
should satisfactory represent the relationship between data element.
· Data Structure Management
should be easy show that programmer can easily process the data.
· Data Structure Management
can be classify in several ways it means it may be either linear or non-linear
· In a linear Data Structure
Management values are arrange in linear fashion for ex. Array, link list,
stack, queue etc are the example of linear Data Structure Management
· Which values are store in a
sequence. Non-linear is opposite to linear Data Structure Management.
· Data Structure Management
in this type of value are not arrange in ordered for ex. Tree, graph, table,
sets are example of non-linear Data Structure Management
· Following
is a diagram of Data Structure Management
According to above diagram we can clearly so that
array, link list, stack and queue are belongs to linear Data Structure
Management so it arrange data in sequence while tree, graph, table and sets are
belongs to non-linear Data Structure Management so it can be expand at any
level.
Data
Structure Management is a systematic way to organize data in order to use it
efficiently.
·
Interface − Each data structure
has an interface. Interface represents the set of operations that a data
structure supports. An interface only provides the list of supported
operations, type of parameters they can accept and return type of these
operations.
·
Implementation − Implementation
provides the internal representation of a data structure. Implementation also
provides the definition of the algorithms used in the operations of the data
structure.
Characteristics of a Data Structure
·
Correctness − Data structure implementation
should implement its interface correctly.
·
Time Complexity –
- Running
time or the execution time of operations of data structure must be as
small as possible. Time complexity defines how long the process
is running. It is possible to take very long times on large input or
until the program do not complete its task.
- Estimated time is a based on a user input functionality so we can
not considered the time of an algorithm for designing. The number of
instruction which program execute during its runtime call complexity.
·
Space Complexity –
- Memory
usage of a data structure operation should be as little as possible.
Space complexity depends on the amount of working storage.
- An algorithm need this means that how much memory space require
with a special functionality or for entire program and it is not able to
designing an algorithm. So it creates one another complexity call space
complexity.
Need for Data Structure
As
applications are getting complex and data rich, there are three common problems
that applications face now-a-days.
·
Data Search − Consider an
inventory of 1 million(106) items of a store. If the application is
to search an item, it has to search an item in 1 million(106) items
every time slowing down the search. As data grows, search will become slower.
·
Processor speed −
Processor speed although being very high, falls limited if the data grows to
billion records.
·
Multiple requests −
As thousands of users can search data simultaneously on a web server, even the
fast server fails while searching the data.
To solve
the above-mentioned problems, data structures come to rescue. Data can be
organized in a data structure in such a way that all items may not be required
to be searched, and the required data can be searched almost instantly.
Execution Time Cases
There are
three cases which are usually used to compare various data structure's
execution time in a relative manner.
·
Worst Case − This is the
scenario where a particular data structure operation takes maximum time it can
take. If an operation's worst case time is ƒ(n) then this operation will not
take more than ƒ(n) time where ƒ(n) represents function of n.
·
Average Case − This is the
scenario depicting the average execution time of an operation of a data
structure. If an operation takes ƒ(n) time in execution, then m operations will
take mƒ(n) time.
·
Best Case − This is the
scenario depicting the least possible execution time of an operation of a data
structure. If an operation takes ƒ(n) time in execution, then the actual
operation may take time as the random number which would be maximum as ƒ(n).
Basic Terminology
·
Data − Data are values or
set of values.
·
Data Item − Data item refers to
single unit of values.
·
Group Items − Data items that are
divided into sub items are called as Group Items.
·
Elementary Items −
Data items that cannot be divided are called as Elementary Items.
·
Attribute and Entity −
An entity is that which contains certain attributes or properties, which may be
assigned values.
·
Entity Set − Entities of similar
attributes form an entity set.
·
Field − Field is a single
elementary unit of information representing an attribute of an entity.
·
Record − Record is a
collection of field values of a given entity.
·
File − File is a
collection of records of the entities in a given entity set.
What are primitive and non-primitive data types?
o A data type is a classification
of data, which can store a specific type of information. Data types are
primarily used in computer programming, in which variables are created to store
data.
o Each
variable is assigned a data type that determines what type of data the variable
may contain.
o The term
"data type" and "primitive data type" are often used
interchangeably.
o Primitive data types are
predefined types of data, which are supported by the programming language. For
example, integer, character, and string are all primitive data types. Programmers
can use these data types when creating variables in their programs.
o For example,
a programmer may create a variable called "lastname" and define it as
a string data type. The variable will then store data as a string of
characters.
o Non-primitive data types are not
defined by the programming language, but are instead created by the programmer.
o They are
sometimes called "reference variables," or "object
references," since they reference a memory location, which stores the data. In
the Java programming
language, non-primitive data types are simply called "objects"
because they are created, rather than predefined. While an object may contain
any type of data, the information referenced by the object may still be stored
as a primitive data type.
Sorting
and Searching
Sorting refers to arranging data in a particular format. Sorting
algorithm specifies the way to arrange data in a particular order. Most common
orders are in numerical or lexicographical order.
The importance of sorting lies in the fact that data searching can
be optimized to a very high level, if data is stored in a sorted manner.
Sorting is also used to represent data in more readable formats. Following are
some of the examples of sorting in real-life scenarios −
·
Telephone Directory −
The telephone directory stores the telephone numbers of people sorted by their
names, so that the names can be searched easily.
·
Dictionary −
The dictionary stores words in an alphabetical order so that searching of any
word becomes easy.
Bubble Sort
This sorting method is Based on comparing and exchanging pairs of
adjacent elements, until elements in an area are sorted. One round of scanning
through the set of elements of any array called
a “Pass”.
The Bubble sort method derives its name from the fact that the smallest
data item “Bubble Up” to the top of an array of n elements. Assuming that the
array elements are arranged vertically. The algorithm begins by comparing the
bottom most elements with its adjacent Element and an exchange of the two
elements take place of bottom most element is smaller then the adjacent
element.
Bubble Sort Algorithm
1. Start
2. Bubble_sort(n, array)
n
is Number of Elements
array is List of array elements
3. initialize
i = 0
4. Repeat through step – 7 while ( i <
n)
5. j = 0
6. Repeat through step – 7 while (i <
n-1)
7. Check for Execution
if array[j] < array [j-1] then
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
8. j = j + 1
9. i = i + 1
10. Exit
Selection Sort
Selection sort is the easiest way to sort a table. Beginning with the
first record in the table, a search is performed to locate which has the
smallest key. When the element is found it is interchange with the first
record. The interchange place the record with the smallest key in the first
position of the table. A search for the second smallest is then carried out.
This is accomplished by examining the keys of the records form the second
element on word. The element which has second smallest key is interchange with
the element located in the second position of the table. The process of
searching for the record with the next smallest key and placing it in its
proper position continues until all records have been sorted.
Selection Sort Algorithm
1. Start
2. Selection_sort(n, array)
n
is Number of Elements
array is List of array elements
3. initialize
i = 0
4. Repeat through step – 7 while ( i <
n)
5. j = i + 1
6. Repeat through step – 7 while (i <
n-1)
7. Check for Execution
if array[i] < array [j] then
temp = array[i]
array[i] = array[j]
array[j] = temp
8. j = j + 1
9. i = i + 1
10. Exit
Merge Sort
The operation on sorting is closely related to the process of merging.
First examine the merging of two ordered tables which can be combined to
produce a single sorted element in table. This process can be accomplished
easily by successively selecting the records with the smallest key occurring
either of the table or placing this record in a new table there be creating
order list.
In
merge sort there are two different array in unsorted elements so first of all
arrange in orderly and then compare each elements in an ordered array and
transfer smallest element in third merge array in sorted order.
Merge Sort Algorithm
1.
Start
2.
Merge_sort(a, array1, b, array2, array3)
where
a Represent No. of
Element in First Array
array1
Represent the list of element in First Array
b
Represent No. of Element in Second Array
array2
Represent the list of element in Second Array
array3
Empty Array
3.
Initialize
i = 0, j = 0, k = 0
4.
Repeat Step 5 While (( i < a) and (j < b))
5.
if array1[i] < array2[j] then
Array3[k] = array1[i]
i = i + 1
k = k + 1
else if array1[i] > array2[j]
then
Array3[k] = array1[j]
j = j + 1
k = k + 1
else [ Elements of Both List are
equal and insert only
one
of them into Third Array]
Array3[k]
= array1[j]
i = i +
1
j = j + 1
k = k + 1
6.
Exit
Quick Sort
This method is used to perform sorting on larger table. The goal is to
place a particular record in it’s final position within the table. In so doing
all records which come first this record have smaller keys, while all records
that follow it have larger keys. This technique essentially partitions the
table into sub table. The same process can then be applied each of these sub
table and repeated until all the records are placed in their positions.
Quick Sort Algorithm
1.
Start
2.
Qick_sort(array,first,last)
Where
array Represent the list of an
Elements
first Represent the position of the first
element in the list
last Represent the position of the
last element in the list
3.
Initialize
low = first
high = last
mid = array[(low+high)/2]
4.
Repeat through step 10 while
(low <= high)
5.
Repeat Step – 6
while (array[low] < mid)
6.
low = low + 1
7.
while (array[high] > mid)
8.
high = high – 1
9.
if(low <= high)
temp = array[low]
array[low] = array[high]
array[high] = temp
low = low + 1
high = high – 1
10.
if(first < high)
Qick_sort(array,first,high)
11.
if(low < last)
Qick_sort(array,low,last)
12.
Exit
Searching Technique
·
Searching is a mechanism in
which the large amount of data are sorted in a local buffer as well as in
server database and user want to search individually then database allow to
satisfy the criteria or condition which individual record to retrieved from the
database.
·
So, the efficient storage of
the data facility provides fast searching algorithm technique.
·
Searching of the data is the
fundamental requirement of any computer application.
·
The main advantages of the
searching algorithms is to provide a good communication way by which user can
retrieve a single or group of records from thousand of records.
·
Data structure provide two
fundamental searching techniques.
o
Liner Search
o
Binary Search
Linear Search
·
This is a simplest and
easiest implementation of most frequently used searching algorithm.
·
The Linear search is also
most effective searching algorithm because in this technique it simply
traversal from top to bottom in an array and compare each element of an array
with their searching elements.
·
If searching element is
found in the list then it display appropriate message on the screen otherwise
it continues to find a searching element up to the end of the list.
·
In Linear search searching
algorithm has one flag type variable.
·
If searching element found
in the list then it change the value of flag type variable.
·
It will take more time in
compare to others searching algorithm.
·
It is only used in limited
amount of data because it require more consuming time
·
This is the simplest technique
to find out an element from an unsorted list. It simply traverse from top to
bottom in the array and find for the key target value from the list and display
output as well. It will also call as sequential searching method.
·
In this technique the value
of the key is compared with the first element of the list, if match is found
then the appropriate message is displayed and searching is done on remaining array elements.
linear Search
1.
Start
2.
Linear_Search(element, n, l)
Where element represents an Array List
n represents Number of Elements
l represents Last Elements of an Array
3.
Initialize:
k = 0
Flag = 1
4.
Repeat Step – 5 for k = 0, 1, 2 .. n -1
5.
if array[k] = element output: Element
Found
flag = 0
return
6.
if flag = 1 then output : Element Not Found
7. Exit
Binary Search
·
Binary search is also one of
the fundamental algorithms to provide efficient searching algorithm.
·
Sequential search use in a
small amount of data while binary search used in large amount of data because
it user divide and conquer method.
·
Binary search is widely use
searching algorithm for any application because within a sort amount of time it
produces thousands of output on a special keyword.
·
Binary search is a fastest
searching algorithm.
·
The main characteristics of
binary search are that work on sorted data list.
·
In a binary search there are
3 different values are use that is
·
Low Value
·
High Value
·
Mid Value
·
The Low value represent the
lower limit of an array which is always 0.
·
The High value represents
the Upper limit of an array which is always SIZE – 1.
·
The Mid value represents the
average value of High value and Low value.
·
According to Binary Search
algorithm searching element compare with mid
value.
·
If searching element is
higher then mid value then the searching element is down
side of mid value otherwise up side of
the mid value and this process is still continue up to the searching element is
not found.
·
This is an effective
searching algorithm because within a short period of time it displays the
position of searching element in the
list.
Binary Search
1.
Start
2.
Binary_Search(element, n, l)
Where element represents an Array List
n
represents Number of Elements
l represents Last Elements of an Array
3. Initialize: low = 0,high = n-1
4. Repeat through Step – 6 while (low <=
high)
5. mid = (low + high)/2
6. if
element < mid then high = mid – 1 else if element >
mid then low = mid + 1
else if element = mid then output: Element
Found
flag = 0
return
7.
if flag = 1 then
output : Element Not Found
8.
Exit
:: Best Of Luck ::
