Fundamental of Data

Structure
-Ms.S.D.Patil
 Syllabus

SR. NO TOPIC

Unit 1 Introduction to Algorithm and Data Structures

Unit 2 Linear Data Structure Using Sequential

Organization
Unit 3 Searching and Sorting

Unit 4 Linked List

Unit 5 Stack

Unit 6 Queue
 Searching

Searching :
Searching is a techniques of finding an element in a given list of elements.

List of element could be represented using an :

• Array
• Linked list
• tree

PROF.SHOBHA PATIL,JSPM NTC

 Searching techniques

• Searching techniques
1. Linear Search
2. Binary Search
3. Fibonacci Search
4. Index sequential search

PROF.SHOBHA PATIL,JSPM NTC

 Linear Search

Linear Search :
• The linear search is a sequential search. It compares each
element with the value being searched for.
• In the sequential search, we start searching for the key
element at the beginning of the list and continue until we find
the key element.

This approach gives us two possibilities

• Successful Search
• Unsuccessful Search

PROF.SHOBHA PATIL,JSPM NTC

Linear search example

PROF.SHOBHA PATIL,JSPM NTC

Linear search example

PROF.SHOBHA PATIL,JSPM NTC

 Analysis of Linear Search

• Complexity of linear search :

1.Best Case = O(1)
2.Worst case = O(n)

PROF.SHOBHA PATIL,JSPM NTC

 Linear Search Algorithm

Linear Search ( List A, Value x)

Step 1: Set i to 0
Step 2: if i > n-1 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 step 8
Step 7: Print element not found
Step8: Exit

PROF.SHOBHA PATIL,JSPM NTC

 Linear Search Program

List1 = [ 34,23,5,6,7,1,22,8]
print(List1)
Key = int(input(“enter the key element:”))
for i in range (len(List1)):
if key == List1[i]:
print(“key element is found :”)
break
else:
print(“element is not found”)
PROF.SHOBHA PATIL,JSPM NTC
 Linear search advantages

• Easy to understand.
• It operates on both sorted and unsorted list
• It doest not require array/list to be in order
• Easy to implement

PROF.SHOBHA PATIL,JSPM NTC

 Linear search disadvantages

• Linear search is not efficient when list

is large
• Maximum no. of comparision are N(n
Element).
• Not suitable for large problem.
• You need to search whole list.
• Linear search is slower. PROF.SHOBHA PATIL,JSPM NTC
 Binary Search
• Binary search is the most popular Search
algorithm.
• Binary search works only on a sorted set of
elements.
• Mid = (start+last )/2
23 45 52 67 78 89

• Start index =0, last index = 5

• Mid index = (0+5)/2 = 2.5

PROF.SHOBHA PATIL,JSPM NTC

Binary Search example

PROF.SHOBHA PATIL,JSPM NTC

Binary Search example

PROF.SHOBHA PATIL,JSPM NTC

Binary search algorithm

PROF.SHOBHA PATIL,JSPM NTC

Binary search algorithm

PROF.SHOBHA PATIL,JSPM NTC

Binary search Program

PROF.SHOBHA PATIL,JSPM NTC

Analysis of Binary Search

PROF.SHOBHA PATIL,JSPM NTC

 Difference between Linear & Binary Search

Linear Search Binary Search

Linear search is an algorithm to find an Binary search is an algorithm that finds
element in a list by sequentially checking the position of a target value within a
the elements of the list until finding the sorted array
matching element.
In a linear search, it is not required to sort In a binary search, it is necessary to sort
the array before searching the element. the array before searching the element
The time complexity of a linear search is The time complexity of a binary search is
O(N)  O(log2N).
The best case in a linear search is to find The best case in binary search is to find
the element in the first position i.e O(1)  the element in the middle position. i.e
O(1)
Linear search is not efficient when list is Binary search is more efficient than linear
large. search.

Easy to understand and easy to implement Binary search is more complex than linear
search.

PROF.SHOBHA PATIL,JSPM NTC

 Fibonacci Search

• Similarities with Binary Search:

1. Works for sorted arrays
2. A Divide and Conquer Algorithm.
3. Has Log n time complexity.

PROF.SHOBHA PATIL,JSPM NTC

Fibonacci Series

PROF.SHOBHA PATIL,JSPM NTC

Fibonacci Series

PROF.SHOBHA PATIL,JSPM NTC

Example

PROF.SHOBHA PATIL,JSPM NTC

Pictorial representation of f5

PROF.SHOBHA PATIL,JSPM NTC

Fibonacci pseudo code

PROF.SHOBHA PATIL,JSPM NTC

 Fibonacci search algorithm
1. Find No which is greater than equal to n from Fibonacci
series & let assume it as M.
2. Find two Fibonacci number preceding to M. i.e M1 &
M2.
3. Compare key with (list[M2+offset])
4. If Key = = (list[M2+offset]) then print Message “Key is
Found”. STOP
5. If Key > (list[M2+offset]) then update M as M1 & go to
step 2
6. If Key < (list[M2+offset]) then update M as M2 & go to
step 2.
PROF.SHOBHA PATIL,JSPM NTC
PROF.SHOBHA PATIL,JSPM NTC
PROF.SHOBHA PATIL,JSPM NTC
 Sorting
• Sorting: Sorting refers to arranging data in a particular
format. Sorting algorithm specifies the way to arrange
data in a particular order.

• 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.

PROF.SHOBHA PATIL,JSPM NTC

 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: 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.

PROF.SHOBHA PATIL,JSPM NTC

Sorting Categories

PROF.SHOBHA PATIL,JSPM NTC

Internal sort v/s external sort

PROF.SHOBHA PATIL,JSPM NTC

 SORT ORDER
• Sort Order: The sort order identifies the sequence of
sorted data either ascending order or descending order

• Unsorted Data Sorted Data

365 blue 119 purple
212 green 212 green
876 white 212 yellow
212 yellow 365 blue
119 purple 876 white
PROF.SHOBHA PATIL,JSPM NTC
 Basic Terminology
• Sort Stability : sort stability is an attribute
of a sort indicating that data with equal keys maintain
their relative order in the output
• Unsorted Data Sorted Data
365 blue 119 purple
212 green 212 green
876 white 212 yellow
212 yellow 365 blue
119 purple 876 white

PROF.SHOBHA PATIL,JSPM NTC

 Basic Terminology
• Sort Efficiency: is the measure of relative
efficiency of a sort
• Sort Passes: During the sorting data traverse
many time, Each traversal of the data is
referred as sort pass
• E.g 7 3 5
375
357

PROF.SHOBHA PATIL,JSPM NTC

 Sorting Categories
• Comparison Based Sorting Methods:
1.Bubble Sort,
2.Insertion Sort,
3.Selection Sort,
4.Quick Sort,
5.Shell Sort,

• Non-Comparison Based Sorting Methods :

1.Radix Sort,
2.Bucket Sort,
PROF.SHOBHA PATIL,JSPM NTC
 Bubble Sort
• Bubble sort is an algorithm that compares the adjacent elements and swaps
their positions if they are not in the sorted order. The order can be
ascending or descending.

How Bubble Sort Works?

Starting from the first index, compare the first and the second elements.If
the first element is greater than the second element, they are swapped.

Now, compare the second and the third elements. Swap them if they are
not in order.

The above process goes on until the last element.

PROF.SHOBHA PATIL,JSPM NTC

 Bubble Sort

• Bubble sort starts with very first two elements, comparing them to check which one
is greater.

• In this case, value 33 is greater than 14, so it is already in sorted locations. Next,
we compare 33 with 27.

• We find that 27 is smaller than 33 and these two values must be swapped . The
new array should look like this .

PROF.SHOBHA PATIL,JSPM NTC

 Bubble Sort
• Next we compare 33 and 35. We find that both are in already sorted positions.

• Then we move to the next two values, 35 and 10.

• We know then that 10 is smaller 35. We swap these values. We find that we have
reached the end of the array. After one iteration, the array should look like this

PROF.SHOBHA PATIL,JSPM NTC

 Bubble Sort
• Compare first two element . In this case, value 27 is greater than 14, so it is already
in sorted locations

• Next, we compare 27 with 33. In this case, value 33 is greater than 27, so it is
already in sorted locations

• Next, we compare 33 with 10. In this case, value 10 is smaller than 33, so we swap
these values

• Next, we compare 33 with 35. In this case, value 35 is greater than 33, so it is already in sorted
locations. We find that we have reached the end of the array. After Second iteration, the array
should look like this

PROF.SHOBHA PATIL,JSPM NTC

 Bubble Sort
• After First Sort:

• After Second Sort:

• After Third Sort:

• After Fourth Sort:

• After Fifth sort:

PROF.SHOBHA PATIL,JSPM NTC

 Bubble Sort

• Bubble sort starts with very first two elements, comparing 10 and 14 it is already in sorted locations

• Next, we compare 14 with 27. it is already in sorted locations

• Next, we compare 27 with 33. it is already in sorted locations

• Next, we compare 33with 35. it is already in sorted locations

PROF.SHOBHA PATIL,JSPM NTC

PROF.SHOBHA PATIL,JSPM NTC
Analysis of Bubble Sort

PROF.SHOBHA PATIL,JSPM NTC

Analysis of Bubble Sort

PROF.SHOBHA PATIL,JSPM NTC

Bubble sort Algorithm

PROF.SHOBHA PATIL,JSPM NTC

PROF.SHOBHA PATIL,JSPM NTC
 Insertion Sort
• This is an in-place comparison-based sorting algorithm. Here,
a sub-list is maintained which is always sorted. An element
which is to be 'insert'ed in this sorted sub-list, has to find its
appropriate place and then it has to be inserted there. Hence
the name, insertion sort

• The array is searched sequentially and unsorted items are

moved and inserted into the sorted sub-list (in the same
array).

PROF.SHOBHA PATIL,JSPM NTC

 How Insertion Sort Works?

We take an unsorted array for our example.

10 14 27 33 19 35 42 44

10 14 27 19 33 35 42 44
10 14 19 27 33 35 42 44
PROF.SHOBHA PATIL,JSPM NTC
 Insertion algorithm
1. If it is the first element, it is already sorted.
mark first element as sorted;
2. Pick next element
3. Compare with all elements in the sorted sub-
list
4. Shift all the elements in the sorted sub-list
that is greater than the value to be sorted
5. Insert the value
6. Repeat until list is sorted
PROF.SHOBHA PATIL,JSPM NTC
 Analysis of Insertion Sort

• Worst case complexity:

In worst case, each element is compared with all the other elements in the
sorted array. For N elements, there will be N2 comparisons. Therefore, the
time complexity is O(N2)

• Best case complexity:

If the input array is already in sorted order, insertion sort compares O(n)
elements and performs no swaps. Therefore, in the best case, insertion sort
runs in O(n)time.

PROF.SHOBHA PATIL,JSPM NTC

PROF.SHOBHA PATIL,JSPM NTC
 Selection sort
• 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 and the
unsorted part. Initially, the sorted part is empty and the
unsorted part is the entire list.

• The smallest element is selected from the unsorted list and

swapped with the leftmost element, and that element becomes
a part of the sorted list. This process continues moving
unsorted array boundary by one element to the right.

PROF.SHOBHA PATIL,JSPM NTC

 How Selection Sort Works?

Consider the following depicted array as an example.

we search the whole list and find that 10 is the lowest value.

So we swap10 with leftmost element 14. so after one iteration 10 is appears in the first
position of the sorted list.

We find that 14 is lowest value in the unsorted list. So we swap14 with leftmost
element of unsorted list 33.

Aftertwo iterations, two least values are positioned at the beginning in a sorted sub-list.
The same process is applied to the rest of the items in the array.

PROF.SHOBHA PATIL,JSPM NTC

How Selection Sort Works?

PROF.SHOBHA PATIL,JSPM NTC

Analysis of SELECTION Sort

PROF.SHOBHA PATIL,JSPM NTC

 selection algorithm

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the unsorted list
Step 3 − Swap with leftmost element of unsorted list
Step 4 − Repeat until list is sorted

PROF.SHOBHA PATIL,JSPM NTC

 Merge Sort

• Merge sort is a sorting technique based on divide and

conquer technique

• Merge sort first divides the array into equal halves unless the
atomic values are achieved and then combines them in a
sorted manner.

PROF.SHOBHA PATIL,JSPM NTC

 How Merge Sort Works?

we take an unsorted array as the following

divided array into two halves.

Now we divide these two arrays into halves

We further divide these arrays and we achieve atomic value which can no more be divided.

PROF.SHOBHA PATIL,JSPM NTC

 How Merge Sort Works?

Now, we combine them in exactly the same manner as they were broken down

In the next iteration of the combining phase, we compare lists of two data values, and
merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this −

PROF.SHOBHA PATIL,JSPM NTC

How Merge Sort Works?

PROF.SHOBHA PATIL,JSPM NTC

 Merge Sort algorithm

Step 1 − if it is only one element in the list it is already sorted,

return.

Step 2 − divide the list recursively into two halves until it can no
more be divided.

Step 3 − merge the smaller lists into new list in sorted order until
single sorted list is obtained

PROF.SHOBHA PATIL,JSPM NTC

 Analysis of merge Sort

• Worst Case Complexity: Ο(n log n)

• Best Case Complexity: Ο(n log n)

PROF.SHOBHA PATIL,JSPM NTC

 Quick sort

• Quick Sort is also based on the concept of Divide and

Conquer, just like merge sort.

• A large array is partitioned into two subarrays based on Pivot

element. one of which holds values smaller than the pivot
value, another subarray holds values greater than the pivot
value.

PROF.SHOBHA PATIL,JSPM NTC

 How to select Pivot?

• Pivot :- You can choose any element from the array as the
pivot element.

• You can pick pivot in different ways.

pick first element as pivot.
pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.

PROF.SHOBHA PATIL,JSPM NTC

Quick sort algorithm

PROF.SHOBHA PATIL,JSPM NTC

 Quick sort algorithm
• Step 1 − Choose the highest index value has pivot
• Step 2 − Take two variables to point left and right of the list excluding
pivot
• Step 3 − left points to the low index
• Step 4 − right points to the high
• Step 5 − while value at left is less than pivot move right
• Step 6 − while value at right is greater than pivot move left
• Step 7 − if both step 5 and step 6 does not match swap left and right
• Step 8 − if low ≥ high, the point where they met is new pivot
• Step 9 − Quick sort left part recursively
• Step 10 − Quick sort right part recursively

PROF.SHOBHA PATIL,JSPM NTC

PROF.SHOBHA PATIL,JSPM NTC
PROF.SHOBHA PATIL,JSPM NTC
 Quick Sort Pseudocode

quickSort(left, right)
if right-left <= 0
return
else pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure

PROF.SHOBHA PATIL,JSPM NTC

Quick Sort Pivot Pseudocode

PROF.SHOBHA PATIL,JSPM NTC

 Analysis of QUICK Sort
• Worst Case Complexity : O(n2)
It occurs when the pivot element picked is either the greatest or the
smallest element.
This condition leads to the case in which the pivot element lies in an
extreme end of the sorted array. One sub-array is always empty and
another sub-array contains n - 1 elements. Thus, quicksort is called
only on this sub-array.

• Best Case Complexity : O(n*log n)

It occurs when the pivot element is always the middle element or near to
the middle element.

PROF.SHOBHA PATIL,JSPM NTC

 Shell sort

• Shell sort is varition of insertion sort

• Shell sort break original list into number of smaller

sublist and each sublist is sorted using the insertion
sort.

PROF.SHOBHA PATIL,JSPM NTC

Shell sort algoritham

PROF.SHOBHA PATIL,JSPM NTC

 Shell sort Example
35 33 42 10 14 19 27 44

PROF.SHOBHA PATIL,JSPM NTC

 Non-comparison Based Sorting Methods

• Radix sort
• Bucket Sort

PROF.SHOBHA PATIL,JSPM NTC

 Radix sort

• Radix sort is advanced method of sorting.

• In this method sorting can be done digit by digit thus

in this method number of passes depends on number
of digit in maximum number.

PROF.SHOBHA PATIL,JSPM NTC

 Algorithm of Radix sort
• 1. In first pass of radix sort elements are sorted
according to last digit.
• 2. At the end of each pass elements are collected from
each bucket. Output of this pass is taken as input for
next pass.
• 3. In second pass of Radix, ten’s digit of element are
sorted.
• 4. In third pass of Radix, 100’s digit of element are
sorted & so on.

PROF.SHOBHA PATIL,JSPM NTC

 radix sort Example
• Sort the given number in ascending order using radix sort
160,550,101,342,455,896,207
pass – I
Last Digit Element
0 160,550
1 101
2 342
3
4
5 455
6 896
7 207
8
9

PROF.SHOBHA PATIL,JSPM NTC

 radix sort Example
• After completion of pass – I elements are
160,550,101,342,455,896,207
pass – II
10th digit Element
0 101,207
1
2
3
4 342
5 550,455
6 160
7
8
9 896
PROF.SHOBHA PATIL,JSPM NTC
 radix sort Example
• After completion of pass – II elements are
101,207,342,550,455,160,896
pass – III
100th digit Element
0
1 101,160
2 207
3 342
4 455
5 550
6
7
8 896
9
• After completion of pass – III list is sorted
101,160,207,342,455,550,896
PROF.SHOBHA PATIL,JSPM NTC
 Analysis of radix Sort

• Complexity = O(m.n)
Where
• m = number of digits in the maximum number in the given
list.
• n = number of data element in list.

PROF.SHOBHA PATIL,JSPM NTC

 bucket sort

• Bucket sort is a sorting algorithm that works by

distributing element of list into number of buckets.
Each bucket is then sorted individually using some
other sorting algorithm.

PROF.SHOBHA PATIL,JSPM NTC

 Algorithm of bucket sort

• 1. Set up list of initially empty bucket.

• 2. Put each element in corresponding bucket.

• 3. Sort each non empty bucket

• 4. Visit the bucket in order & put all element into

sequence and print them

PROF.SHOBHA PATIL,JSPM NTC

 bucket sort Example
• Sort the given number in ascending order using bucket sort
121,235,355,973,327,179
• Set up list as follows

100 to 200 201 to 300 301 to 400 401 to 500 501to 600 601 to 700 7001to 800 801 to 900 901to 1000

• Putting each element in its corresponding bucket

121, 235 355, 973
179 327

• Sort each bucket individually

121, 235 327,355 973
179

• Visit the bucket in order & put all element into sequence
• 121,179,235,327,355,973

PROF.SHOBHA PATIL,JSPM NTC

 Analysis of BUCKET Sort

• The Computational complexity depends on the

algorithm used to sort each bucket, the number
of buckets to use.

PROF.SHOBHA PATIL,JSPM NTC