Data Structure Sweta Bohra

Data Structure
Data and Data Item: Raw facts are called as data & those raw facts which are the
part of our information is called as meaningful data.
Data Items are classified as -
1. Elementary Items.
2. Group Items.
Those data items that are not divided into sub items are called Elementary items.
And those data items that are divided into sub items are called Group items.

Collections of data are frequently organized into a hierarchy of fields, records and
files. Therefore representation of single unit of value on certain type is termed as
data items.

Data Structure: - Techniques and methods are used to represent the data in
computer memory along with some operations to perform on it is termed as Data
Structure.

Algorithm: - Step by Step solution of a given problem is called as Algorithm.

Flowchart:- Graphical representation of solution of given problem is termed as

flowchart.

Classification of Data Structure

Data Structure may be classified as –
1. Linear.
2. Non-Linear.

Data structure is said to be linear if it’s elements forms a sequence.

Data structure is said to be non-linear if it’s elements doesn’t form a sequence.

Operations on Data structure

The data appearing in our data structure are processed by means of certain
operations. There are four major operations applied by all data structure.
1. Traversing: - Accessing each record once so that all items in the record may
be processed.
2. Searching: - Finding the location of the record with a given key value.
3. Inserting: - Adding a new record to the structure.
4. Deleting: - Deleting means removable of a data element from a data structure.
Data structure is first removed and then it can be eliminated.

Other operations
1. Sorting: - Sorting means arranging of an data elements of a data structure in
a specified order {Ascending and Descending}.
2. Merging: - Merging means combining the two similar data structure to make
new data structure of a same time.

1
 Data Structure Sweta Bohra

Primitive and non-primitive data type

A data can be either primitive or non-primitive.
1. Primitive data type: - Primitive Data types are those which are not composed
of other data type. Some languages have their fundamental data type like int,
float, char are considered as primitive data type.
2. Non-primitive data type: - Non-primitive data types are those which are
composed of primitive data type, normally these data items are defined by the
some type are referred as user – defined data type.
Examples of non – primitive data type are Array, Stack, Queue, linked list, etc.

After these illustrations we can further divide non-primitive data type in 2 categories
1. Simple data structure: - Simple data structure is normally built from
primitive data type by int, char, float.
Following data structure can be formed as simple data structure.
1. Array.
2. Structure.
2. Compound data structure: - Simple data structure can be combined in
various ways to form a complex structure are called compound data structure.

Compound data structures are

1. Linear.
2. Non-linear.
1. Linear: - Those data structure that are single level said to be linear or single
level data structure.
Example: - stack, queue, linked list.

2. Non-linear: - Those data structure which are multi level like tree, graph and
forest are termed as non-linear data structure.

Data Structure

Primitive Non-Primitive
(int, float, char)

Simple Compound
[Array, Structure]

Linear Non-Linear
[Stack, Queue, Linked List] [Tree, Graph,
Forest]

2
Data Structure Sweta Bohra

Algorithms, are used to manipulate the data contained in these data structures as
in searching and sorting. The formal representation of this model as a sequence of
instructions is called an algorithm, and coded algorithm, in a specific computer
language is called a program.

Complexity theory in computer science is a part of theory of computation dealing

with the resources required during computation to solve a given problem. The most
common resources are time (how many steps (time) does it take to solve a problem)
and space (how much memory does it take to solve a problem). It may be noted that
complexity theory differs from computability theory, which deals with whether a
problem can be solved or not through algorithms, regardless of the resources
required.

3
Data Structure Sweta Bohra

It is about structuring and organizing data as a fundamental aspect of developing a

computer application. A program usually contains different types of data types
(integer, float, character etc.) and need to store the values being used in the
program. Every language has sets of data type.

Characteristics of Algorithm
It should contain finite number of steps and for execution contain finite time.
It should contain unambiguous symbol.

Analysis of algorithms has been an area of research in computer science; evolution

of very high speed computers has not diluted the need for the design of time-efficient
algorithms.

4
Data Structure Sweta Bohra

Analy
sis
Priory Posteri
Calculate on the base of or on a particular
Dependent
Iteration Hardware
• Gives Approx. Value • Gives Exact Value
• (Independent) • (Dependency)
• Uniformity • Value is not uniform

Asymptotic Notation
It’s a mathematical way to represent time complexity.

1. Big - Oh (O)
c=
constant
value
n = input
value
t = time

5
Data Structure Sweta Bohra

t c.g(n) Graph Convention

f(n) = O g(n)
f(n) <= c.g(n)
where c > 0
k n>k
• Worst Case k >=0
• Upper Bound (At
most)

6
Data Structure Sweta Bohra

2. Big - Omega
c=
constant
value
n = input
value
t = time
t Graph Convention
f(n)f(n) = g(n)
f(n) >= c.g(n)
where c > 0
c.g(n) n > k
k >=0
k

• Best Case
• Lower Bound (At
least)

3. Theta

7
Data Structure Sweta Bohra

c=
constant
value
n = input
value
t = time
t Graph Convention
f(n) C1.g(n) <=f(n) <= c2.g(n)

c.g(
n)
k
• Best
Case
• Lower
Bound
(At least)

8
Data Structure Sweta Bohra

Array: - We used variables to store only a single piece of data. But sometimes, you
want to refer to a whole bunch of data all at once. For that, you need a new type of
variable: the array. An array is a “collection variable” or data structure. It is a linear
structure where all the elements [Data Items] form a sequence.
When elements are Linear Structure & are represented by means of contiguous
[sequence] memory location then this Linear Structure are called Array.

Array is one of the simplest Data Structure and is very easy to sort, search & traverse.
Array stores a list of finite numbers of homogeneous statements, i.e., Data Elements
of same type.

Instead of declaring individual variables, such as number0, number1, ..., and

number99, you declare one array variable such as numbers and use numbers[0],
numbers[1], and ..., numbers[99] to represent individual variables. A specific
element in an array is accessed by an index.

All arrays consist of contiguous memory locations.

The lowest address corresponds to the first element.
The highest address to the last element.

Types of Array
1. One dimensional array [1-d]
2. Multidimensional array [n-d]

1 2 3 4 5 6 7 8
1 n

Here, n is length of array (total number of data can be stored in array) and it can be
found by index (Lower bound and Upper bound).
Lower bound (LB); smallest index i.e. 1
Upper bound (UB); largest index i.e. 8

Length = (UB – LB) +1

Length = (8 – 1) +1
Length = (7) +1
Length = 8

9
Data Structure Sweta Bohra

1-D Array, 2D Array, 3D Array

Way of representing linear structures in memory (1-d):

Relationship of elements represented by means of sequential memory
locations. (Array)

3rd Element; num[2] 5th Element; num[4]

2 4 64 4 33

1st Element; num[0] 2nd Element; num[1] 4th Element; num[3]

Here ‘num’ is the name of the array, size is 5 and it is of int type. The array subscript
always starts from zero.
Subscript notation
num[6] or
Bracket notation

Subscript
or
Index

Way of representing linear structures in memory (n-d):

Let take example of 2d array of m rows and n columns. It will be represented in
memory by a block of m.n sequential memory locations.

10
Data Structure Sweta Bohra

In computing, row-major order and column-major order describe methods for storing
multidimensional arrays in linear memory.
It can be store by programming language in two different ways
Column by Column (Column-major order)
Row by Row(Row major order)

Column by Column (Column-major order)

Column-major order is a similar method of flattening arrays onto linear memory, but
the columns are listed in sequence.

(1,1) (1,2) (1,3) (1,4)

(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)

(1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,3) (3,3) (1,4) (2,4) (3,4)

Row by Row (Row major order)

In row-major storage, a multidimensional array in linear memory is organized such
that rows are stored one after the other.

(1,1) (1,2) (1,3) (1,4)

(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)

(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)

Computer does not keep track of address of each element of array; rather it will store
address of first element i.e. base address,
Base(LA)

Base Address of First Element

Linear Array

LOC (LA[K])

Location
Element of Array

11
Element of Array
Data Structure Sweta Bohra

Now if we want to calculate address of any other element of LA.

Value 58 312 37 988

Address 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Index 7 8 9 10

Address of first Word length number Index of which we

element of array of bytes used to store want address i.e. 9
i.e. 2 one value i.e. 4

LOC(LA[K]) = Base(LA) + w(K-lowerbound)

LOC(LA[9]) = Base(LA) + w(K-lowerbound)
LOC(LA[9]) = 2 + 4 (9-7)
LOC(LA[9]) = 2 + 4 (2)
LOC(LA[9]) = 10

It means address (memory location) of 9th index element is 10. Using this formula
we can access any of the data element of array, no need to traverse each element
one by one

Computation of Address in Column by Column (Column-major order)

(1,1) (1,2) (1,3) (1,4)

(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)
500 504 508 512 516 520 524 528 532 536 540 544
4 4 4 4 4 4 4 4 4 4 4 4
byte byte byte byte byte byte byte byte byte byte byte byte
(1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,1) (3,3) (1,4) (2,4) (3,4)

LOC(LA[J,K]) = Base(LA) + w[M(K-1)+(J-1)]

Here, M is no. of row
LOC(LA[1,3]) = 500+ 4[3((3-1)+(1-1))]
LOC(LA[1,3]) = 500+ 4[3(2+0)]
LOC(LA[1,3]) = 500+ 4[6]
LOC(LA[1,3]) = 500+ 24
LOC(LA[1,3]) = 524

12
 Data Structure Sweta Bohra

Computation of Address in Row by Row (Row-major order)

(1,1) (1,2) (1,3) (1,4)

(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)
500 504 508 512 516 520 524 528 532 536 540 544
4 4 4 4 4 4 4 4 4 4 4 4
byte byte byte byte byte byte byte byte byte byte byte byte
(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)

LOC(LA[J,K]) = Base(LA) + w[N(J-1)+(K-1)]

Here, N is no. of column
LOC(LA[2,3]) = 500 + 4[4(2-1)+(3-1)]
LOC(LA[2,3]) = 500 + 4[4(1)+2]
LOC(LA[2,3]) = 500 + 4[6]
LOC(LA[2,3]) = 500 + 24
LOC(LA[2,3]) = 524

Types of Operations normally perform on any linear structure.

Traversal; Process each element.
Search; Find the location of element. Every languages has
Insertion; Add new element in the list. its own way to
Deletion; Remove element from list. represent array
Sorting; Arrange elements in order.
Merging; Combine elements

13
Data Structure Sweta Bohra

Traversal; Process each element

Let ‘LA’ be a collection of data elements stored in the memory of the computer.
Suppose we want to count the number of elements of LA with a specific
property{+1}, these can be accomplished by accessing and processing each element
of LA exactly one.

Algorithm: Traversing a Linear Array

(Applying any process to each element of Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array

TRAVERSE(LA,LB,UB,N)
Step 1. Set K = LB
Step 2. Repeat Step 3 to Step 4 while K < LB+N
Step 3. PROCESS LA[K]
Step 4. K=K+1
End while
Step 5. End

14
Data Structure Sweta Bohra

Insertion; Add new element in the list.

Let “LA” be a collection of data elements in the memory of the computer.
“Insertion refers to the operation of adding another element to the collection of LA”.
In array Insertion an element may be:
1. Beginning
2. End
3. After (Value/Position/Index)
4. Before (Value/Position/Index)
5. At given Position

Insertion an element at the end of a linear array can be easily done provided by
memory space located for the array is large enough to accommodate the additional
elements.
On the other hand, suppose we need to insert an element in the middle of the array
then an average half of the element must be moved downwards to new location to
accommodate the new element and keep the order of the element.

1. Beginning/First

Algorithm: Insert element at Beginning in Linear Array

(Insert element at first location in Linear Array)
LA: Linear Array
LB: Lower Bound
1. Check whether array
UB: Upper Bound is full or not
N: Total Number present in array 2. Shift all elements by
ITEM: Number to insert one index
3. Place required
element at first index
INSERTFIRST(LA,LB,UB,N,NUM,ITEM)
Step 1. Set K = LB+N-1
Step 2. IF(K = UB)
Step 3. PRINT “ARRAY IS FULL, CAN’T INSERT VALUE”
Step 4. EXIT
Else
IF(N=0)
LA[0]=ITEM
Else
Step 5. Repeat Step 3 to Step 4 while K >= LB
Step 6. LA[K+1]=LA[K]
K=K-1
Step 7. End while
Step 8. LA[LB] = ITEM
End if

15
Data Structure Sweta Bohra

Step 9. N=N+1
End if
Step 10. End

16
Data Structure Sweta Bohra

2. End/Last

Algorithm: Insert element at End in Linear Array

(Insert element at last location in Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound 1. Check whether
array is full or not
N: Total Number present in array 2. Place required
ITEM: Number to insert element at last in list

INSERTLAST(LA,LB,UB,N,NUM,ITEM)
Step 1. Set K = UB
Step 3. IF(LB+N = UB)
Step 4. PRINT “ARRAY IS FULL, CAN’T INSERT VALUE”
Else
Step 5. LA[LB+N-1] = ITEM
Step 6. N=N+1
End if
Step 6. End

17
Data Structure Sweta Bohra

3. After

Algorithm: Insert element after specified element in Linear Array

(Insert element at specified location in Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
VAL: Reference Number where to insert ITEM
ITEM: Number to insert 1. Check whether
array is full or not
INSERTAFTER(LA,LB,UB,N,VAL,ITEM) 2. Place required
element before
Step 1. Set K = LB specified number
Set J = LB+N-1
Step 2. Repeat Step 3 to Step 4 while K < J
Step 4. if (LA[K] = VAL)
BREAK
End if
Step 5. K=K+1
Step 6. End while
Step 7. Repeat Step 3 and Step 4 while J >= K
Step 8. LA[J+1] = LA[J]
Step 9. J=J-1
End while
Step 10. LA[K+1] = ITEM
Step 11. End

18
Data Structure Sweta Bohra

19
Data Structure Sweta Bohra

4. Before

Algorithm: Insert element before specified element in Linear Array

(Insert element at specified location in Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
VAL: Reference Number where to insert ITEM
ITEM: Number to insert

INSERTBEFORE(LA,LB,UB,N,VAL,ITEM)
Step 1. Set K = LB
Set J = LB+N-1
Step 2. Repeat Step 3 to Step 4 while K < N+K
Step 4. if (LA[K] = VAL)
BREAK
End if
Step 5. K=K+1
Step 6. End while
Step 7. Repeat Step 3 and Step 4 while K >= J
Step 8. LA[J+1] = LA[J]
Step 9. J=J-1
End while
Step 10. LA[K] = ITEM
Step 11. End

20
Data Structure Sweta Bohra

Deletion; Remove element from list

Let “LA” be a collection of data elements in the memory of the computer.
“Deletion refers to the operation of removing one of the element from the Linear
Array LA”.
Deleting an element at the end of a linear array presents no difficulties but deleting
an element somewhere in the middle of the array would require that each element
be moved one location upward in order to fill up the ‘1’.

Algorithm: Delete element from Linear Array

(Delete element from Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
ITEM: Number to delete

DELETE(LA,LB,UB,N,NUM,ITEM)
Step 1. Set K = LB
Set J = N
Step 2. Repeat Step 3 to Step 4 while K < LB+N
Step 4. if (LA[K] = NUM)
BREAK
End if
Step 5. K=K+1
Step 6. End while
Step 7. Repeat Step 3 and Step 4 while K<=LB+N-1
Step 8. LA[K] = LA[K+1]
Step 9. K=K+1
End while
Step 10. N=N-1
Step 11. End

21
Data Structure Sweta Bohra

22
Data Structure Sweta Bohra

Search; Find the location of element.

Searching refers to the operation of finding location of item in ‘LA’ or printing a
message that item exists or not.
The search is said to be successful if item exists in an array and unsuccessful
otherwise.
The complexity of searching algorithms is measure in terms of the number f(n) of
compares required.
There are two different searching algorithms:
1. Linear Search.
2. Binary Search.

Linear Search; searching a linear array

Suppose ‘LA’ is a linear array with N elements. The most sufficient way to search for
a given ‘Item’ in a ‘LA’ is to compare Item with each elements of Linear Array one by
one.
i.e., first we test whether LA [1] =Item and so on.
The method which traverses LA sequentially to locate item is called Linear search or
sequential search.

Algorithm: Searching a Linear Array

(Searching element in Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
NUM: Number to search

SEARCH(LA,LB,UB,N,NUM)
Step 1. Set K = LB
Step 2. Repeat Step 3 to Step 4 while K < LB+N
Step 3. if (LA[K] = NUM)
PRINT “Element found at”,K or
End K<=LB+N-1
End if
Step 4. K=K+1
Step 5. End while
Step 6. PRINT “Element not found!”
Step 7. End

23
Data Structure Sweta Bohra

Complexity of Linear Search

1. Best Case: O(1) where the element is found at the first index.
Element to search: 2

2 3 1 9 4 7 8 2 10 21 5 56 78 15 56 28

2. Worst Case: O(n) where the element is found at the last index or element is
not present in the array.
Element to search: 28

2 3 1 9 4 7 8 2 10 21 5 56 78 15 56 28

Element to search: 50

2 3 1 9 4 7 8 2 10 21 5 56 78 15 56 28

3. Average Case: O((n+1)/2) where the average number of comparison

required to find the location of item is approximately equal to half the number
of elements in the array.

Element to search: 10

2 3 1 9 4 7 8 2 10 21 5 56 78 15 56 28

24
Data Structure Sweta Bohra

Binary Search

Array on which binary search is to applied is must be SORTED. It can be increasing

or decreasing.

A binary search or half-interval search algorithm finds the position of a specified

input value (the search "key") within an array sorted by key value
In each step, the algorithm compares the search key value with the key value of the
middle element of the array.

If the keys match, then a matching element has been found and its index, or position,
is returned. Otherwise, if the search key is less than the middle element's key, then
the algorithm repeats its action on the sub-array to the left of the middle element or,
if the search key is greater, on the sub-array to the right.

If the remaining array to be searched is empty, then the key cannot be found in the
array and a special "not found" indication is returned.

For example, if we search record of student in stack of forms of all students arranged
on roll number or any key or searching name in directory or any word in dictionary.

Algorithm: Binary Search in Linear Array

(Find element from Linear Array)
LA: Linear Array
LB: Lower Bound
UB: Upper Bound
N: Total Number present in array
ITEM: Number to search

BINARYSRCH(LA,LB,UB,N,NUM,ITEM)
Step 1. Set BEG = LB
Step 2. Set END = LB+N-1
Step 3. MID = int(BEG+END)/2
Step 4. Repeat Step 4 to Step while BEG < END AND LA[MID]!= ITEM
Step 5. if (LA[MID] < ITEM)
BEG = MID+1
End if
if (LA[MID] > ITEM)
END = MID-1
End if
MID = int(BEG+END)/2
Step 6. End while

25
Data Structure Sweta Bohra

Step 7. if (LA[MID] = ITEM)

LOC = MID
ELSE
LOC = NULL
End IF
Step 8.End

Complexity of Binary Search

1. Best Case : O(1) where the element is found at the first iteration.

Element to search: 9

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

MID = int
((BEG+END)/2)

26
Data Structure Sweta Bohra

2. Worst Case : Log2N where the element is found at the last index or element
is not present in the array.

3. Average Case : Log2N where the average number of comparison required to

find the location of item is approximately equal to half the number of elements
in the array.

Sort an (Array) Arrange an array in specific order

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the
way to arrange data in a particular 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.

Types of Sorting algorithms:-

Although there is no. of sorting algorithms best algorithm is which can solve a
problem in the minimum time and minimum space required to do so

1. Bubble Sort 8. Radix Sort

2. Insertion Sort 9. Shell Sort
3. Selection Sort 10. Comb Sort
4. Quick Sort 11. Cycle Sort
5. Heap Sort 12. Bitonic Sort
6. Counting Sort 13. Tree Sort
7. Bucket Sort 14. Stooge Sort

Sorting Categories
There are two different categories in sorting:

Internal sorting: If the input data is such that it can be adjusted in the main
memory at once, it is called internal sorting.

External sorting: When the data is in big volume the data is divided into block and
stored in secondary memory. From secondary memory data is transferred blocks by
blocks to main memory & sorting procedure is used to sort on each block. Then the
whole data is merged to get the completed sorted file. This type of sorting is called
external sorting.

27
Data Structure Sweta Bohra

If the input data is such that it cannot be adjusted in the memory entirely at
once, it needs to be stored in a hard disk, floppy disk, or any other storage
device. This is called external sorting.

Bubble Sorting
Bubble Sort: It’s one of the simplest algorithms which repeatedly iterates through
the list, compares the elements next to each other, and swaps according to the
condition passed to them.
Suppose, an array, arr [5] = {14,33,27,35,10} and we have to sort it in increasing
order then Steps followed would be as:
Here two loops would be required in sorting, the first loop for iterating and the second
loop for comparing.
As first we check if the previous element is greater than the next element then swap
it otherwise increase the counter.

1. Bubble Sort is Stable.

2. Bubble sort is in place. {No extra space is required}

Bubble Sort (Array)

28
Data Structure Sweta Bohra

29
Data Structure Sweta Bohra

Bubble Sort (Algorithm)

LA: Linear Array
N: Total Number present in array

BUBBLE(LA, N,TEMP)
Step 1. i=0
Step 2. Repeat Step 3 to Step 4 while i<N-1
Step 3. Repeat Step 4 for j=0 to [(N-1)-i]
Step 4. if(LA[j]>LA[j+1]
TEMP=LA[j]
LA[j]=LA[j+1]
LA[j+1]=TEMP
End if
Step 4. End for
Step 5. i=i+1
Step 6. End while
Step 7. End

Complexity of Bubble Sort

1. Best Case : O(n) It occurs when there is no sorting required, i.e. the
array is already sorted. The best-case time complexity of bubble sort
is O(n).
2. Worst Case : O(n2) - It occurs when the array elements are required
to be sorted in reverse order. That means suppose you have to sort
the array elements in ascending order, but its elements are in
descending order. The worst-case time complexity of bubble sort is
O(n2).
3. Average Case : O(n2) It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The
average case time complexity of bubble sort is O(n2).

30
Data Structure Sweta Bohra

Insertion Sorting
Insertion Sort: Insertion sort is the sorting mechanism where the sorted array is built
having one item at a time. The array elements are compared with each other
sequentially and then arranged simultaneously in some particular order. The analogy
can be understood from the style we arrange a deck of cards. This sort works on the
principle of inserting an element at a particular position, hence the name Insertion
Sort.

Insertion Sort (Algorithm)

LA: Linear Array
N: Total Number present in array

INSERTION-SORT(LA , n)
Step 1: for i = 1 to n
Step 2: key =LA [i]
Step 3: j=i – 1
Step 4: while j > 0 and LA[j] > key
Step 5: LA[j+1] = LA[j]
Step 6: j=j–1
Step 7: End while
Step 8: LA[j+1] = key
Step 9: End for

Properties of Insertion Sort

1. Insertion Sort is Stable.
2. Insertion sort is in place. {No extra space is required}
3. It’s a online algorithm. {At the time of insertion, sort the array}

31
Data Structure Sweta Bohra

Consider the following array: 25, 17, 31, 13, 2

32
Data Structure Sweta Bohra

Complexity of Insertion Sort

1. Best Case : O(n) It occurs when there is no sorting required, i.e. the
array is already sorted. The best-case time complexity of Insertion sort
is O(n).

2. Worst Case : O(n2) It occurs when the array elements are required to
be sorted in reverse order. That means suppose you have to sort the array
elements in ascending order, but its elements are in descending order.
The worst-case time complexity of Insertion sort is O(n2).

3. Average Case : O(n2) It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The
average case time complexity of Insertion sort is O(n2).

33
Data Structure Sweta Bohra

Selection Sorting
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place
comparison-based algorithm in which the list is divided into two parts, the sorted part
at the left end and the unsorted part at the right end. Initially, the sorted part is
empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the
leftmost element, and that element becomes a part of the sorted array. This process
continues moving unsorted array boundary by one element to the right.

1. Selection Sort is not Stable.

2. Insertion sort is in place. {No extra space is required}

Selection Sorting (Algorithm)

LA: Linear Array
N: Total Number present in array

SELECTION-SORT(LA , n)
Step 1: for i = 1 to n-1
Step 2: min=i *set current element as minimum
Step 3: for j=i+1 to n
Step 4: If (LA [j] < LA [min]) then *check the element minimum
Step 5: min=j
Step 6: End if
Step 7: End for
Step 8: If indexmin != i *swap min element with current element
Step 9: Swap LA[min] and LA[i]
Step 10: End if
Step 11: End for

Complexity of Selection Sort

1. Best Case : O(n2) It occurs when there is no sorting required, i.e. the
array is already sorted. The best-case time complexity of Selection sort
is O(n2).

2. Worst Case : O(n2) It occurs when the array elements are required to
be sorted in reverse order. That means suppose you have to sort the array
elements in ascending order, but its elements are in descending order.
The worst-case time complexity of Selection sort is O(n2).

3. Average Case : O(n2) It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The
average case time complexity of Selection sort is O(n2).

34
Data Structure Sweta Bohra

POINTER ARRAY
{5, 8, 6, 9, 1, 5, 3} Integer Array: each elements are integer.
{0.2, 2.3, 5.6, 9.2, 8.2} Real Array: each elements are real.
Pointer Array: In array if each elements are pointer then it’s called pointer array.
Pointer is the variable which contains the address of the elements.

Let we have 4 groups.

Each group consist of list of members.
Membership list is stored in memory.
The most efficient method is to form two arrays. One is members consisting of all
members one after the other.
And another pointer array group containing the starting locations of different groups.
Observe that the elements of pointer array are starting addresses of each group.

35
Data Structure Sweta Bohra

RECORDS ; Record Structures

A record is a data structure for storing a fixed number of elements. It is a collection
of related data items, each of which is called field or attribute. In record the number
to left of each variable is called level number. Each group item is followed by its
subitem. The level of subitem is 1 more than the level of group item.
Any particular field in record is accessed by using period.(dot)
{Student. Full Name. Last Name}

1. Student(15)
It indicates 15 records in a file; is a collection of records.
Any particular field in file can be accessed by
Student.Age[5]

Representation of Records in Memory

Records contain non homogeneous data.
To store record in memory we need parallel linear arrays.
i.e., one array for each elements of data item.

36
Data Structure Sweta Bohra

Array and Record

A record is a data structure for storing a fixed number of elements. It is a collection
of related data items, each of which is called field or attribute.

Arrays Records

1. Collection of homogeneous data 1. Collection of non-homogeneous

items. data.

2. Elements are described by their 2. Elements in record are described by

subscript values level numbers.
3. Natural ordering of elements 3. As data items are indexed by
attribute names, so there may not be
natural ordering of its elements.

37