BIT SINDRI

I N F O R M AT I O N AND TECHNOLOGY
THANK YOU SIR
 WELCOME

INFORMATION AND TECHNOLOGY, BIT SINDRI

DATA STRUCTURE AND ALGORITHMS
INDEX

Basic of data structure and algorithm

Sorting
Searching
Array
Notations
STUDENT INFO.

R O L L N O – 2 0 11 0 0 2 D
BRANCH - IT

Nikhil Singh
DATA
Data is basically some collected information.
Holds set of values of qualitative and quantitative
variables about one or more persons or object.
STRUCTURE
The way that the parts of something (data) are put
together or organized.
A website that has been built or made from a number
of parts
ALGORITHM
A finite set of rules or instructions that must be
followed when solving a specific problem or class
of problem.
STRUCTURE
The way that the parts of something (data) are put
together or organized.
A website that has been built or made from a number
or parts
DATA+STRUCTURE
* Data Structure can be defined as the group of data elements which
provides an efficient way of storing and organising data in the
computer so that it can be used efficiently.

* Some examples of Data Structures are arrays, Linked List, Stack,

Queue, etc.

* Data Structures are widely used in almost every aspect of Computer

Science i.e. Operating System, Compiler Design, Artificial
intelligence, Graphics and many more.
Data Structures are the main part of many computer
science algorithms as they enable the programmers to
handle the data in an efficient way. It plays a vital role in
enhancing the performance of a software or a program as
the main function of the software is to store and retrieve
the user's data as fast as possible
JUT
 JUT

APPLICATION FORM FOR NEW REGISTRATION

 JUT

ABC BRANCH
 GYANJYOTI PORTAL

STUDENT FILLING FORM

TIME- 06:00 AM- 11:00 AM

JUT
NOMS-

ACCORDING TO
NAME (A-Z)
 GYANJYOTI PORTAL
DATA BASE-

TIME- 06:00 AM- 11:00 AM

ROLL A ROLL P
ROLL B ROLL N

ROLL Z ROLL A
JUT
NOMS-

ACCORDING TO
NAME (A-Z)
 JUT
BEST PROGRAMER

BEST SORTING TCHNIQUE

ROLL A
ROLL B

ROLL Z
STUDENT INFO.

R O L L N O – 2 0 11 0 0 1 D
BRANCH - IT

Alka Kumari
SORTING

1. The process of arranging data in some logical order is known as

sorting .The order can be ascending or descending for numeric data
and alphabetically for character data.

2. In simple words, Sorting is one of the operations which we can

perform on data structure in order to arrange data elements in
ascending and descending order.
There are different methods that can be used to arrange data in
ascending or descending order, which are following:-

1. Bubble sort
2. Selection sort
3. Insertion sort
4. Merge sort
5. Quick sort
6. Counting sort
Bubble sort:-

Bubble sort is simple sorting

algorithm. A bubble sort is an
internal exchange sort. This
sorting technique is named bubble
because of the logic is similar to
the bubble in water when a bubble
is formed it is small at the bottom
and when it moves up it becomes
bigger and bigger.
The main key idea of bubble
sort is that to compare first
element of array to the
second element of the array.
If the first element is larger
and second element is a
smaller than swap the
element otherwise no
swapping is done.
In simple words bubble
sort starts by comparing
first element with second
element if first element
is greater than second
element then it will swap
both the elements and
move on to compare
second element with
third element and so on.
Selection sort :-

1. Selection sort perform in

place comparison which
means that the array is
divided into two parts, the
sorted part at the left end
and unsorted part at the right
end. Initially the sorted part
is empty and the unsorted
part is the entire list.
2. During iteration 1,
smallest element in
the array is selected
and that selected
element is replaced
with first position
element.
3. During iteration 2,
smallest element
from sub array is
selected and that
selected element is
replaced with 2nd
position element and
so on.
4. In simple word we can say
that the idea of the selection sort
is to search the smallest element
in the list and exchange it with
the element in the first position
then find the second smallest
element and exchange it with the
element in the second position
and so on until the entire array is
sorted.
STUDENT INFO.

R O L L N O – 2 0 11 0 0 5 D
BRANCH - IT

Vivekananda Bediya
Insertion sort :-

Insertion sort is different from

other sorting algorithms as sorting
starts from the index 1 .The
element at index 1 is compared
with element at index 0 if element
at index 1 is smaller than the
element at index 0 then we insert
the element at index 1 to index
0.2.
In second iteration element at
index 2 is compared with
element at. index 1 if element
at index 2 is smaller than
element at index 1 then we
again compare element at
index 2 with element at index
0 and insert element at index
2 to its proper position.
In other words during pass
1, the second element of
array is checked with
element before it and select
second element in proper
position during pass 2, the
third element of array is
compared to element before
it and insert third element at
proper position and so on.
 Insertion sort is just like a arranging a
picked card in Deck of card in our hands.
Merge sort :-

Merge sort is a sorting

technique based on divide and
conquer technique like as binary
search. Merge sort divide the
element into sub array until
there is one element in sub
array. At the end merging
process take place to combine
generate a sorted array.
 Merging means
combining two sorted list
into one sorted list. For
this the elements from
both the sorted list are
compared. The smaller
of both the element is
then stored in the third
array.
The sorting operation
is complete when all
the elements from
both the list are
placed in the third list.
The merge sort
algorithm requires
two sorted list.
Quick sort :-

Quick sort uses divide and

conquer approach to sort the
elements. A quick sort first
select a value which is called
the pivot value, the pivot value
can be e starting element, last
element or can be the middle
element. The role of the pivot
value is to assist with splitting
the list.
 2. As mentioned before that
there are many different ways to
choose the pivot value we will
simply use the first item in the
list .On the basis of a selected
element which is a pivot from
the list, it partitions the rest of the
list into two parts - a sub list that
contains element less than the
pivot and other sub list
containing element greater than
the pivot.
3. All element in the first sub-
list are arranged to be smaller
than the pivot, while all
elements in the second sub-list
are arranged to be larger than
the pivot. The same
partitioning and arranging
process is performed
repeatedly on the resulting
sub-list until the whole list of
items are sorted.
STUDENT INFO.

R O L L N O – 2 0 11 0 0 6 D
BRANCH - IT

Syed Saqlain Ahmad

Asymptotic Notation

The efficiency of an algorithm depends on the amount of time,

storage and other resources required to execute the algorithm.
And to represent the efficiency we use mathematical notation,
which are known as asymptotic notations. An algorithm may
not have the same performance for different types of inputs.
 So With the increase in the input size, the
performance will change. And The study of change in
performance of the algorithm with the change in the
order of the input size is known as asymptotic
analysis.
Asymptotic notations are the mathematical notations
used to describe the running time of an algorithm
when the input tends towards a particular value or a
limiting value.
• There are mainly three asymptotic notations:
• Big-O notation
• Omega notation
• Theta notation
• Big O notation specifically describes worst case scenario

• 2. Omega Notation (Ω) – Omega(Ω) notation specifically

describes best case scenario.

• 3. Theta Notation (θ) – This notation represents the average

complexity of an algorithm.
 Let know about the big O notation Big-O Notation (O-
notation)Big-O notation represents the upper bound of the
running time of an algorithm. Thus, it gives the worst-case
complexity of an algorithm. Since it gives the worst-case
running time of an algorithm, it is widely used to analyze an
algorithm as we are always interested in the worst-case
scenario
Lets take few examples to understand how we represent the time and
space complexity using Big O notation O(1)Big O of (1) represents
the complexity of an algorithm that always execute in same time or
space regardless of the input data.

O(n)Big O of (N) represents the complexity of an algorithm, whose

performance will grow linearly (in direct proportion) to the size of the
input data.

Big O of (n^2) represents the complexity of an algorithm, whose

performance is directly proportional to the square of the size of the
input data.
STUDENT INFO.

R O L L N O – 2 0 11 0 0 3 D
BRANCH - IT

Pintu Kumar Rana

ARRAY
An array is a collection of items stored at contiguous
memory locations. The idea is to store multiple items of the
same type together.

-Store the elements with the same data type

-Variable capable of storing multiple values of same data
type.
A character array in C/C++/Java
• char arr1[] = {'g', 'e', 'e', 'k', 's'};

An Integer array in C/C++/Java

• int arr[20] = {10, 20, 30, 40, 50…n};
• Types of Arrays

• The various types of arrays are as follows.

• One dimensional array
• Multi-dimensional array
• One-Dimensional Array
A one-dimensional array is also called a
single dimensional array where the
elements will be accessed in sequential
order. This type of array will be
accessed by the subscript of either a
column or row index.

• Multi-Dimensional Array
When the number of dimensions
specified is more than one, then it is
called as a multi-dimensional array.
Multidimensional arrays include 2D
arrays and 3D arrays.
int one_dim [10];    # declaration of 1D array
int two_dim [2][2];  #declaration of 2D array
int three_dim [2][3][4] = { { {3, 4, 2, 3}, {0, -3, 9, 11}, {23, 12, 23, 2} },
{ {13, 4, 56, 3},{5, 9, 3, 5}, {3, 1, 4, 9}
; #declaration of 3D array.
Here the elements are also defined.

return 0; }
 Array is something that is having a continuous memory
location which stores same type of data using some common
name or one variable capable of storing we can say that is
one variable that is capable of storing multiple values so
from the definition we can say this array is something that
can store multiple values of same type
STUDENT INFO.

R O L L N O – 2 0 11 0 0 4 D
BRANCH - IT

Riya Kumari Singh

SEARCHING
Searching is the process of finding some particular element in the list. If the
element is present in the list, then the process is called successful and the
process returns the location of that element, otherwise the search is called
unsuccessful.

There are two popular search methods that are widely used in order to search
some item into the list. However, choice of the algorithm depends upon the
arrangement of the list.
1.Linear Search
2.Binary Search
Linear Search-

Linear search is the simplest search algorithm and often called sequential search.
In this type of searching, we simply traverse the list completely and match each
element of the list with the item whose location is to be found. If the match found
then location of the item is returned otherwise the algorithm return NULL. Linear
search is mostly used to search an unordered list in which the items are not sorted.
Algorithm

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step8
Step 7: Print element not foundStep
8: Exit
Binary Search

Binary search is the search technique which works efficiently on the

sorted lists. Hence, in order to search an element into some list by
using binary search technique, we must ensure that the list is sort.
Binary search follows divide and conquer approach in which, the
list is divided into two halves and the item is compared with the
middle element of the list. If the match is found then, the location of
middle element is returned otherwise, we search into either of the
halves depending upon the result produced through the match.
Algorithm

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = - 1
Step 2: Repeat Steps 3 and 4 while BEG <=END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VALSET
END = MID – 1
ELSESET BEG = MID + 1
[END OF IF]
[END OF LOOP]
Step 5: IF POS = -1PRINT "VALUE IS NOT PRESENT IN THE ARRAY“
 BIT SINDRI
INFORMATION AND TECHNOLOGY

PRESENTED TO-

PROFESSOR
MR. SACHIN AGARWAL
THANK YOU SIR
 BIT SINDRI
INFORMATION AND TECHNOLOGY

P R E S E N T E D B Y-

2 0 11 0 0 1 D
2 0 11 0 0 3 D
2 0 11 0 0 4 D
2 0 11 0 0 5 D
2 0 11 0 0 6 D
2 0 11 0 0 2 D