Data Structures through C Programming

UNIT 1 Syllabus:

 Introduction to Linear Data Structures

o Definition and importance of linear data structures
o Abstract Data Types (ADTs) and their implementations
 Overview of Time and Space complexity analysis for linear data
structures
 Searching Techniques: Linear & Binary Search
 Sorting techniques: Bubble Sort, Selection Sort, Insertion Sort

What are Data Structures?

Data structure is a way of organizing (or) arranging all data items to
represent the logical relationship existing between individual elements of data
and to ensure that it can be accessed and used efficiently.

Why to use Data Structures?

 Data Structure allows you to store information locally – that is on your
hard disk
 Efficiency: proper choice of Data Structure make program efficient in
terms of space & time.
 Simplifying complex problems
 Reusability: Creating standard reusable code components, once
implemented can be used by multiple clients.
 Creating programs that are easy to understand and maintain
 Provides a controlled way to access the data

Types of Data Structures

Primitive Data Structures

  Defines a certain domain of values and the operations allowed on those
values.
 Types:
o Integer: This type is used to represent a whole number, without
any decimal (or) fractional values.
o Character: This type is used to represent a Single Character which
is enclosed within single quotations. The character can be an
alphabet, digit or special symbols.
o Floating - point: This type is used to represent a fractional
number.
o String: This type is used to represent a sequence of characters
that are enclosed within double quotations. The characters can be
alphabets, digits, special symbols, or a combination of any of these.
o Boolean: This type is used to represent a True (or) False value.

Non-Primitive Data Structures

 Also known as user-defined Data Structures.

A Linear Data Structure is a type of data structure where elements are

arranged sequentially, and each element is connected to its previous and next
elements. These structures are called linear because their elements form a
sequence or a line.
A Non-Linear Data Structure is a type of data structure where elements are
not arranged in a sequential or linear order. Instead, they are connected in a
hierarchical or interconnected manner, making traversal and access more
complex compared to linear data structures.

Let us have a peek into its Introduction

ARRAYS
An array is a collection of similar elements referred by a common name. The
array elements are stored in consecutive memory locations. The individual
elements of an array can be accessed by its index/subscript value

QUEUES
Queue operates in First-In-First-Out (FIFO) fashion.
The data are inserted at one end and deleted from another end.
STACKS
Stack operates in Last-In-First-Out (LIFO) fashion. Insertion & Deletion of
elements can be done only at one end called TOP of the stack.

TREES
Trees are used to represent the hierarchical relationship between various data
elements
 A

B C

D E F G

GRAPHS
Graph is a mathematical, non-linear data structure which can represent many
kinds of physical structures.

E4
A D
E6

E1 E3 E5
E

E2 E7
B C

V(G)={A,B,C,D,E} Vertices ; E(G)={e1,e2,e3,e4,e5,e6,e7} Edges

LINKED LIST
Linked list is a collection of N numbers of data items of same type. Each
element is referred as a node and must contain 2 fields –
 one for storing data or information
 another for storing the address for the next element
dataset  {10,45,78,47}

Following are the various types of linked list

Single Linked List − Item navigation is forward only.

Doubly Linked List − Items can be navigated forward and backward.

Circular Linked List − Last item contains link of the first element as next
and the first element has a link to the last element as previous.

 Doubly Circular Linked List: Items can be navigated forward and

backward. The first node previous part will hold the address of the last
node and the next part of the last node will hold the address of the first
node thus making a circular reference.
 Linear Vs Non-Linear Data Structures

Parameter Linear Data Structure Non-linear Data Structure

Arrangement In the case of a linear data In the case of a non-linear
of the data structure, the data items are data structure, the data pieces
elements stored in a linear order. Every are ordered non-linearly and
element is linked to the first attached hierarchically. The
and next elements in the data elements are linked to
sequence. several items.

Categories A linear data structure can be Non-linear data structures

an array, a stack, a linked list, include trees and graphs.
or a queue.

Levels The linear data structure There are several layers

consists of a single level. It has involved in this arrangement.
no hierarchy. As a result, the elements are
organized hierarchically.

Traversal Because linear data has only non-linear data structure data
 one level, traversing each data elements cannot be retrieved
item needs only one run. in a single run. It is necessary
to traverse many runs.

Memory Memory use is inefficient in Memory is used very

usages this case. efficiently in this case.

Applications Linear data structures are Image processing and artificial

mostly utilized in software intelligence both make use of
development. non-linear data structures.

Time The time complexity of a linear The time complexity of a non-

Complexity data structure grows as the linear data structure
input size grows. frequently remains constant as
the input size increases.

Relationships Only one form of relationship A non-linear data structure can

between the data pieces is have a one-to-one or one-to-
possible. many connection between its
pieces.

Real-time Usage of the DS Concepts

Arrays: Used for storing and accessing elements sequentially.
Real-world Examples:
 Weather Applications: Storing daily temperatures or precipitation data.
 Image Processing: Representing pixel data in a matrix-like structure.
Linked Lists: Ideal for dynamic memory allocation and operations requiring
frequent insertions/deletions.
Real-world Example:
 Operating Systems: Managing free and allocated memory blocks with
linked lists in a heap memory.
 Music Playlists: Maintaining songs as a queue where you can add/remove
tracks dynamically.
 Browser Tabs: A stack implemented with a linked list helps track open
tabs.
 Call Centres: A queue implemented with a linked list organizes incoming
calls dynamically.
 Web Browsers: History navigation where you can move back and forth
between visited pages.
 Image Viewers: Switching between previous and next images in a gallery.

Stacks: Follows the Last In, First Out (LIFO) principle.

 Browser History: When you visit a new webpage, the current page is
pushed onto the stack. Going back pops the top page off the stack.
 Undo/Redo Functionality: MS Word or Photoshop: Undo (pop the last
change) and redo (push the reverted change).
 Expression Evaluation: Compilers use stacks for syntax parsing and
expression evaluation.
 Backtracking Algorithms
o Maze Solvers: Tracking the path taken and backtracking when a
dead end is encountered.
o Game Development: Undoing moves in games like chess or
Sudoku.

Queues: Follows the First In, First Out (FIFO) principle.

 Customer Support Systems: Handling queries in the order they arrive.
 Print Queue: Sending documents to a printer.
 Task Scheduling in Operating Systems: Running higher-priority tasks
before others.
Trees: Hierarchical data representation.
 File Systems: Organizing files and directories.
 Databases: Used in relational databases like MySQL, PostgreSQL, and
MongoDB for indexing.
 Autocomplete Systems:
o Search Engines: Google Search autocomplete.
o Text Editors: Code completion in IDEs.
o Mobile Keyboards: Suggesting words while typing.

Graphs: Represent relationships between entities.

 Social Networks: Representing connections between users.
 Routing Algorithms: Shortest path calculation in Google Maps.
Let us say for example – We must go from point A to point B within a
particular time; Search for multiple routes that can take us to our destination,
and whichever is faster.

From Location

To Location

Input Given -
Location

Data Provided
is Processed

output is
produced.

We can further classify the

Linear Data Structures as
Static Data Structure
In this type, the memory
occupancy (size) is decided at compile-time itself  Hence the maximum size
remains fixed. It cannot grow or shrink according to the requirement.
Advantage: Fast Access
Disadvantage: Slower Insertion & Deletion
Arrays are of Static Linear Data Structure category.

Dynamic Data Structure

In this type how much of memory space required is calculated at run-time
(dynamic) and therefore the maximum size is flexible.
Whenever we insert a new element size automatically grows and when a data
is deleted, size automatically shrinks.
Advantage: Faster Insertion & Deletion
Disadvantage: Slower Access
Linked Lists are of Dynamic Linear Data Structure category.

So, we can clearly see that the advantage of one is the disadvantage of the
other type. Choice of Data Structure purely depends upon the user
requirements.

Linear Data Structure

What is a Linear Data Structure?
Linear Data Structures are a type of data structure in computer science where
data elements are arranged sequentially or linearly. Each element has a
previous and next adjacent, except for the first and last elements.

Characteristics of Linear Data Structure

1. Sequential Organization
Elements are stored in a sequential manner (one after another).
 2. Order Preservation
The order in which elements are added to the data structure is preserved.

3. Fixed or Dynamic Size

Linear data structures can have either fixed or dynamic sizes.
Arrays typically have a fixed size when they are created.
Other like Linked Lists, Stacks, and Queues are dynamic (Size can grow &
shrink when elements are added or removes respectively)

4. Direct or Sequential Access

Arrays allow direct access using an index (random access).
Linked lists, stacks, and queues require sequential access (element-by-
element traversal).

5. Memory Allocation: Contiguous or Linked

Arrays use contiguous memory locations.
Linked lists use nodes connected via pointers.

6. Efficient Traversal
One of the fundamental operations with Linear Data Structures is
sequential traversal. You can start at the first element and move through
the structure one element at a time until you reach the end. This
sequential access is particularly useful for processing data in a
systematic manner.
Traversing elements is straightforward using loops or recursion.

7. Insertion and deletion

Linear Data Structures allow for the insertion and deletion of elements at
specific positions. These operations can be performed efficiently in most
Linear Data Structures, although the exact mechanisms may vary from
one type to another.

Common operations on Linear Data Structures

Some of the most common operations on Linear Data Structures include:

1) Access: Accessing elements involves retrieving data from a specific position

within the Linear Data Structure. To access an element, you typically specify
the index or position, and the Data Structure returns the element stored at that
location.

2) Insertion: Inserting an element entail adding a new data element at a

specific position within the structure. Depending on the type of Linear Data
Structure, this operation can be performed at the beginning, end, or anywhere
in between.
3) Deletion: Deletion involves removing an element from a specified position
within the linear structure. This operation can free up memory or simply
reorganise the elements to maintain the linear order.

4) Traversal: Traversal is the process of iterating through all the elements in

the Linear Data Structure sequentially. This operation is fundamental for
examining or processing the data in a systematic manner.

Types of Linear Data Structures

Time & Space Complexity

We already saw in the previous chapter that:
Data Structure is the organization of data in a way so that it can be used
efficiently.

Efficiency of Data Structure is always measured in terms of Time and Space.

An ideal data structure could be the one that takes the least possible time for
all its operations and consumes the least memory space.

Time Complexity
  Time complexity is a measure of how the runtime of an algorithm scales
as the input size increases.

 Time complexity is not about measuring the exact runtime of an

algorithm in seconds or milliseconds. Instead, it is a way to analyse the
efficiency of algorithms, describing how the runtime grows relative to the
input size.

Space Complexity
 Space complexity is the amount of memory an algorithm uses to solve a
problem.
 It is the total space taken by the algorithm with respect to the input size.
 It includes both Auxiliary space and space used by input.

Note: Auxiliary Space is the extra space or temporary space used by an

algorithm.

Why is Time Complexity Important?

Understanding time complexity is crucial for:

 Choosing the Right Algorithm
When solving a problem, you often have multiple algorithms to choose
from. Time complexity helps you select the most efficient one, especially
when dealing with large datasets.

 Predicting Performance
Time complexity allows you to estimate how well an algorithm will
perform as the input size grows. This is essential for designing
applications that can handle increasing amounts of data.

 Optimizing Code
By analysing the time complexity of your code, you can identify
bottlenecks and areas for improvement, leading to more efficient
programs.
 On what basis we could compare the Time Complexity of the
Data Structure?

Key Factors -
a. Input Size(n)
How does the data structure perform as the input size grows?
b. Frequency of Operations
Which operations are performed most frequently in your use
case?
c. Memory Usage
Some data structures trade time complexity for memory
efficiency.
d. Data Organization
How the data is organized affects the time complexity of
operations.

Based on the Operations performed on the Data

Structures
Operations Description
1 Insertion Adding a new element
2 Deletion Removing an element
3 Searching Finding an element
4 Access Retrieving an element
5 Sorting Arranging elements in a particular order
6 Traversal Visiting all the elements
7 Minimum & Maximum Finding the min and max values
Value

Time Complexity Table

Example
O(1) Constant The runtime doesn't depend on the Accessing an
time input size. array element
Whatever the input size n, the
algorithm takes a constant amount
of time.
O(log n) Logarithmic The runtime increases Binary search
time logarithmically with the input size.
These are slower than an ever-
growing linear function.
O(n) Linear time The runtime increases linearly with Linear search
the input size.
O(n log n) Linear A combination of linear and Merge sort,
Logarithmic logarithmic factors. Quick sort
time Faster growing than linear but
 slower than quadratic.
O(n2) Quadratic The runtime increases quadratically Bubble sort,
time with the input size. Selection sort
These functions grow faster than the
linear logarithmic functions
O(n3) Cubic time Faster growing than quadratic but
slower than exponential.
O(2n) Exponential The runtime doubles with each Solving the
time additional input. Tower of Hanoi
Faster than all the functions
mentioned here, except the factorial
function.
O(n!) Factorial Fastest growing than all the Generating all
time functions mentioned here. permutations

Comparing Common Data Structures

Data Acces Searc Inserti Deleti Use Case
Structure s h on on
Array O(1) O(n) O(n) O(n) Fixed-size data, random
access
Linked List O(n) O(n) O(1) O(1) Dynamic data, frequent
insertions/deletions
Hash Table O(1)* O(1)* O(1)* O(1)* Fast lookups, no ordering
Binary O(log O(log O(log O(log Ordered data, balanced
Search Tree n)* n)* n)* n)* trees
(BST)
Stack O(n) O(n) O(1) O(1) LIFO operations
Queue O(n) O(n) O(1) O(1) FIFO operations

Note: *Assuming average-case scenarios and balanced structures.

Types of Time Complexity Notations
 Big-O Notation (O)
Describes the upper bound of an algorithm's runtime. It represents the
worst-case scenario.
 Big Omega Notation (Ω)
Describes the lower bound of an algorithm's runtime. It represents the
best-case scenario.
 Big Theta Notation (Θ)
Describes the tight bound of an algorithm's runtime. It represents both
the upper and lower bounds, meaning the algorithm's runtime grows at
the same rate in both the best and worst cases.
 Little o Notation (o)
Describes an upper bound that is not tight. It means the algorithm's
runtime grows strictly slower than the given function.
 Little omega Notation (ω)
Describes a lower bound that is not tight. It means the algorithm's
runtime grows strictly faster than the given function.
The most common and usually the most relevant  Big-O Notation (O)
Worst-case: The operation takes the longest possible time.
Average-case: The operation takes a typical amount of time.
Best-case: The operation takes the shortest possible time.

Searching Techniques
Searching techniques are fundamental operations that allow us to find specific
elements within a data structure.
The search is said to be successful or unsuccessful depending on whether the
element that is to be searched is found or not.

Commonly used techniques –

 Linear Search
 Binary Search
 Linear Search Technique
It is a very simple searching technique.
This type of Searching technique is also known as Sequential Search.
 In this type, a sequential search is made over all items one by one.
 Sorted Data Structures: Starts from the element at the 0th index and
continues till the element is found or an element whose value is greater
than the value being searched is reached, assuming the list is sorted in
ascending order.
 Unsorted Data Structures: Starts from the 0th index and continues
until the element is found or the end of the list is reached.

Algorithm:
1. Read the data from the user and store it in a array.
2. Read the element to searched for from the user and store it within a
variable.
3. Start from Index position 0 (1st element) of the list and compare one by
one with the element to be searched for.
a. If a match is found return the matched element’s index value and
its position with in the list. And stop the program
 b. If a match is not found then continue search by comparing the next
element within the list one by one until a match is found.
c. If the searching element is not available within the given list, then
print a message “element not found”.

Working Examples
Example 1:
This is the List of numbers – 15, 5, 20, 35, 2, 42, 67, 19
0 1 2 3 4 5 6 7
15 5 20 35 2 42 67 17

N=8
Number to Search for = 42

1st Iteration: Compare 15 == 42 : False

2nd Iteration: Compare 5 == 42 : False
3rd Iteration: Compare 20 == 42 : False
4th Iteration: Compare 35 = 42 : False
5th Iteration: Compare 2 == 42 : False
6th Iteration: Compare 42 == 42 : True  Stop the Iteration and return the
Index position of the matching element, which is 5 according to our example.
-----------------------------------------------------------------------------------

Example 2:
This is the List of numbers – 15, 5, 20, 35, 2, 42, 67, 19
0 1 2 3 4 5 6 7
15 5 20 35 2 42 67 17

N=8
Number to Search for = 100

 If the element is present – Print the Index and the Position of the element
 If the element is not present – Print -1

1st Iteration: Compare 15 == 100: False

2nd Iteration: Compare 5 == 100: False
3rd Iteration: Compare 20 == 100: False
4th Iteration: Compare 35 = 100: False
5th Iteration: Compare 2 == 100: False
6th Iteration: Compare 42 == 100: False
7th Iteration: Compare 67 == 100 : False
8th Iteration: Compare 17 == 100: False

Now it reaches the end of the list and we couldn’t get a match; Hence it will
return -1 as the result.
-----------------------------------------------------------------------------------
Time complexity
Counting the number of comparisions done to find out the element.
Time taken to search elements keep increasing as the number of elements are
increased.

Best Case O(1) The target element Only one comparison is needed.
is the first element int arr[] = {10, 20, 30, 40, 50};
in the list. int key = 10; // First element

Worst O(n) The target element The algorithm has to scan all
Case is at the last elements.
position or not int arr[] = {10, 20, 30, 40, 50};
present in the list. int key = 60; // Not in the list
Average O(n) The target element On average, the search will check
Case is somewhere in the n/2 elements.
middle of the list. int arr[] = {10, 20, 30, 40, 50};
int key = 30; // Middle element

Space complexity
Linear Search has a constant space complexity O(1), meaning it does not
require extra memory apart from the input array and a few variables.
The search operates directly on the given data without additional storage.

Code:
#include<stdio.h>
// Function to perform linear search on an unsorted array
int linearSearchUnsorted(int arr[], int n, int target)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == target)
{
// Return the index if the target is found
return i;
}
}
// Return -1 if the target is not found
return -1;
}

int main()
{
// Variable declarations
int n,i,x;

// Getting the number of elements

printf("Enter the Number of Elements you want to store: ");
scanf("%d",&n);

// Creating the Array

 int a[n];

// Loop to read N values and store it into the array

for(i=0;i<n;i++)
{
printf("\nEnter the Element: ");
scanf("%d",&a[i]);
}

// Getting the value of the element to search for within the array
printf("\nEnter the Number to search: ");
scanf("%d",&x);

// Calling the Linear Search Function

int result = linearSearchUnsorted(a,n,x);

// Printing the Result

if (result != -1)
{
printf("Element %d is found at index %d\n", x, result);
} else {
printf("Element %d is not found within the array\n", x);
}

return 0;
}

Input:
Enter the Number of Elements you want to store: 10
Enter the Element: 15
Enter the Element: 52
Enter the Element: 20
Enter the Element: 37
Enter the Element: 89
Enter the Element: 94
Enter the Element: 15
Enter the Element: 30
Enter the Element: 88
Enter the Element: 66
Enter the Number to search: 30
Output:
Element 30 is found at index 7
------------------------------------------------------------------------------
 Binary Search Technique
Binary search is an efficient algorithm for finding an item from a sorted list of
items. It works by repeatedly dividing in half the portion of the list that could
contain the item, until you have narrowed down the possible locations to just
one.
Technique Used: Divide and Conquer Technique

Note: Binary search works only on a sorted list

Algorithm (steps)

1. Read the list of numbers from the user

(Note: The Numbers must be in Sorted Order)
2. Read the number to be searched for
3. Initialize 2 values: low and high
low will pointing to the starting index of the list
high will be pointing to the ending index of the list
4. Condition for Iteration: As long as low is less than or equal to high:
a. Calculate mid
Formula: mid = (low+high) / 2
(Note: Result must be an Integer Number)
b. Check: Searching element == mid - True: return mid as the index position
and terminate the loop.
c. Check: Searching element < mid: update the high value as (mid - 1)
d. Check: Searching element > mid: update the low value as (mid + 1)
5. If the Searching element is not found print a msg saying “Element not
found”
 Working Examples
Example 1

This is the List of numbers – 6, 12, 17, 23, 38, 45, 77, 84, 90
Let us store it within a list: Index position starts from 0 and ends with N-1
where – N represents the number of elements within the list.

N=9
Number to Search for = 45
Fixing the low and high vallues:
low = 0
high = N-1  9 – 1  8

1st Iteration  low <= high  0<= 8: True

Mid = (LB+UB)/2  (0+8) = 4
MID

45==38: False
Searching element is greater than MID

low = mid+1  4+1  5

low = 5, high = 8

2nd Iteration  low <= high  5<= 8: True

New mid value = (5+8)/2  6
MID

45 == 77: False
Searching element is lesser than MID
high = mid – 1  6 – 1  5
low = 5, high = 5

3rd Iteration  low <= high  5<= 5: True

New mid value = (5+5)/2  5
MID

45 == 45: True
Match found
So, the program will return the index position of the mid  5
-----------------------------------------------------------------------------------
Example 2
This is the List of numbers – 10, 12, 20, 32, 50, 55, 65, 80, 90
Let us store it within a list: Index position starts from 0 and ends with N-1
where – N represents the number of elements within the list.

0 1 2 3 4 5 6 7 8
10 12 20 32 50 55 65 80 90
N = 9; Number to Search for = 12
Fixing the low and high vallues:
low = 0
high = N-1  9 – 1  8
1st Iteration  low <= high  0<= 8: True
Mid = (LB+UB)/2  (0+8) = 4
MID

0 1 2 3 4 5 6 7 8
10 12 20 32 50 55 65 80 90

12==50: False
Searching element is lesser than MID
high = mid – 1  4 – 1  3
low = 0, high = 3
2nd Iteration  low <= high  0<= 3: True
New mid value = (0+3)/2  2
MID

0 1 2 3 4 5 6 7 8
10 12 20 32 50 55 65 80 90

12==20: False
Searching element is lesser than MID
high = mid – 1  2 – 1  1
low = 0, high = 1

3rd Iteration  low <= high  0<= 1: True

New mid value = (0+1)/2  1
MID

0 1 2 3 4 5 6 7 8
10 12 20 32 50 55 65 80 90
12==12: True
Match found; So, the program will return the index position of the mid 1
-----------------------------------------------------------------------------------
Time complexity

Best Case O(1) The target element is Only one comparison is

the middle element in needed.
the first comparison. int arr[] = {10, 20, 30, 40, 50};
int key = 30; // Middle element
Worst O(log The element is at either The search space halves each
Case n) end of the array, or not time, leading to log₂(n)
present at all. comparisons.
int arr[] = {10, 20, 30, 40, 50,
60, 70, 80};
int key = 80; // Last element
Average O(log The element is On average, the search will
Case n) randomly placed in the take around log₂(n)
array. comparisons.
int arr[] = {5, 10, 15, 20, 25,
30, 35, 40};
int key = 15;

Space complexity
Iterative Binary Search O(1) It is more space-efficient because it
does not use the call stack.
Uses constant space regardless of the
dataset size.
Recursive Binary Search O(log n) due to function call overhead
(recursive call)

Code:
#include <stdio.h>
// Function to perform the Sorting of the Array
void Sort(int arr[] , int n)
{
int i,j,temp;
for (i=0; i<n; ++i)
{
for (j=i+1; j<n; ++j)
{
if (arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}

// Function to perform Binary Search

int binarySearch(int array[], int x, int low, int high)
{
// Repeat until the pointers low and high meet each other
while (low <= high)
{
int mid = low + (high - low) / 2;

if (array[mid] == x)
return mid;

if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}
return -1;
}
int main(void)
{
int a[20],n,x,i;

printf("How many elements?");

scanf("%d",&n);

printf("Enter %d array elements:\n",n);

for(i=0;i<n;++i)
{
scanf("%d",&a[i]);
}

printf("\nEnter element to search: ");

scanf("%d",&x);

// Sorting the Array before performing the search

Sort(a,n);
// Printing the Sorted Array
printf("\nSorted Array - ");
for(i=0;i<n;++i)
{
printf("%d ",a[i]);
}

// Calling the Function to search for the element

int result = binarySearch(a, x, 0, n - 1);
// Printing the Result
if (result == -1)
printf("\nNot found");
else
printf("\nElement is found at index %d", result);

return 0;
}

Input:
How many elements?8
Enter 8 array elements:
14
16
10
5
78
92
63
48
Enter element to search: 16
 Output:
Sorted Array - 5 10 14 16 48 63 78 92
Element is found at index 3
-----------------------------------------------------------------------------------
Comparison between Linear Search and Binary Search
Techniques

Features Linear Search Binary Search

Working Sequentially checks each Repeatedly divides the dataset
element in the dataset until in half and narrows down the
the target element is found or search space by comparing the
the end of the dataset is target element with the middle
reached. element.
Algorithm Type Sequential Search Divide and Conquer Search
Data Requirement Works on both sorted & Requires sorted data
unsorted data
Time Complexity O(1) (First element is the O(1) (Middle element is the
(Best Case) target) target)
Time Complexity O(n) (Last element or not O(log n) (Last element or not
(Worst Case) found) found)
Time Complexity O(n) O(log n)
(Average Case)
Space Complexity O(1) (Iterative) O(1) (Iterative)
O(log n) (Recursive)
Method Searches each element one by Repeatedly divides the array in
one half
Efficiency Inefficient for large datasets Highly efficient for large
datasets
Use Case Small or unsorted datasets Large, sorted datasets
Suitable for Linked lists, arrays, and small Arrays, sorted lists
lists
Mathematical Maximum comparisons: n Average comparisons: log2 n
Comparison Average comparisons: n/2
 Sorting Techniques
What is Sorting?
Sorting is the process of arranging elements in a specific order, typically
ascending or descending.

Example:
Unsorted Array: [5, 2, 9, 1, 5, 6]
Sorted in Ascending Order: [1, 2, 5, 5, 6, 9]
Sorted in Descending Order: [9, 6, 5, 5, 2, 1]

Sorting Techniques

Comparison Based Non-Comparison

Sorting Techniques Bases Sorting
Techniques

Comparison Based Sorting Techniques

 Bubble Sort
 Selection Sort
 Insertion Sort
 Merge Sort
 Quick Sort
 Heap Sort

Non-Comparison Bases Sorting Techniques

 Counting Sort
 Radix Sort
 Bucket Sort

Comparison Chart of the Sorting Techniques

Algorithm Best Case Worst Average Space Stability

Case Case Complexity
Bubble Sort O(n) O(n²) O(n²) O(1) Stable
Selection Sort O(n²) O(n²) O(n²) O(1) Not Stable
Insertion Sort O(n) O(n²) O(n²) O(1) Stable
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Stable
Quick Sort O(n log n) O(n²) O(n log n) O(log n) Not Stable
Heap Sort O(n log n) O(n log n) O(n log n) O(1) Not Stable
 When to Use Different Sorting Algorithms

Scenario Best Sorting Algorithm

Small datasets Insertion Sort or Bubble Sort
Large datasets Merge Sort or Quick Sort
Requires stability Merge Sort or Insertion Sort
Sorting linked lists Merge Sort
Sorting mostly sorted data Insertion Sort
Fastest general-purpose sort Quick Sort
 Bubble Sort Technique
Algorithm:
1. Create an array of N elements from the user
2. Start at the beginning of the array list.
3. Compare the first two elements. If they're in the wrong order (If the
current element is greater than the next element), swap them.
4. Move to the next pair of elements and repeat the comparison and swap
process (repeat step 3 & 4) until the end of the list.
5. After the first iteration, the largest element will be at the end. Repeat the
process for the remaining elements.
6. Continue iterating until no swaps are needed, indicating the list is sorted.

Time Complexity

Best Case Average Case Worst Case

O(n) O(n²) O(n²)
When the array is Random order elements When elements are in
already sorted, only one require (n²/2) swaps. reverse order, every
pass is required. element must be
swapped in each pass.

Space Complexity
 O(1) - Bubble Sort is in-place, meaning it does not require extra memory
apart from a few auxiliary variables.

Advantages:
 Simplicity: Easy to understand and implement.
 No Additional Memory: It is an in-place sorting algorithm, so it doesn't
require extra memory.
 Adaptive: Can detect if the array is already sorted and terminate early
(with the swapped flag optimization).

Disadvantages:
 Inefficient for large datasets due to its quadratic time complexity
(O(n^2)).
 Poor Performance: Compared to more advanced algorithms like Quick
Sort or Merge Sort, Bubble Sort is much slower.

Working Example
list = {23,28,45,5,56,32};
Pass 1:
0 1 2 3 4 5
23 28 45 5 56 32

Compare: 0 and 1 - 23>28: False

Compare: 1 and 2 - 28>45: False
Compare: 2 and 3 - 45>5: True
perform swapping
0 1 2 3 4 5
23 28 5 45 56 32

Compare: 3 and 4 - 45>56: False

Compare: 4 and 5 - 56>32: True
perform swapping
0 1 2 3 4 5
23 28 5 45 32 56

Pass 2:
0 1 2 3 4 5
23 28 5 45 32 56

Compare: 0 and 1 - 23>28: False

Compare: 1 and 2 - 28>5: True
perform swapping
0 1 2 3 4 5
23 5 28 45 32 56

Compare: 2 and 3 - 28>45: False

Compare: 3 and 4 - 45>32: True
perform swapping

0 1 2 3 4 5
23 5 28 32 45 56

Pass 3:
0 1 2 3 4 5
23 5 28 32 45 56

Compare: 0 and 1 - 23>5: True

perform swapping
0 1 2 3 4 5
5 23 28 32 45 56

Compare: 1 and 2 - 23>28: False

Compare: 2 and 3- 28>32 : False

0 1 2 3 4 5
 5 23 28 32 45 56

Pass 4:
0 1 2 3 4 5
5 23 28 32 45 56

Compare: 0 and 1 - 5>23: False

Compare: 1 and 2 - 23>28: False

0 1 2 3 4 5
5 23 28 32 45 56

Pass 5:
0 1 2 3 4 5
5 23 28 32 45 56

Compare: 0 and 1 - 5>23: False

0 1 2 3 4 5
5 23 28 32 45 56

Complete List is sorted.

-----------------------------------------------------------------------------------
Code:
#include <stdio.h>
// Function to perform the Bubble Sort Technique
void bubbleSort(int arr[], int n)
{
int i, j, temp;
int swapped;

// Outer loop for each pass

for (i = 0; i < n - 1; i++)
{
swapped = 0; // Track if any swaps are made

// Inner loop for comparing adjacent elements

for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
// Swap elements if they are in the wrong order
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

swapped = 1; // Mark that a swap occurred

}
}
 // If no swaps were made, the list is already sorted
if (swapped == 0)
{
break;
}
}
}
// Main Code
int main()
{
// Declaring variable for maintaining the size of the array
int n;

// Input the size of the array

printf("Enter the number of elements: ");
scanf("%d", &n);

// Creating the array of size N

int arr[n];

// Input the elements of the array

printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}

// Call the bubbleSort function

bubbleSort(arr, n);

// Output the sorted array

printf("Sorted array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

Input:
Enter the number of elements: 5
Enter 5 elements: 34 12 56 7 23
Output:
Unsorted array: 34 12 56 7 23
Sorted array: 7 12 23 34 56

Let us try to understand the logic of how the loop works:

Array: [5, 3, 8, 4, 6]

Number of Passes:
  The outer loop runs n-1 times (where n is the size of the array). In this
case, n = 5, so there are 4 passes.
Swapping:
 Swaps occur only when adjacent elements are in the wrong order.
Optimization:
 If no swaps occur during a full pass, the array is already sorted, and the
algorithm terminates early.

Pass Array State Action Performed

0 [5, 3, 8, 4, 6] Initial array
1 [3, 5, 8, 4, 6] Swap 5 and 3
1 [3, 5, 8, 4, 6] No swap (5 < 8)
1 [3, 5, 4, 8, 6] Swap 8 and 4
1 [3, 5, 4, 6, 8] Swap 8 and 6
2 [3, 5, 4, 6, 8] No swap (3 < 5)
2 [3, 4, 5, 6, 8] Swap 5 and 4
2 [3, 4, 5, 6, 8] No swap (5 < 6)
3 [3, 4, 5, 6, 8] No swap (3 < 4)
3 [3, 4, 5, 6, 8] No swap (4 < 5)
4 [3, 4, 5, 6, 8] No swap (3 < 4)
Final [3, 4, 5, 6, 8] Sorted array

-----------------------------------------------------------------------------------

Selection Sort Technique

 Selection sort is a simple sorting algorithm.
 This sorting algorithm is an in-place comparison-based algorithm.

Algorithm:
1. Get the values from the user and store it within the array.
2. Select the first element of the list (i.e., Element at 0 th position in the list)
as the MIN
3. Compare the MIN with all the other elements in the list starting from
position 1 till the end of the list. In every comparison, if any element is
found smaller than the MIN (for Ascending order) is swapped with the
 value at that location. After 1st iteration the smallest value will be placed
at the 1st location within the array.
4. Increment MIN to point to the next location.
5. Repeat the same procedure till the entire list is sorted.

Advantages:
 Simple to understand and implement.
 Performs well on small datasets or when the number of swaps needs to
be minimized.
 In-place sorting (requires no additional memory).

Disadvantages:
 Inefficient for large datasets due to its quadratic time complexity
(O(n^2)).
 Performs the same number of comparisons regardless of the input order.

Time Complexity
Best Case Average Case Worst Case
O(n²) O(n²) O(n²)

Space Complexity
In-place sorting; No extra memory required except a few variables. So, the
space complexity is constant - O(1)

Working Example

Example: array = [15,20,10,30,50,18,5,45]

0 1 2 3 4 5 6 7
15 20 10 30 50 18 5 45

1st Iteration:
Min = Index position 0
2nd Iteration
0 1 2 3 4 5 6 7
5 20 15 30 50 18 10 45
Min = Index position 1
Compare Index 1 and 2: 20>15 – True
perform swapping
0 1 2 3 4 5 6 7
5 15 20 30 50 18 10 45

Compare Index 1 and 3: 15>30: False

Compare Index 1 and 4: 15>50: False
Compare Index 1 and 5: 15>18: False
Compare Index 1 and 6: 15>10: True
perform swapping
0 1 2 3 4 5 6 7
5 10 20 30 50 18 15 45

Compare Index 1 and 7: 10>45: False

Final List after 2nd Iteration:
0 1 2 3 4 5 6 7
5 10 20 30 50 18 15 45

3rd Iteration:
0 1 2 3 4 5 6 7
5 10 20 30 50 18 15 45

Min = Index position 2

Compare Index 2 and 3: 20>30 – False
Compare Index 2 and 4: 20>50 – False
Compare Index 2 and 5: 20>18 – True
perform swapping
 0 1 2 3 4 5 6 7
5 10 18 30 50 20 15 45

Compare Index 2 and 6: 18>15 – True

perform swapping
0 1 2 3 4 5 6 7
5 10 15 30 50 20 18 45

Compare Index 2 and 7: 15>45 – False

Final List after 3rd Iteration:
0 1 2 3 4 5 6 7
5 10 15 30 50 20 18 45

4th Iteration:
0 1 2 3 4 5 6 7
5 10 15 30 50 20 18 45

Min = Index position 3

Compare Index 3 and 4: 30>50 – False
Compare Index 3 and 5: 30>20 – True
perform swapping
0 1 2 3 4 5 6 7
5 10 15 20 50 30 18 45

Compare Index 3 and 6: 20>18 – True

perform swapping
0 1 2 3 4 5 6 7
5 10 15 18 50 30 20 45

Compare Index 3 and 7: 18>45 – False

Final List after 4th Iteration:
0 1 2 3 4 5 6 7
5 10 15 18 50 30 20 45

5th Iteration:
0 1 2 3 4 5 6 7
5 10 15 18 50 30 20 45

Min = Index position 4

Compare Index 4 and 5: 50>30 – True
perform swapping

0 1 2 3 4 5 6 7
5 10 15 18 30 50 20 45

Compare Index 4 and 6: 30>20 – True

 perform swapping
0 1 2 3 4 5 6 7
5 10 15 18 20 50 30 45

Compare Index 4 and 7: 20>45 – False

Final List after 5th Iteration:
0 1 2 3 4 5 6 7
5 10 15 18 20 50 30 45

6th Iteration:
0 1 2 3 4 5 6 7
5 10 15 18 20 50 30 45

Min = Index position 5

Compare Index 5 and 6: 50>30 – True
perform swapping
0 1 2 3 4 5 6 7
5 10 15 18 20 30 50 45

Compare Index 5 and 7: 30>45 – False

Final list after 6th iteration
0 1 2 3 4 5 6 7
5 10 15 18 20 30 50 45

7th Iteration:
0 1 2 3 4 5 6 7
5 10 15 18 20 30 50 45

Min = Index Position 6

Compare Index 6 and 7: 50>45: True
perform swapping
0 1 2 3 4 5 6 7
5 10 15 18 20 30 45 50
The list is over and completely swapped.
Code:
#include <stdio.h>
// Function to implement the Selection Sort Technique
void selectionSort(int arr[], int n)
{
int i, j, minIndex, temp;

// Outer loop to iterate through the array

for (i = 0; i < n - 1; i++) {
// Step 1: Assume the first element of the unsorted part is the minimum
minIndex = i;

// Step 2: Find the smallest element in the unsorted part

for (j = i + 1; j < n; j++)
 {
if (arr[j] < arr[minIndex])
{
minIndex = j; // Update the index of the smallest element
}
}

// Step 3: Swap the found minimum element with the first element of the
unsorted part
if (minIndex != i)
{
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}

// Print the array after each iteration (optional for understanding)

printf("Array after iteration %d: ", i + 1);
for (int k = 0; k < n; k++)
{
printf("%d ", arr[k]);
}
printf("\n");
}
}
// Main Code
int main()
{
int n;

// Input the size of the array

printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];

// Input the elements of the array

printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}

// Call the selectionSort function

selectionSort(arr, n);

// Output the sorted array

printf("Sorted array:\n");
 for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Input:
Enter the number of elements: 8
Enter 8 elements:
78
52
10
46
91
19
30
97
Output:
Array after iteration 1: 10 52 78 46 91 19 30 97
Array after iteration 2: 10 19 78 46 91 52 30 97
Array after iteration 3: 10 19 30 46 91 52 78 97
Array after iteration 4: 10 19 30 46 91 52 78 97
Array after iteration 5: 10 19 30 46 52 91 78 97
Array after iteration 6: 10 19 30 46 52 78 91 97
Array after iteration 7: 10 19 30 46 52 78 91 97
Sorted array:
10 19 30 46 52 78 91 97
------------------------------------------------------------------------------

Insertion Sort Technique

 Insertion Sort is a simple and efficient comparison-based sorting
algorithm.
 It works similarly to how you might sort a hand of playing cards.
 It works by picking one element at a time and inserting it into its
correct position relative to the sorted portion of the array.
 It is particularly efficient for small or nearly sorted datasets.

Algorithm
1. Get N values from the user and store it within the dataset.
2. Start: Assume the first element is already sorted.
3. Iterate: Take the next element and compare it with the elements in the
sorted part.
4. Insert: Insert the element into its correct position in the sorted part by
shifting larger elements to the right.
5. Repeat: Continue this process until all elements are sorted.
Advantages:
 Efficient for small datasets and nearly sorted data.
 Simple to implement and understand.
 Stable sorting algorithm (preserves order of duplicate elements).
 In-place sorting (O(1)) – no extra memory required.

Disadvantages:
 Inefficient for large datasets due to its quadratic time complexity O(n^2)
- SLOW.

Time Complexity

Best Case Average Case Worst Case

O(n) O(n²) O(n²)
If the array is already If the elements are If the array is sorted in
sorted, only n-1 randomly ordered, it reverse order, every
comparisons are required, performs (n²/4) element must be
but no swaps. comparisons and swaps on compared and shifted
average. (n²/2) times.

Space Complexity

In-place sorting; No extra memory required except a few variables. So, the
space complexity is constant - O(1)

Working Example
Let us understand this with an example:
list = [12,27,10,35,19,42,44]

Pass1:
We will start by having 2 arrays – Sorted and Unsorted
Un-sorted list
0 1 2 3 4 5 6 7
14 33 27 10 35 19 42 44

Sorted list
0 1 2 3 4 5 6 7

We will start out sorting process from the unsorted list –

Unsorted List: Compare 0 and 1: 14>33 – false
Add Index 0 value - 14 to the Sorted list

Sorted list
 0 1 2 3 4 5 6 7
14

Pass2:
Un-sorted list
0 1 2 3 4 5 6 7
14 33 27 10 35 19 42 44

Sorted list
0 1 2 3 4 5 6 7
14

Unsorted List: Compare 1 and 2: 33>27 – true

Swap both the values
Add Index 1 value - 27 to the Sorted list

Un-sorted list
0 1 2 3 4 5 6 7
14 27 33 10 35 19 42 44

Before Adding 27 –
Compare Index 0 value with 27 : 14>27 : false
Add 27 to Index 1
Sorted list
0 1 2 3 4 5 6 7
14 27

Pass3:
Un-sorted list
0 1 2 3 4 5 6 7
14 27 33 10 35 19 42 44

Sorted list
0 1 2 3 4 5 6 7
14 27

Unsorted List: Compare 2 and 3: 33>10 – true

Swap both the values
Add Index 2 value - 10 to the Sorted list

Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 35 19 42 44

Before Adding 10 –
Compare Index 0 value with 10 : 14>10 : true
Insert 10 at index 0 and push all the other values down by 1 index

Sorted list
0 1 2 3 4 5 6 7
 10 14 27

Pass 4:
Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 35 19 42 44

Sorted list
0 1 2 3 4 5 6 7
10 14 27

Unsorted List: Compare 3 and 4: 33>35 – false

Add Index 3 value - 33 to the Sorted list
Before Adding 33 –
Sorted List: Compare Index 0 value with 33 : 10>33 : false
Sorted List: Compare Index 1 value with 33 : 14>33 : false
Sorted List: Compare Index 2 value with 33 : 27>33 : false
Add 33 at Index 3
Sorted list
0 1 2 3 4 5 6 7
10 14 27 33

Pass5:
Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 35 19 42 44

Sorted list
0 1 2 3 4 5 6 7
10 14 27 33

Unsorted List: Compare 4 and 5: 35>19 – true

Swap both the values
Add Index 4 value - 19 to the Sorted list

Before Adding 19 –
Sorted List: Compare Index 0 value with 19 : 10>19 : false
Sorted List: Compare Index 1 value with 19 : 14>19 : false
Sorted List: Compare Index 2 value with 19 : 27>19 : true
Insert 19 in the index 2 and push all the values by 1 position down

Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 19 35 42 44

Sorted list
 0 1 2 3 4 5 6 7
10 14 19 27 33

Pass 6:
Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 19 35 42 44

Sorted list
0 1 2 3 4 5 6 7
10 14 19 27 33

Unsorted List: Compare 5 and 6: 35>42 – false

Add Index 5 value - 35 to the Sorted list
Before Adding 35 –
Sorted List: Compare Index 0 value with 35 : 10>35 : false
Sorted List: Compare Index 1 value with 35 : 14>35 : false
Sorted List: Compare Index 2 value with 35 : 19>35 : false
Sorted List: Compare Index 3 value with 35 : 27>35 : false
Sorted List: Compare Index 4 value with 35 : 33>35 : false
Add 35 at index position 5
Sorted list
0 1 2 3 4 5 6 7
10 14 19 27 33 35

Pass 7:
Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 19 35 42 44

Unsorted List: Compare 6 and 7: 42>44 – false

Add Index 6 value - 42 to the Sorted list
Before Adding 42 –
Sorted List: Compare Index 0 value with 42 : 10>42 : false
Sorted List: Compare Index 1 value with 42 : 14>42 : false
Sorted List: Compare Index 2 value with 42 : 19>42 : false
Sorted List: Compare Index 3 value with 42 : 27>42 : false
Sorted List: Compare Index 4 value with 42 : 33>42 : false
Sorted List: Compare Index 5 value with 42 : 35>42 : false
Add 42 at index position 6
Sorted list
0 1 2 3 4 5 6 7
10 14 19 27 33 35 42

Pass 8:
Un-sorted list
0 1 2 3 4 5 6 7
14 27 10 33 19 35 42 44

Now only Index 7 is left in the Unsorted list : 44

Ass 44 into the Sorted list
Sorted List: Compare Index 0 value with 44 : 10>44 : false
Sorted List: Compare Index 1 value with 44 : 14>44 : false
Sorted List: Compare Index 2 value with 44 : 19>44 : false
Sorted List: Compare Index 3 value with 44 : 27>44 : false
Sorted List: Compare Index 4 value with 44 : 33>44 : false
Sorted List: Compare Index 5 value with 44 : 35>44 : false
Sorted List: Compare Index 5 value with 44 : 42>44 : false
Add 44 at index position 7
Sorted list
0 1 2 3 4 5 6 7
10 14 19 27 33 35 42 44

Code:
#include <stdio.h>
// Function to perform the Insertion Sort
void insertionSort(int arr[], int n)
{
int i, j, key;

// Outer loop to iterate through each element in the array

for (i = 1; i < n; i++)
{
// Step 1: Take the current element as the 'key'
key = arr[i];
j = i - 1;

// Step 2: Compare 'key' with elements in the sorted sublist

// Move elements of the sorted sublist that are greater than 'key' to one
position ahead
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}

// Step 3: Insert 'key' at the correct position

arr[j + 1] = key;

// Print the array after each iteration (optional for understanding)

printf("Array after iteration %d: ", i);
 for (int k = 0; k < n; k++)
{
printf("%d ", arr[k]);
}
printf("\n");
}
}
// Main Code
int main()
{
int n;

// Input the size of the array

printf("Enter the number of elements: ");
scanf("%d", &n);

// Creating the Array

int arr[n];

// Input the elements of the array

printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}

// Call the insertionSort function

insertionSort(arr, n);

// Output the sorted array

printf("Sorted array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}

return 0;
}

Input:
Enter the number of elements: 10
Enter 10 elements:
56
12
48
79
90
64
37
10
5
29
Output:
Array after iteration 1: 12 56 48 79 90 64 37 10 5 29
Array after iteration 2: 12 48 56 79 90 64 37 10 5 29
Array after iteration 3: 12 48 56 79 90 64 37 10 5 29
Array after iteration 4: 12 48 56 79 90 64 37 10 5 29
Array after iteration 5: 12 48 56 64 79 90 37 10 5 29
Array after iteration 6: 12 37 48 56 64 79 90 10 5 29
Array after iteration 7: 10 12 37 48 56 64 79 90 5 29
Array after iteration 8: 5 10 12 37 48 56 64 79 90 29
Array after iteration 9: 5 10 12 29 37 48 56 64 79 90
Sorted array:
5 10 12 29 37 48 56 64 79 90
-----------------------------------------------------------------------------------