DATA STRUCTURE

Before Mid
Table of Contents
Week 1 ............................................................................................................................................................... 3
Data Structure ................................................................................................................................................ 3
Importance of Data Structure ........................................................................................................................ 3
Real world applications of data structures in software development ........................................................... 4
Week 2 ............................................................................................................................................................... 6
Abstract Data Type (ADT) ............................................................................................................................... 6
Complexity analysis in data structures .......................................................................................................... 7
➢ Asymptotic Notations in Complexity Analysis.................................................................................... 7
➢ How to measure complexity .............................................................................................................. 7
Big O notation .............................................................................................................................................. 10
Week 3 ............................................................................................................................................................. 12
Basic terminology......................................................................................................................................... 12
1. Arrays ................................................................................................................................................... 12
2. Linked Lists ........................................................................................................................................... 13
3. Stacks ................................................................................................................................................... 14
4. Queues ................................................................................................................................................. 14
Week 4 ............................................................................................................................................................. 15
Searching an Unsorted Array ....................................................................................................................... 15
1. Linear Search / Sequential Search / Sentinel Linear Search ............................................................ 15
2. Binary Search / Half-Interval Search / Logarithmic Search / Binary Chop ....................................... 16
Operations on arrays .................................................................................................................................... 18
Week 5 ............................................................................................................................................................. 23
Stack ............................................................................................................................................................. 23
Implementation ........................................................................................................................................... 23
• Array-based Implementation ........................................................................................................... 24
• Linked List-based Implementation ................................................................................................... 27
Week 6 ............................................................................................................................................................. 32
Recursion in Data Structures........................................................................................................................ 32
Divide and Conquer Algorithms ................................................................................................................... 33
Week 7 ............................................................................................................................................................. 34
Sorted linked list, single and doubly linked list ............................................................................................ 34
Types of Linked List ...................................................................................................................................... 35
1. Singly Linked List .............................................................................................................................. 35

1
 2. Doubly Linked List ............................................................................................................................ 40
3. Circular Linked List ........................................................................................................................... 49
Sorted linked list........................................................................................................................................... 57
Sort Linked List using Bubble Sort ............................................................................................................ 57
Sort Linked List using Insertion Sort ......................................................................................................... 58
Sort Linked List using Quick Sort .............................................................................................................. 58
Sort Linked List using Merge Sort............................................................................................................. 58
Week 8 ............................................................................................................................................................. 59
Sorting Algorithm ......................................................................................................................................... 59
 Selection sort ................................................................................................................................... 60
 Insertion Sort ................................................................................................................................... 64
 Merge sort........................................................................................................................................ 67
 Quick Sort ......................................................................................................................................... 71
Comparison Between Sorting Algorithms................................................................................................ 75
The End ............................................................................................................................................................ 76

2
Week 1
Data Structure
“A data structure is a specialized format for organizing, storing, and managing data in
a computer's memory or storage. It defines how data elements are arranged, the
relationships among them, and the operations that can be performed on the data.”

The primary goal of using data structures is to enable efficient access, modification, and processing
of data, optimizing both time and space complexity in software applications e.g. Arrays.

Importance of Data Structure

 Data structures are important because they provide an organized, efficient way to store,
retrieve, and manipulate data, enabling faster and more effective code execution and system
performance.
 They are essential for managing large datasets, building complex algorithms, optimizing
resource usage, and are a fundamental requirement for software development, big data, and
artificial intelligence.
 Choosing the right data structure is crucial for solving problems efficiently, making it a core
concept in computer science and programming.

Key Reasons Data Structures Are Important:

→ Efficiency:
Data structures are designed for efficient operations like searching, insertion, and
deletion, which are critical for processing large amounts of data quickly.

→ Data Organization:

They provide a systematic way to store and organize data, making it easier for
computers to process and manage.

→ Algorithm Design:

Data structures are the foundation for designing efficient algorithms, which are
sequences of instructions that solve specific problems.

→ Resource Management:
Appropriate data structures help optimize memory usage, improving overall system
performance and resource management.

→ Scalability:

They are vital for handling the growing volume of data in modern applications, from
databases to big data frameworks and AI.

→ Code Reusability:

3
 By providing structured ways to format and store data, they allow for the creation of
reusable components that can be accessed and utilized by different parts of a system.

→ Fundamental to Computer Science:

Data structures are a core concept in computer science, forming the basis for
understanding how data is managed and manipulated at a fundamental level.

→ Employability:
Proficiency in data structures is a highly valued skill in the tech industry and is often
tested in job interviews for programming roles.

Real world applications of data structures in software

development
Data structures are fundamental to software development, enabling efficient organization,
storage, and retrieval of data. Their real-world applications are diverse and pervasive:
1. Operating Systems:
• Queues:
Manage process scheduling, handling tasks in a First-In-First-Out (FIFO) manner.
• Stacks:
Support function call management, handling memory allocation for local variables and
return addresses.
• Linked Lists:
Used for dynamic memory allocation and managing file system directories.

2. Database Management Systems (DBMS):

• B-trees and B+ trees:

Efficiently index and organize large datasets, optimizing search and retrieval
operations.

• Hash Tables: Provide fast data access and indexing for key-value pairs.

3. Web Development:

• Arrays and Linked Lists:

Manage dynamic content, user sessions, and caching mechanisms.

• Hash Maps:

Store and retrieve user data, session information, and configurations.

• Trees (e.g., DOM tree):

Represent the structure of web pages, enabling efficient manipulation and

rendering.

4. Artificial Intelligence and Machine Learning:

• Decision Trees:
4
 Used for classification and regression tasks, creating a tree-like model of
decisions.

• Graphs:

Represent relationships in neural networks and knowledge graphs.

• Hash Maps and Tries:

Enhance the efficiency of Natural Language Processing (NLP) tasks like

autocomplete and word embeddings.

5. Search Engines:

• Tries and Hash Tables:

Efficiently index web pages and facilitate rapid searching and auto-completion.

• Graphs:

Represent the interconnectedness of web pages, enabling page ranking

algorithms like PageRank.

6. Computer Graphics and Gaming:

• Arrays:

Store pixel data in images and vertex information in 3D models.

• Trees (e.g., Quadtrees, Octrees):

Optimize spatial partitioning for rendering and collision detection.

7. Networking:

• Graphs and Adjacency Matrices:

Model network topologies and enable routing algorithms to find optimal paths.

8. Compiler Design:

• Symbol Tables (often implemented with Hash Tables or Trees):

Store information about variables, functions, and other program entities during
compilation.

• Abstract Syntax Trees (ASTs):

Represent the hierarchical structure of source code for analysis and

optimization.

5
Week 2
Abstract Data Type (ADT)
“An Abstract Data Type (ADT) is a mathematical model for data types, defined by its
behavior and operations rather than its implementation.”

It specifies what operations can be performed on the data and what their behavior is, but not
how those operations are implemented or how the data is organized in memory.

Key characteristics of ADTs:

• Abstraction:

→ ADTs hide the internal details of data representation and operation implementation from
the user.
→ Users interact with the ADT through a defined interface of operations, without needing to
know the underlying mechanisms.

• Behavioral Definition:

→ The core of an ADT is its behavioral specification.

→ This includes the set of operations that can be performed on the data, the types of
arguments they take, the values they return, and their effects on the ADT's state.
• Implementation Independence:

→ An ADT can be implemented in various ways using different data structures.

→ For example, a Stack ADT can be implemented using an array or a linked list, but its core
operations (push, pop, peek, isEmpty) and their LIFO (Last-In-First-Out) behavior remain
the same.

Examples of ADTs in Data Structures:

• Stack ADT:

Defines operations like push, pop, peek, isEmpty, with LIFO behavior.

• Queue ADT:

Defines operations like enqueue, dequeue, front, isEmpty, with FIFO (First-In-First-Out) behavior.

• List ADT:

Defines operations like add, remove, get, set, size, allowing ordered collections of elements.
• Set ADT:
Defines operations like add, remove, contains, union, intersection, storing unique elements without
a specific order.
Summarizing / Conclusion:

6
In essence, ADTs provide a high-level, conceptual view of data and its manipulation, promoting
modularity, reusability, and easier reasoning about software systems. They focus on the "what" of
data management, leaving the "how" to concrete data structure implementations.

Complexity analysis in data structures

“Complexity analysis in data structures and algorithms is the study of the resources,
primarily time and space, required by an algorithm to solve a given problem as the input size
grows.”

OR

“Complexity analysis is defined as a technique to characterize the time taken by an algorithm

with respect to input size (independent from the machine, language and compiler). It is used
for evaluating the variations of execution time on different algorithms.”

This analysis helps in understanding and comparing the efficiency of different algorithms.

➢ Asymptotic Notations in Complexity Analysis

Common notations used to express time complexity include:

• Big O Notation (O):

Represents the upper bound or worst-case scenario of an algorithm's running time. It describes
the maximum time an algorithm will take for a given input size.

• Big Omega Notation (Ω):

Represents the lower bound or best-case scenario. It describes the minimum time an algorithm
will take.

• Big Theta Notation (Θ):

Represents both the upper and lower bounds, indicating that the algorithm's running time is
tightly bound within a certain range.

➢ How to measure complexity

1. Time Complexity:

“Time complexity measures how the execution time of an algorithm grows with
the input size.”

→ It quantifies the number of elementary operations an algorithm performs.

→ How is Time complexity computed?
• To estimate the time complexity, we need to consider the cost of each fundamental
instruction and the number of times the instruction is executed.
o If we have statements with basic operations like comparisons, return
statements, assignments, and reading a variable. We can assume they take constant
time each O (1).

7
 Statement 1: int a=5; // reading a variable

statement 2; if(a==5) return true; // return statement

statement 3; int x= 4>5 ? 1:0; // comparison

statement 4; bool flag=true; // Assignment

• This is the result of calculating the overall time complexity.

total time = time(statement1) + time(statement2) + ... time (statementN)

• Assuming that n is the size of the input, let's use T(n) to represent the overall
time and t to represent the amount of time that a statement or collection of
statements takes to execute.

T(n) = t(statement1) + t(statement2) + ... + t(statementN);

• Overall, T(n)= O(1), which means constant complexity.

o For any loop, we find out the runtime of the block inside them and multiply it by the
number of times the program will repeat the loop.

for (int i = 0; i < n; i++) {

cout << "GeeksForGeeks" << endl;

→ Examples of Time Complexities:

• O(1) - Constant Time:

Operations that take a fixed amount of time regardless of input size (e.g., accessing an
element in an array by index).

• O(log n) - Logarithmic Time:

Operations where the time required grows logarithmically with the input size (e.g., binary
search).

• O(n) - Linear Time:

Operations where the time required grows linearly with the input size (e.g., traversing a linked
list).

• O(n log n) - Linearithmic Time:

Often seen in efficient sorting algorithms (e.g., Merge Sort, Quick Sort).

• O(n²) - Quadratic Time:

Operations where the time required grows quadratically with the input size (e.g., Bubble Sort,
insertion sort in the worst case).
• O(2^n) - Exponential Time:

Operations where the time required grows exponentially with the input size (e.g., some
recursive algorithms without memorization).

8
2. Space Complexity:

“Space complexity measures the amount of memory an algorithm requires to

execute, also as a function of the input size.”

→ This includes both the fixed part (memory for constants, simple variables) and the
variable part (memory for dynamic data structures, recursion stack, temporary
variables).
→ How is space complexity computed?
• The space Complexity of an algorithm is the total space taken by the algorithm with
respect to the input size. Space complexity includes both Auxiliary space and
space used by input.
• Space complexity is a parallel concept to time complexity. If we need to create an
array of size n, this will require O(n) space. If we create a two-dimensional array
of size n*n, this will require O(n2) space.
• In recursive calls stack space also counts.
→ Example:
int add (int n){

if (n <= 0)}

return 0;

}
return n + add (n-1);

Here each call add a level to the stack:

1. add(4)

2. -> add(3)

3. -> add(2)
4. -> add(1)

5. -> add(0)

Each of these calls is added to call stack and takes up actual memory.
So it takes O(n) space.

However, just because you have n calls total doesn’t mean it takes O(n) space.

3. Auxiliary Space:

“The temporary space needed for the use of an algorithm is referred to as auxiliary
space.”

→ Like temporary arrays, pointers, etc.

→ It is preferable to make use of Auxiliary Space when comparing things like sorting
algorithms.

9
 → For example, sorting algorithms take O(n) space, as there is an input array to sort.
but auxiliary space is O(1) in that case.

Importance of Complexity Analysis:

• Algorithm Comparison:

Allows for objective comparison of different algorithms for the same problem.

• Performance Prediction:

Helps predict how an algorithm will perform with larger inputs.

• Optimization:

Identifies bottlenecks and areas for optimization within an algorithm or data structure.
• Resource Management:

Aids in making informed decisions about resource allocation for software development.

Big O notation
“Big O notation is a powerful tool used in computer science to describe the time
complexity or space complexity of algorithms.”

Big O notation, in the context of data structures and algorithms, is a mathematical notation used to
describe the worst-case time or space complexity of an algorithm as the input size grows.
It provides an upper bound on the growth rate of an algorithm's resource consumption.

Key Characteristics:
Here's a breakdown of its key aspects:

• Upper Bound:

Big O notation focuses on the maximum time or space an algorithm will require. It represents a limit
that the algorithm's performance will not exceed.

• Asymptotic Analysis:

It describes the algorithm's behavior for very large input sizes, ignoring constant factors and lower-
order terms that become insignificant as 'n' grows.

• Growth Rate:

Big O describes how the time or space requirements scale with increasing input size. It
categorizes algorithms based on their fundamental growth patterns, such as constant,
logarithmic, linear, quadratic, or exponential.
It categorizes algorithms based on their growth rate, such as constant (O(1)), logarithmic
(O(log n)), linear (O(n)), quadratic (O(n²)), or exponential (O(2^n)).

10
• Efficiency Comparison:

It allows for a standardized way to compare the efficiency of different algorithms, helping to
determine which algorithm is more suitable for a given problem, especially with large datasets.

• Worst-Case Scenario:

Big O focuses on the maximum amount of time or space an algorithm will take to complete,
assuming the most unfavorable input. This is important for understanding how an algorithm will
perform under stress.

• Input Size (n):

The complexity is expressed as a function of 'n', which represents the size of the input data. For
example, in an array, 'n' might be the number of elements.

• Machine Independence:

Big O notation abstracts away machine-specific details (like processor speed or memory access
times), focusing on the number of operations or memory units required.
Summarizing / Conclusion:

In essence, Big O notation provides a standardized way to compare and analyze the
efficiency of different data structures and algorithms, allowing developers to choose the most
appropriate solution for a given problem based on its performance characteristics.

11
Week 3
Basic terminology
1. Arrays
• Definition: A linear data structure that stores a collection of elements of the same data type
in contiguous memory locations.

• Element: An individual item stored within the array.

• Index / position / Subscript: A numerical position of an element within the array, typically
starting from 0.

• Size / Length / no. of elements: The total number of elements an array can hold.

• Types of arrays

→ Static Arrays: These have a fixed size that is determined at compile-time. They are
generally stored on the stack.

→ Dynamic Arrays: These overcome the fixed-size limitation by automatically resizing

when elements are added or removed. They are typically implemented using a static array
underneath and are allocated on the heap.
• Operations on Array:
• Advantages:

→ Fast Access: Because elements are stored in adjacent memory locations, you can access
any element in constant time, 𝑂(1), using its index.

→ Memory Efficient: There is very little overhead since no extra memory is needed for links or
pointers between elements.

→ Cache Friendly: Contiguous memory access is more efficient for the CPU cache, which can
lead to better performance for large datasets.

→ Simple Iteration: Traversing all elements is straightforward using a simple loop.

• Disadvantages:
→ Fixed Size: The most significant drawback is its static nature. If you need to add more
elements than the array can hold, you must create a new, larger array and copy all the
elements over, which is an inefficient process.
→ Inefficient Insertions/Deletions: Adding or removing an element in the middle of an array
requires shifting all subsequent elements, which is a slow operation.

→ Wasted Memory: If an array is allocated with more space than is ultimately needed, the
unused memory is wasted.
12
 → Homogeneous: The restriction to a single data type limits its flexibility.

• Common applications:
→ Storing data: Arrays are used to store collections of data like a list of exam scores, inventory
items, or phone contacts.

→ Implementing other data structures: Stacks, queues, and hash tables can all be built using
an array as their foundation.

→ Matrices: Multi-dimensional arrays are used to represent matrices in mathematics, image

processing, and game development.

→ CPU scheduling: Algorithms for managing CPU processes often utilize arrays.

→ Sorting and searching: Most sorting algorithms, such as quicksort or merge sort, and
searching algorithms like binary search, operate on arrays.
2. Linked Lists
• Definition: A linear data structure where elements are stored in nodes, and each node
contains data and a reference (or pointer) to the next node in the sequence.
• Node: The fundamental building block of a linked list, comprising data and a pointer to the
next node.
• Head: A pointer to the first node in the linked list.

• Tail: A pointer to the last node in the linked list.

• Null/None: A special value in the pointer of the last node, indicating the end of the list.

• Operations on the Linked List:

→ Traversal:

 Starting from the head node, a temporary pointer iterates through the list, moving from
one node to the next using the next pointer until the end of the list (where
the next pointer is nullptr) is reached.

 During traversal, the data within each node can be accessed or processed.

→ Insertion:

 At the beginning: A new node is created, its next pointer is set to the current head,
and the head pointer is updated to point to the new node.

 At the end: A new node is created, and the next pointer of the current last node is
updated to point to the new node. If the list is empty, the new node becomes the head.

 At a specific position: A new node is created, and the list is traversed to find the
node before the desired insertion point. The new node's next pointer is set to
the next of the preceding node, and the preceding node's next pointer is updated to
point to the new node.

→ Deletion:

13
  From the beginning: The head pointer is moved to the next node, and the original
head node is deallocated.

 From the end: The list is traversed to find the second-to-last node. The next pointer
of the second-to-last node is set to nullptr, and the last node is deallocated.

 Of a specific node: The list is traversed to find the node to be deleted and its
preceding node. The next pointer of the preceding node is updated to bypass the
deleted node, and the deleted node is deallocated.

→ Search:

 The list is traversed from the head, comparing the data in each node with the target
value.

 If a match is found, the search stops, and the node (or its data) is returned. If the end
of the list is reached without a match, the element is not found.

→ Sorting:

 Various sorting algorithms can be applied to linked lists, such as bubble sort, insertion
sort, or merge sort. These algorithms involve rearranging the nodes or their data
based on a defined order.

3. Stacks
• Definition: A linear data structure that follows the Last-In, First-Out (LIFO) principle, meaning
the last element added is the first one to be removed.

• Operations on the Stack:

→ Push: The operation of adding an element to the top of the stack.

→ Pop: The operation of removing and returning the top element from the stack.

→ Peek/Top: An operation to view the top element of the stack without removing it.

→ Empty: A state where the stack contains no elements.

4. Queues
• Definition: A linear data structure that follows the First-In, First-Out (FIFO) principle, meaning
the first element added is the first one to be removed.
• Operation on Queue:

→ Enqueue: The operation of adding an element to the rear (or tail) of the queue.

→ Dequeue: The operation of removing and returning the element from the front (or head)
of the queue.

→ Front/Peek: An operation to view the element at the front of the queue without removing
it.
→ Rear/Tail: The position where new elements are added to the queue.

→ Empty: A state where the queue contains no elements.

14
Week 4
Searching an Unsorted Array
Searching for an element in an unsorted array in C++ is typically done using a linear search
algorithm.

This method involves iterating through each element of the array sequentially until the target
element is found or the end of the array is reached.

1. Linear Search / Sequential Search / Sentinel Linear Search

Linear search is the appropriate algorithm for searching an unsorted array in C++. This
algorithm sequentially checks each element in the array until the target element is found or the end
of the array is reached.

Here's how linear search works for an unsorted array in C++:

• Initialization: Start from the first element of the array (index 0).

• Comparison: Compare the current element with the target value you are searching for.

• Match Found: If the current element matches the target value, the search is successful, and
the index of the current element is returned.

• No Match: If the current element does not match the target value, move to the next element
in the array.

• Iteration: Repeat steps 2-4 until either the target element is found or all elements in the array
have been checked.

• Element Not Found: If the end of the array is reached without finding the target element, it
means the element is not present in the array, and a suitable indicator (e.g., -1) is returned.

Program (Linear Search):

#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 2, 8, 1, 9, 4}; // Unsorted array
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array
int i, target, loc = -1;
cout << "Elements in the array: ";
for ( i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;

15
 cout << "Number to find: " ;
cin >> target;

for (i = 0; i < n; ++i) {

if (target == arr[i]) {
loc = i;
break; // Exit the loop immediately
}
}

if (loc == -1) {
cout << "Element not found in the list." <<endl;
} else {
cout << "Element found at index " << loc << " in the list." <<endl;
}

return 0;
}

2. Binary Search / Half-Interval Search / Logarithmic Search / Binary Chop

Binary search is an efficient algorithm for finding a target value within a sorted array. It works by
repeatedly dividing the search interval in half. The process is as follows:

• Initialize:

Define a low pointer at the beginning of the array and a high pointer at the end.

• Find Midpoint:
Calculate the mid index, typically as low + (high - low) / 2 to prevent potential integer overflow.
• Compare:

→ If the element at mid is equal to the target, the target is found, and its index is returned.

→ If the element at mid is less than the target, the target must be in the right half of the current
search space. Update low = mid + 1.

→ If the element at mid is greater than the target, the target must be in the left half of the current
search space. Update high = mid - 1.

• Repeat:
Continue steps 2 and 3 until the target is found or low becomes greater than high, indicating the
target is not present in the array.

Program:

16
#include <iostream>
using namespace std;
int main() {
// The array must be sorted for binary search to work
int arr[] = {2, 5, 9, 12, 17, 37, 86};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array
int target;

// Prompt user for the target element to search

cout << "Array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << "\nEnter number to search: ";
cin >> target;

int low = 0;
int high = n - 1;
int result = -1;

// Perform binary search

while (low <= high) {
int mid = low + (high - low) / 2; // Prevent potential overflow

// Check if target is present at mid

if (arr[mid] == target) {
result = mid;
break;
}
// If target is greater, search the right half
else if (arr[mid] < target) {
low = mid + 1;
}
// If target is smaller, search the left half
else {
high = mid - 1;
}
}

// Output the result

17
 if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found in the array." << endl;
}
return 0;
}
Summarizing / Conclusion:

Binary search is an efficient algorithm for finding an item within a sorted array. It works by repeatedly
dividing the search interval in half. If the value of the search key is less than the item in the middle
of the interval, the algorithm narrows the interval to the lower half. Otherwise, it narrows it to the
upper half. This process continues until the value is found or the interval is empty.

Operations on arrays
The following operations can be done on the Array:

→ Traversal:
Traversal is the process of visiting and accessing each element of an array exactly
once. It is typically done using a loop that iterates from the first element to the last.

→ Insertion:
Insertion adds a new element to the array. The time complexity of this operation varies
depending on the insertion point.
 Insertion at the end: If there is space, this is very fast, taking 𝑂(1)constant time.
 Insertion at the beginning or middle: Requires shifting all subsequent elements to make
space, which is an 𝑂(𝑛) operation.
 Example: Inserting 25 at index 2 in an array [10, 20, 30, 40].

o Shift 30 to index 3.
o Shift 40 to index 4.
o Place 25 at index 2.
o Resulting array: [10, 20, 25, 30, 40].

→ Deletion:
Deletion removes an element from the array. The performance is dependent on the
position of the element being removed.

 Deletion from the end: A constant-time 𝑂(1) operation, as no other elements need to
be moved.
 Deletion from the beginning or middle: Requires shifting all subsequent elements
to fill the gap, making it an 𝑂(𝑛) operation.
 Example: Deleting the element at index 1 (20) from [10, 20, 30, 40].
18
 o Shift 30 to index 1.
o Shift 40 to index 2.
o The array becomes [10, 30, 40].

→ Searching:
Searching involves finding the location of a specific element within the array.

 Linear Search: Checks each element sequentially until a match is found. It works on
unsorted arrays and has a time complexity of 𝑂(𝑛) in the worst case.
 Binary Search: An optimized search method that only works on a sorted array. It repeatedly
divides the search interval in half and has a much faster time complexity of 𝑂(log𝑛).

→ Update
Updating an element involves changing the value at a specific index. This is a very
efficient operation.
 Time Complexity:
▪ 𝑂(1), because you can access the element directly using its index and overwrite
its value.
 Example: Updating the element at index 2 in array [10, 20, 30, 40] to 35.
1. Access arr[2].
2. Assign the new value: arr[2] = 35.
3. Resulting array: [10, 20, 35, 40].

Program(Operations):
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

// Function prototypes
void displayArray(const int arr[], int size);
void insertElement(int arr[], int &size, int element, int position);
void deleteElement(int arr[], int &size, int position);
int linearSearch(const int arr[], int size, int target);
void updateElement(int arr[], int size, int position, int newValue);

int main() {
int arr[MAX_SIZE] = {10, 20, 30, 40, 50};
int size = 5;
int choice, element, position, target, newValue;
int searchResult;
do {
cout << "\n--- Array Operations Menu ---" << endl;
cout << "1. Display Array" << endl;
cout << "2. Insert Element" << endl;
cout << "3. Delete Element" << endl;
cout << "4. Search Element" << endl;

19
 cout << "5. Update Element" << endl;
cout << "6. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
displayArray(arr, size);
break;
case 2:
cout << "Enter element to insert: ";
cin >> element;
cout << "Enter position to insert at (0-indexed): ";
cin >> position;
insertElement(arr, size, element, position);
break;
case 3:
cout << "Enter position to delete (0-indexed): ";
cin >> position;
deleteElement(arr, size, position);
break;
case 4:
cout << "Enter element to search: ";
cin >> target;
searchResult = linearSearch(arr, size, target);
if (searchResult != -1) {
cout << "Element " << target << " found at index " << searchResult << "."
<< endl;
} else {
cout << "Element " << target << " not found in the array." << endl;
}
break;
case 5:
cout << "Enter position to update (0-indexed): ";
cin >> position;
cout << "Enter new value: ";
cin >> newValue;
updateElement(arr, size, position, newValue);
break;
case 6:
cout << "Exiting program. Goodbye!" << endl;
break;
default:
cout << "Invalid choice. Please try again." << endl;
}
} while (choice != 6);

20
 return 0;
}

// Displays all elements of the array

void displayArray(const int arr[], int size) {
if (size == 0) {
cout << "Array is empty." << endl;
return;
}
cout << "Array elements: ";
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}

// Inserts an element at a specific position, shifting other elements

void insertElement(int arr[], int &size, int element, int position) {
if (size >= MAX_SIZE) {
cout << "Error: Array is full." << endl;
return;
}
if (position < 0 || position > size) {
cout << "Error: Invalid position." << endl;
return;
}
// Shift elements to the right to make space
for (int i = size; i > position; --i) {
arr[i] = arr[i - 1];
}
arr[position] = element;
size++;
cout << "Element " << element << " inserted at position " << position << "." << endl;
}

// Deletes an element at a specific position, shifting other elements

void deleteElement(int arr[], int &size, int position) {
if (size == 0) {
cout << "Error: Array is empty." << endl;
return;
}
if (position < 0 || position >= size) {
cout << "Error: Invalid position." << endl;
return;
}

// Shift elements to the left to fill the gap

21
 for (int i = position; i < size - 1; ++i) {
arr[i] = arr[i + 1];
}
size--;
cout << "Element at position " << position << " deleted." << endl;
}

// Searches for an element using linear search

int linearSearch(const int arr[], int size, int target) {
for (int i = 0; i < size; ++i) {
if (arr[i] == target) {
return i; // Return the index if found
}
}
return -1; // Return -1 if not found
}

// Updates the value of an element at a specific position

void updateElement(int arr[], int size, int position, int newValue) {
if (position < 0 || position >= size) {
cout << "Error: Invalid position." << endl;
return;
}
arr[position] = newValue;
cout << "Element at position " << position << " updated to " << newValue << "." <<
endl;
}

22
Week 5
Stack
A stack is a linear data structure that adheres to the Last In, First Out (LIFO) principle. This means
that the last element added to the stack is the first one to be removed. Imagine a stack of plates:
you always add new plates to the top, and when you take a plate, you take the one from the top,
which was the last one placed.

Key Characteristics:
• LIFO (Last In, First Out): The fundamental principle governing element access.

• Single-ended Operations: All insertions and deletions occur at one end, referred to as the
"top" of the stack.

Basic Operations:
• Push: Adds a new element to the top of the stack.

• Pop: Removes and returns the element from the top of the stack.

• Peek (or Top): Returns the top element without removing it.

• isEmpty: Checks if the stack contains any elements.

• isFull: Checks if the stack has reached its maximum capacity (relevant for array-based
implementations).

Implementation
Stacks can be implemented using various underlying data structures, such as arrays or linked lists.

23
 • Array-based Implementation
Uses a fixed-size array to store elements and a pointer (often called "top") to keep track of the top
element's index.

Example Program:

#include <iostream>
using namespace std;

#define MAX 100 // Maximum size of stack

class Stack {
private:
int arr[MAX];
int top;

public:
Stack() {
top = -1; // Stack is initially empty
}

// Check if stack is full

bool isFull() {
return (top == MAX - 1);
}

// Check if stack is empty

bool isEmpty() {
return (top == -1);
}

// Push operation
void push(int value) {
if (isFull()) {
cout << "Stack Overflow! Cannot push " << value << endl;
} else {

24
 top++;
arr[top] = value;
cout << value << " pushed into the stack.\n";
}
}

// Pop operation
void pop() {
if (isEmpty()) {
cout << "Stack Underflow! Nothing to pop.\n";
} else {
cout << arr[top] << " popped from the stack.\n";
top--;
}
}

// Peek / Top operation

void peek() {
if (isEmpty()) {
cout << "Stack is empty!\n";
} else {
cout << "Top element: " << arr[top] << endl;
}
}

// Display all stack elements

void display() {
if (isEmpty()) {
cout << "Stack is empty!\n";
} else {
cout << "Stack elements (top to bottom): ";
for (int i = top; i >= 0; i--)
cout << arr[i] << " ";
cout << endl;

25
 }
}
};

// Main Function
int main() {
Stack s;
int choice, value;

do {
cout << "\n--- Stack Menu ---\n";
cout << "1. Push\n";
cout << "2. Pop\n";
cout << "3. Peek (Top Element)\n";
cout << "4. Check if Empty\n";
cout << "5. Check if Full\n";
cout << "6. Display Stack\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to push: ";
cin >> value;
[Link](value);
break;

case 2:
[Link]();
break;

case 3:
[Link]();

26
 break;

case 4:
cout << ([Link]() ? "Stack is empty.\n" : "Stack is not empty.\n");
break;

case 5:
cout << ([Link]() ? "Stack is full.\n" : "Stack is not full.\n");
break;

case 6:
[Link]();
break;

case 0:
cout << "Exiting program...\n";
break;

default:
cout << "Invalid choice! Try again.\n";
}
} while (choice != 0);

return 0;
}

• Linked List-based Implementation

Uses nodes to store elements, where each node points to the next, and a head pointer indicates
the top of the stack.

#include <iostream>
using namespace std;

// Node structure for linked list

struct Node {
int data;
Node* next;
27
};

// Stack class using linked list

class Stack {
private:
Node* top; // pointer to the top element

public:
Stack() {
top = NULL;
}

// Push operation
void push(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = top; // new node points to old top
top = newNode; // update top
cout << value << " pushed into the stack.\n";
}

// Pop operation
void pop() {
if (isEmpty()) {
cout << "Stack Underflow! Nothing to pop.\n";
return;
}
Node* temp = top;
cout << top->data << " popped from the stack.\n";
top = top->next;
delete temp;
}

// Peek (Top element)

28
void peek() {
if (isEmpty()) {
cout << "Stack is empty!\n";
} else {
cout << "Top element: " << top->data << endl;
}
}

// Check if stack is empty

bool isEmpty() {
return (top == NULL);
}

// Display all stack elements

void display() {
if (isEmpty()) {
cout << "Stack is empty!\n";
return;
}
cout << "Stack elements (top to bottom): ";
Node* temp = top;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

// Destructor to free memory

~Stack() {
while (!isEmpty()) {
pop();
}
}

29
};

// Main Function
int main() {
Stack s;
int choice, value;

do {
cout << "\n--- Stack Menu (Linked List Implementation) ---\n";
cout << "1. Push\n";
cout << "2. Pop\n";
cout << "3. Peek (Top Element)\n";
cout << "4. Check if Empty\n";
cout << "5. Display Stack\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to push: ";
cin >> value;
[Link](value);
break;

case 2:
[Link]();
break;

case 3:
[Link]();
break;

case 4:

30
 cout << ([Link]() ? "Stack is empty.\n" : "Stack is not empty.\n");
break;

case 5:
[Link]();
break;

case 0:
cout << "Exiting program...\n";
break;

default:
cout << "Invalid choice! Try again.\n";
}
} while (choice != 0);

return 0;
}
Applications:
Stacks are widely used in computer science for various tasks, including:

• Function Call Management:

Compilers use stacks to manage function calls and local variables during program execution.

• Expression Evaluation:
Stacks are crucial for converting infix expressions to postfix/prefix and evaluating them.

• Undo/Redo Functionality:

Many applications use stacks to store changes, allowing users to undo or redo actions.

• Browser History:

Web browsers often use a stack to manage visited pages, enabling back and forward navigation.

• Backtracking Algorithms:

Stacks are used in algorithms like maze solving or searching file directories, where exploring
different paths and backtracking is necessary.

31
Week 6
Recursion in Data Structures
“Recursion is a programming technique where a function calls itself to solve a
problem.”

It is essential for implementing many algorithms, especially those following the "divide and conquer"
paradigm.

Key Components of a Recursive Function:

• Base Case:

A condition that stops the recursion, preventing an infinite loop. It defines the simplest version of the
problem that can be solved directly.
• Recursive Step:

The part of the function that calls itself with a modified input, moving closer to the base case.

Example Program:
The factorial of a number n is n * (n-1) * ... * 1. The recursive function handles this by:

• Base Case: If n is 0 or 1, the factorial is 1.

• Recursive Case: For n > 1, the function returns n * factorial(n-1).
#include <iostream>
using namespace std;

int factorial(int n) {
if (n == 0) { // Base Case
return 1;
} else { // Recursive Step
return n * factorial(n - 1);
}
}
int main() {
int num = 5;
cout << "Factorial of " << num << " is " << factorial(num) << endl;
return 0;
}

32
Divide and Conquer Algorithms
Divide and Conquer is a powerful algorithmic design paradigm that naturally lends itself to
recursive implementations. It involves three steps:
• Divide: Break the problem into smaller subproblems of the same type.

• Conquer: Solve the subproblems recursively. If a subproblem is small enough, solve it

directly (this forms the base case).
• Combine: Combine the solutions of the subproblems to obtain the solution for the original
problem.

Examples of Divide and Conquer Algorithms:

• Merge Sort: Divides an array into two halves, recursively sorts them, and then merges the
sorted halves.

• Quick Sort: Partitions an array around a pivot element and recursively sorts the sub-arrays.
• Binary Search: Divides the search space in half at each step.

Analyzing Recursive Algorithms

Analyzing the time complexity of recursive algorithms, particularly those following the divide and
conquer approach, often involves using recurrence relations. These relations express the time
complexity of a problem in terms of the time complexity of its subproblems.

Master Theorem:
A common tool for solving recurrence relations of the form

T(n) = aT(n/b) + f(n),

where:

• n is the size of the input.

• a is the number of subproblems.

• n/b is the size of each subproblem.

• f(n) is the cost of the work done outside the recursive calls (dividing and combining).

Recursion Tree Method:

A visual method to analyze recursive algorithms by drawing a tree where each node
represents the cost of a subproblem. The total cost is the sum of costs at each level of the tree.
Example: Merge Sort Analysis

The recurrence relation for Merge Sort is T(n) = 2T(n/2) + O(n). Using the Master Theorem, this
resolves to O(n log n).

33
Week 7
Sorted linked list, single and doubly linked list
Linked list:
• Definition: A linear data structure where elements are stored in nodes, and each node
contains data and a reference (or pointer) to the next node in the sequence.

• Node: The fundamental building block of a linked list, comprising data and a pointer to the
next node.

• Head: A pointer to the first node in the linked list.

• Tail: A pointer to the last node in the linked list.

• Null/None: A special value in the pointer of the last node, indicating the end of the list.

• Operations on the Linked List:

→ Traversal

→ Insertion

→ Deletion

→ Search

→ Sorting

• Characteristics:
 Data Structure: Non-contiguous
 Memory Allocation: Typically allocated one by one to individual elements

 Insertion/Deletion: Efficient

 Access: Sequential
34
Types of Linked List
1. Singly Linked List
A singly linked list is a linear data structure composed of a sequence of connected
nodes. Each node in a singly linked list consists of two main parts:

 Data Field: This part stores the actual data or value associated with that node.
 Next Link (or Pointer): This part stores the memory address (or reference) of the next
node in the sequence. The last node's next link typically points to NULL or None,
signifying the end of the list.

Key Characteristics:
➢ One-Way Traversal:

You can only traverse a singly linked list in one direction, from the beginning (head) to the
end, by following the next pointers.

➢ Head Node:
A special pointer, often called head, points to the first node of the list. If the list is
empty, head will be NULL.

➢ Dynamic Size:
Unlike arrays, linked lists do not require contiguous memory allocation and can grow or shrink
dynamically as elements are added or removed.
➢ Non-Contiguous Memory:

Nodes in a linked list are not necessarily stored in adjacent memory locations. Their
connection is established through the pointers.

Basic Operations:
Common operations on a singly linked list include:

► Insertion: Adding a new node at the beginning, end, or a specific position in the list.

► Deletion: Removing a node from the beginning, end, or a specific position.

► Traversal: Iterating through the list to access or process the data in each node.

► Search: Finding a node containing a specific data value.

Advantages:
→ Dynamic size, allowing for flexible memory usage (no fixed limit like arrays).

→ Efficient insertion and deletion at beginning and end. We also have insertion at the
middle efficient if we have reference or pointer to the node after which we need to
insert. (O(1) time complexity).

→ Can implement complex data structures like stack, queue, graph.

Disadvantages:
35
 → Accessing an element at a specific index requires traversing from the beginning,
resulting in O(N) time complexity.

→ Traversal is only possible in one direction.

→ Extra memory required for storing pointers.

→ No direct/random access (need traversal).

→ Cache unfriendly (not stored in contiguous memory).

Example program:
#include <iostream>
using namespace std;

// Node structure
class Node {
public:
int data;
Node* next;

//CONSTRUCTOR
Node(int val) {
data = val;
next = NULL;
}
};

// Linked List class

class SinglyLinkedList {
private:
Node* head;

public:
//Constructor
SinglyLinkedList() {
head = NULL;
}

36
// Insert node at the end
void insert(int val) {
Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
return;
}

Node* temp = head;

while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

// Delete node by value

void deleteNode(int val) {
if (head == NULL) {
cout << "List is empty!\n";
return;
}

if (head->data == val) {
Node* toDelete = head;
head = head->next;
delete toDelete;
cout << "Node deleted successfully.\n";
return;
}

Node* temp = head;

while (temp->next != NULL && temp->next->data != val) {
temp = temp->next;
}

37
 if (temp->next == NULL) {
cout << "Value not found!\n";
return;
}

Node* toDelete = temp->next;

temp->next = temp->next->next;
delete toDelete;
cout << "Node deleted successfully.\n";
}

// Search a value
void search(int val) {
Node* temp = head;
int pos = 1;
while (temp != NULL) {
if (temp->data == val) {
cout << "Value found at position " << pos << endl;
return;
}
temp = temp->next;
pos++;
}
cout << "Value not found in the list!\n";
}

// Display all nodes

void display() {
if (head == NULL) {
cout << "List is empty!\n";
return;
}

38
 Node* temp = head;
cout << "Linked List: ";
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL\n";
}
};

// Main function
int main() {
SinglyLinkedList list;
int choice, value;

do {
cout << "\n--- Singly Linked List Menu ---\n";
cout << "1. Insert\n";
cout << "2. Delete\n";
cout << "3. Search\n";
cout << "4. Display\n";
cout << "5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
[Link](value);
break;
case 2:
cout << "Enter value to delete: ";
cin >> value;

39
 [Link](value);
break;
case 3:
cout << "Enter value to search: ";
cin >> value;
[Link](value);
break;
case 4:
[Link]();
break;
case 5:
cout << "Exiting program...\n";
break;
default:
cout << "Invalid choice!\n";
}

} while (choice != 5);

return 0;
}

2. Doubly Linked List

A doubly linked list is a type of linked data structure where each node contains three primary
components:
▪ Data: The actual information or value stored within the node.
▪ Next Pointer: A reference or pointer to the subsequent node in the sequence.
▪ Previous Pointer: A reference or pointer to the preceding node in the sequence.
Key Characteristics:
→ Bidirectional Traversal:
Unlike a singly linked list, which only allows traversal in one direction (forward), a
doubly linked list enables movement both forward (using the next pointer) and backward
(using the previous pointer) through the list.
→ Node Structure:
Each node in a doubly linked list is typically represented as an object or struct containing
the data and the two pointers.
→ Head and Tail:

40
 The list is managed by a head pointer, which points to the first node, and often
a tail pointer, which points to the last node.
→ Terminators:
The previous pointer of the first node and the next pointer of the last node typically point
to null or a sentinel node to mark the list's boundaries.

Basic Operations:
Common operations on a doubly linked list include:

► Insertion: Adding a new node at the beginning, end, or a specific position in the list.

► Deletion: Removing a node from the beginning, end, or a specific position.

► Traversal: Iterating through the list to access or process the data in each node.

► Search: Finding a node containing a specific data value.

Advantages:
→ Efficient Backward Traversal:
Allows easy navigation to previous elements without starting from the head.
→ Simplified Deletion:
Deleting a node is generally more straightforward as the previous node's next pointer
can be easily updated using the deleted node's previous pointer.
→ Efficient Insertion/Deletion in the Middle:
Operations in the middle of the list can be more efficient compared to singly linked
lists, as finding the previous node is direct.

Disadvantages:
→ Increased Memory Usage:
Each node requires extra memory to store the previous pointer compared to a singly
linked list.
→ More Complex Operations:
Insertion and deletion operations are slightly more complex as they involve updating
two pointers (next and previous) instead of just one.

Example Program:
#include <iostream>
using namespace std;

// Node structure
struct Node {
int data;
Node* prev;
Node* next;
};

41
// Doubly Linked List Class
class DoublyLinkedList {
private:
Node* head;

public:
DoublyLinkedList() {
head = NULL;
}

// Insert at Beginning
void insertAtBeginning(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->prev = NULL;
newNode->next = head;

if (head != NULL)
head->prev = newNode;

head = newNode;
cout << "Inserted " << value << " at beginning.\n";
}

// Insert at End
void insertAtEnd(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = NULL;

if (head == NULL) {
newNode->prev = NULL;
head = newNode;

42
 } else {
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
cout << "Inserted " << value << " at end.\n";
}

// Delete from Beginning

void deleteFromBeginning() {
if (head == NULL) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
head = head->next;
if (head != NULL)
head->prev = NULL;
cout << "Deleted " << temp->data << " from beginning.\n";
delete temp;
}

// Delete from End

void deleteFromEnd() {
if (head == NULL) {
cout << "List is empty!\n";
return;
}

Node* temp = head;

if (temp->next == NULL) { // Only one node
cout << "Deleted " << temp->data << " from end.\n";

43
 delete temp;
head = NULL;
return;
}

while (temp->next != NULL)

temp = temp->next;

cout << "Deleted " << temp->data << " from end.\n";
temp->prev->next = NULL;
delete temp;
}

// ? Delete by Value
void deleteByValue(int value) {
if (head == NULL) {
cout << "List is empty!\n";
return;
}

Node* temp = head;

// Case 1: Value is in the first node

if (head->data == value) {
head = head->next;
if (head != NULL)
head->prev = NULL;
cout << "Deleted node with value " << value << ".\n";
delete temp;
return;
}

// Traverse to find value

while (temp != NULL && temp->data != value)

44
 temp = temp->next;

if (temp == NULL) {
cout << "Value " << value << " not found in the list.\n";
return;
}

// Adjust links
if (temp->next != NULL)
temp->next->prev = temp->prev;
if (temp->prev != NULL)
temp->prev->next = temp->next;

cout << "Deleted node with value " << value << ".\n";
delete temp;
}

// Traverse Forward
void traverseForward() {
if (head == NULL) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
cout << "Traversing forward: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

// Traverse Backward
void traverseBackward() {

45
 if (head == NULL) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;

cout << "Traversing backward: ";

while (temp != NULL) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}

// Search by Value
void search(int value) {
if (head == NULL) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
int pos = 1;
bool found = false;

while (temp != NULL) {

if (temp->data == value) {
cout << "Value " << value << " found at position " << pos << ".\n";
found = true;
}
temp = temp->next;
pos++;
}

46
 if (!found)
cout << "Value " << value << " not found in the list.\n";
}
};

// Main Function
int main() {
DoublyLinkedList dll;
int choice, value;

do {
cout << "\n--- Doubly Linked List Menu ---\n";
cout << "1. Insert at Beginning\n";
cout << "2. Insert at End\n";
cout << "3. Delete from Beginning\n";
cout << "4. Delete from End\n";
cout << "5. Delete by Value\n";
cout << "6. Traverse Forward\n";
cout << "7. Traverse Backward\n";
cout << "8. Search a Value\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value: ";
cin >> value;
[Link](value);
break;
case 2:
cout << "Enter value: ";
cin >> value;

47
 [Link](value);
break;
case 3:
[Link]();
break;
case 4:
[Link]();
break;
case 5:
cout << "Enter value to delete: ";
cin >> value;
[Link](value);
break;
case 6:
[Link]();
break;
case 7:
[Link]();
break;
case 8:
cout << "Enter value to search: ";
cin >> value;
[Link](value);
break;
case 0:
cout << "Exiting program...\n";
break;
default:
cout << "Invalid choice! Try again.\n";
}
} while (choice != 0);

return 0;
}

48
 3. Circular Linked List
A circular linked list is a variation of a traditional linked list where the last node in the list
points back to the first node (head), forming a continuous loop. Unlike linear linked lists where
the last node's next pointer is NULL, in a circular linked list, the next pointer of the last node
contains the address of the first node.

Types of Circular Linked Lists:

 Circular Singly Linked List:

In this type, each node has a data field and a single next pointer. The next pointer of the last node
points to the first node, creating a circular structure.

 Circular Doubly Linked List:

This variation extends the circular singly linked list by adding a previous pointer to each node. In a
circular doubly linked list, the next pointer of the last node points to the first node, and
the previous pointer of the first node points to the last node. This allows for traversal in both forward
and backward directions within the circular structure.

Key Characteristics:
o No NULL pointer:

The absence of a NULL pointer at the end of the list is a defining feature, as the last node always
points to the first.

o Continuous Traversal:

Traversal can continue indefinitely, as there is no designated end point. Careful handling is required
to prevent infinite loops during traversal, typically by stopping when the starting node is encountered
again.
o Efficient end-to-beginning operations:

Operations that involve wrapping around from the end of the list to the beginning, such as in round-
robin scheduling or playlist management, are naturally supported.

Advantage of Circular Linked List

49
 → Efficient Traversal

→ No Null Pointers / References

→ Useful for Repetitive Tasks

→ Insertion at Beginning or End is O(1)

→ Uniform Traversal
→ Efficient Memory Utilization

Disadvantage of Circular Linked List

→ Complex Implementation

→ Infinite Loop Risk

→ Harder to Debug

→ Deletion Complexity

→ Memory Overhead (for Doubly Circular LL)

→ Not Cache Friendly

Example Program:
#include <iostream>
using namespace std;

// Node structure
struct Node {
int data;
Node* next;
};

// Circular Linked List Class

class CircularLinkedList {
private:
Node* last; // Pointer to the last node

public:
CircularLinkedList() {
last = NULL;
}

50
// Check if list is empty
bool isEmpty() {
return last == NULL;
}

// Insert at Beginning
void insertAtBeginning(int value) {
Node* newNode = new Node;
newNode->data = value;

if (isEmpty()) {
last = newNode;
last->next = last; // Points to itself
} else {
newNode->next = last->next;
last->next = newNode;
}
cout << "Inserted " << value << " at beginning.\n";
}

// Insert at End
void insertAtEnd(int value) {
Node* newNode = new Node;
newNode->data = value;

if (isEmpty()) {
last = newNode;
last->next = last;
} else {
newNode->next = last->next;
last->next = newNode;
last = newNode;
}
cout << "Inserted " << value << " at end.\n";

51
}

// Delete from Beginning

void deleteFromBeginning() {
if (isEmpty()) {
cout << "List is empty!\n";
return;
}

Node* temp = last->next; // First node

if (last == last->next) { // Only one node
cout << "Deleted " << temp->data << " from beginning.\n";
delete temp;
last = NULL;
} else {
last->next = temp->next;
cout << "Deleted " << temp->data << " from beginning.\n";
delete temp;
}
}
// Delete from End
void deleteFromEnd() {
if (isEmpty()) {
cout << "List is empty!\n";
return;
}

Node* temp = last->next; // Start

if (last == last->next) { // Only one node
cout << "Deleted " << temp->data << " from end.\n";
delete temp;
last = NULL;
} else {
while (temp->next != last)

52
 temp = temp->next;

cout << "Deleted " << last->data << " from end.\n";
temp->next = last->next;
delete last;
last = temp;
}
}

// ? Delete by Value
void deleteByValue(int value) {
if (isEmpty()) {
cout << "List is empty!\n";
return;
}

Node* curr = last->next;

Node* prev = last;

// Single node case

if (curr == last && curr->data == value) {
cout << "Deleted node with value " << value << ".\n";
delete curr;
last = NULL;
return;
}

// Traversing to find the value

do {
if (curr->data == value) {
prev->next = curr->next;
if (curr == last)
last = prev;
cout << "Deleted node with value " << value << ".\n";

53
 delete curr;
return;
}
prev = curr;
curr = curr->next;
} while (curr != last->next);

cout << "Value " << value << " not found in the list.\n";
}

// Traverse / Display
void traverse() {
if (isEmpty()) {
cout << "List is empty!\n";
return;
}

Node* temp = last->next;

cout << "Circular Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != last->next);
cout << endl;
}

// Search for a value

void search(int value) {
if (isEmpty()) {
cout << "List is empty!\n";
return;
}

Node* temp = last->next;

54
 int pos = 1;
bool found = false;

do {
if (temp->data == value) {
cout << "Value " << value << " found at position " << pos << ".\n";
found = true;
}
temp = temp->next;
pos++;
} while (temp != last->next);

if (!found)
cout << "Value " << value << " not found in the list.\n";
}
};

// Main Function
int main() {
CircularLinkedList cll;
int choice, value;

do {
cout << "\n--- Circular Linked List Menu ---\n";
cout << "1. Insert at Beginning\n";
cout << "2. Insert at End\n";
cout << "3. Delete from Beginning\n";
cout << "4. Delete from End\n";
cout << "5. Delete by Value\n";
cout << "6. Traverse / Display\n";
cout << "7. Search a Value\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

55
switch (choice) {
case 1:
cout << "Enter value: ";
cin >> value;
[Link](value);
break;
case 2:
cout << "Enter value: ";
cin >> value;
[Link](value);
break;
case 3:
[Link]();
break;
case 4:
[Link]();
break;
case 5:
cout << "Enter value to delete: ";
cin >> value;
[Link](value);
break;
case 6:
[Link]();
break;
case 7:
cout << "Enter value to search: ";
cin >> value;
[Link](value);
break;
case 0:
cout << "Exiting program...\n";
break;

56
 default:
cout << "Invalid choice! Try again.\n";
}
} while (choice != 0);

return 0;
}

Sorted linked list

A sorted linked list is a type of linked list where the data elements (nodes) are maintained in a
specific order, such as ascending or descending, based on their values. This order is preserved
during all operations, particularly insertion and deletion.

Key Characteristics:
• Ordered Elements:
Unlike a general linked list, elements in a sorted linked list are always arranged according to a
defined sorting criterion.

• Dynamic Sizing:
Like all linked lists, it can grow or shrink dynamically as elements are added or removed.

• Efficient Insertion (Maintaining Order):

When a new element is inserted, the list must be traversed to find the correct position to maintain
the sorted order. This involves comparing the new element's value with existing node values.

• Flexible Node Structure:

Each node typically contains the data element and a pointer (or reference) to the next node in the
sequence. In a doubly sorted linked list, nodes also have a pointer to the previous node.

Sort Linked List using Bubble Sort

→ To apply Bubble Sort to a linked list, we need to traverse the list multiple
times, comparing adjacent nodes and swapping their positions by adjusting their links if
the current node’s data is greater than the next.
→ During each pass, the largest unsorted element moves to its correct position at the end of
the list.
→ This process continues until no more swaps are needed, indicating that the list is sorted.
→ Time complexity: O(n^2), where n is the number of nodes in the Linked List.
→ Auxiliary space: O(1)

Please refer to Bubble Sort for Linked List for implementation.

57
Sort Linked List using Insertion Sort
→ The algorithm for sorting a linked list using Insertion Sort involves gradually building a sorted
portion of the list within the same memory space.
→ For each node, the algorithm determines its correct position within the sorted list.
→ If the node is smaller than the current head of the sorted list, it becomes the new head.
→ Otherwise, it is inserted into its appropriate position by traversing the sorted list.
→ This process is repeated until all nodes are correctly positioned, resulting in the sorted list.
→ Time Complexity: O(n2), In the worst case, we might have to traverse all nodes of the sorted
list for inserting a node.
→ Auxiliary Space: O(1), no extra space is required.
Please refer to Insertion Sort for Singly Linked List for implementation.

Sort Linked List using Quick Sort

→ Quick Sort is a highly efficient divide-and-conquer algorithm used for sorting linked lists.
→ The algorithm operates by selecting a pivot element from the list and partitioning the
remaining elements into two sub lists, one containing elements smaller than the pivot and
the other with elements larger.
→ This partitioning step ensures that elements are grouped around the pivot, with all elements
smaller placed before it and all larger placed after the pivot.
→ The algorithm then recursively applies the same process to the sub lists, progressively
sorting the entire list.
→ Time Complexity: O(n * log n), It takes O(n2) time in the worst case and O(n log n) in
→ the average or best case.
→ Auxiliary Space: O(n)

Please refer to QuickSort on Singly Linked List for implementation.

Sort Linked List using Merge Sort

→ Merge Sort is a divide-and-conquer algorithm that splits the array into two halves,
recursively sorts each half, and then merges the sorted halves back together.
→ It requires additional memory to store temporary subarrays during the merge process.
→ The algorithm repeatedly splits and merges until the entire array is sorted.
Please refer to Merge Sort for Linked Lists for implementation.

Which Sorting Algorithm is best for Linked Lists?

For linked lists, Merge Sort is often the best choice because:

• Merge Sort guarantees a time complexity of O(nlogn) in the average, best, and worst cases.

• Merge Sort is Stable.

• Merge Sort naturally fits well with Linked List because it traverses items in sequential manner
(no random access).
• When we compare linked list implementation with the array implementation we can notice
that the linked list implementation does not require extra space to merge because linked list
allows insertion and deletion in the middle in O(1) time.
58
Week 8
Sorting Algorithm
Sorting algorithms are fundamental procedures in data structures used to arrange elements
of a list or array in a specific order, typically ascending or descending.

Common Sorting Algorithms in C++:

→ Bubble Sort:

• Compares adjacent elements and swaps them if they are in the wrong order.

• Repeatedly passes through the list until no more swaps are needed.
• Simple to understand but inefficient for large datasets.

→ Selection Sort:

• Finds the minimum (or maximum) element from the unsorted part of the list and swaps
it with the element at the beginning of the unsorted part.

• Repeats until the entire list is sorted.

• Also simple to implement but has a quadratic time complexity.

→ Insertion Sort:

• Builds the final sorted array one item at a time.

• Each new element is inserted into its correct position within the already sorted portion
of the array.
• Efficient for small datasets or nearly sorted data.

→ Merge Sort:
• A divide-and-conquer algorithm.

• Divides the unsorted list into n sublists, each containing one element, and then
repeatedly merges sublists to produce new sorted sublists until there is only one
sublist remaining.

• Guarantees O(n log n) time complexity.

→ Quick Sort:

• Another divide-and-conquer algorithm.

• Picks an element as a pivot and partitions the array around the pivot, placing all smaller
elements before the pivot and all greater elements after it.
• Recursively sorts the sub-arrays.

59
 • Generally considered one of the fastest sorting algorithms in practice, with an average
time complexity of O(n log n).

→ Heap Sort:

• Uses a binary heap data structure.

• Builds a max-heap (or min-heap) from the input data, then repeatedly extracts the
maximum (or minimum) element and rebuilds the heap.

• Guarantees O(n log n) time complexity.

→ Shell Sort:

• An extension of insertion sort.

• Sorts elements that are far apart, then gradually reduces the gap between elements
to be sorted.

• More efficient than simple insertion sort for larger lists.

 Selection sort
Selection sort is a simple, in-place comparison-based sorting algorithm.

It works by repeatedly finding the minimum element from the unsorted part of the array and placing
it at the beginning of the sorted part.

Algorithm Steps / working:

• Divide the array: Conceptually, the array is divided into two parts: a sorted subarray at the
beginning and an unsorted subarray at the end. Initially, the sorted subarray is empty, and
the unsorted subarray is the entire array.

• Iterate through the unsorted part: For each iteration, starting from the first element of the
unsorted part:

a. Find the minimum: Find the minimum element in the unsorted subarray.

b. Swap: Swap the found minimum element with the first element of the unsorted
subarray. This effectively moves the minimum element to its correct position in the sorted
subarray.

• Update boundaries:

Increment the boundary of the sorted subarray by one, and decrement the boundary of
the unsorted subarray by one.

• Repeat:

Continue this process until the entire array is sorted (i.e., the unsorted subarray becomes
empty).

Advantages of Selection Sort:

→ Simplicity:
60
It is easy to understand and implement, making it a good choice for learning basic sorting concepts.

→ Minimal Swaps:

Selection sort performs a maximum of N-1 swaps, where N is the number of elements. This can be
advantageous in scenarios where swapping elements is a computationally expensive operation.

→ In-place Sorting:

It requires a constant amount of extra memory (O(1)) as it sorts the array directly without needing
additional temporary storage.

→ Good for Small Datasets:

For small lists, its simplicity and minimal swap count can make it a reasonable choice, as the
overhead of more complex algorithms might outweigh their asymptotic advantages.

Disadvantages of Selection Sort:

→ Poor Efficiency for Large Datasets:

Its time complexity is O(N^2) in all cases (best, average, and worst), making it highly inefficient for
large lists compared to algorithms like Quick Sort or Merge Sort.

→ Not Adaptive:

Selection sort does not take advantage of any pre-existing order in the input array. It performs the
same number of comparisons regardless of whether the array is partially or fully sorted.

→ Not Stable:
It is not a stable sorting algorithm, meaning the relative order of equal elements might not be
preserved after sorting.

→ Inefficient Comparisons:
The algorithm performs a high number of comparisons, even when the array is nearly sorted, leading
to wasted computations for larger datasets.

Use Cases of Selection Sort:

Selection Sort is a simple, in-place comparison-based sorting algorithm. While its O(N^2) time
complexity makes it inefficient for large datasets, it has specific use cases and best practices where
its characteristics are advantageous.

o Small Datasets:
For sorting very small arrays or lists, the simplicity of Selection Sort can make it a practical choice,
as the overhead of more complex algorithms might not be justified.
o Memory-Constrained Environments (e.g., Embedded Systems):

Selection Sort is an in-place algorithm, meaning it requires only a constant amount of extra memory
(O(1) space complexity). This makes it suitable for environments with limited memory resources.
o Educational Purposes:

61
Its straightforward logic and step-by-step nature make it an excellent algorithm for teaching
fundamental sorting concepts and algorithmic design to beginners in computer science.

o Minimizing Swaps/Writes:

Selection Sort performs a maximum of N-1 swaps, which is the minimum possible for any sorting
algorithm. This can be beneficial in scenarios where memory write operations are costly or have a
limited lifespan (e.g., certain types of Flash memory).

o Data Preprocessing for Small Subsets:

When preparing small subsets of data for further processing, Selection Sort can be used to organize
them before applying more advanced algorithms.

Best Practices for Selection Sort:

o Avoid for Large Datasets:

Due to its quadratic time complexity, Selection Sort should not be used for sorting large datasets,
as it will be significantly slower than algorithms like Merge Sort or Quick Sort.

o Understand Its Limitations:

Be aware of Selection Sort's performance characteristics and choose it only when its advantages
(simplicity, in-place nature, minimal swaps) outweigh its time complexity limitations for the specific
application.

o Clear Implementation:

While simple, ensure the implementation is clear and correctly handles edge cases, such as empty
arrays or arrays with a single element.

o Consider Alternatives for General-Purpose Sorting:

For most general-purpose sorting tasks, especially with larger datasets, more efficient algorithms
are preferred. Selection Sort is a specialized tool for particular scenarios.

Example Program:
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int arr[5],i,j,temp;

for(i=0;i<5;i++)
{
cout<<"Enter value: ";
cin>>arr[i];

62
 }

cout<<"\nThe original value in array: ” ;

for(i=0;i<5;i++)
cout<<arr[i]<<" ";

for(i=0;i<5;i++)
{
for(j=0;j<4;j++)
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
cout<<"\nThe sorted array is: " ;
for(i=0;i<5;i++)
cout<<arr[i]<<" ";
getch();
}
Output:
Enter value: 31
Enter value: 4
Enter value: 55
Enter value: 6
Enter value: 12
The original value in array: 31 4 55 6 12
The sorted array is: 4 6 12 31 55
Complexity Analysis of Selection sort:
► Time Complexity:
Selection Sort exhibits a time complexity of O(n^2) in all cases: best, average, and

worst. This quadratic complexity arises from its nested loop structure.

• Outer Loop:

63
 This loop iterates n-1 times, where n is the number of elements in

the array. Each iteration places one element in its correct sorted position.

• Inner Loop:

Within each iteration of the outer loop, the inner loop traverses the

remaining unsorted portion of the array to find the minimum element. In the first iteration, it
performs n-1 comparisons, in the second, n-2 comparisons, and so on, until the last iteration with 1
comparison.

The total number of comparisons sums up to (n-1) + (n-2) + ... + 1, which is equivalent to n(n-
1)/2. This sum simplifies to O(n^2), indicating that the execution time grows quadratically with the
input size. The number of swaps is at most n-1.

► Space Complexity:

Selection Sort is an in-place sorting algorithm, meaning it sorts the arraywithout requiring
significant additional memory. Its space complexity is O(1), as it only uses a constant amount of
extra space for temporary variables during swaps.

Example Dry Run:

Array: [64, 25, 12, 22, 11]

Pass Minimum After Swap

1 11 [11, 25, 12, 22, 64]

2 12 [11, 12, 25, 22, 64]

3 22 [11, 12, 22, 25, 64]

4 25 [11, 12, 22, 25, 64]

Final Sorted Array: [11, 12, 22, 25, 64]

 Insertion Sort
o Insertion Sort is a simple comparison-based sorting algorithm.
o It works by taking one element at a time and placing it in its correct position.
o Similar to arranging cards in your hand one by one in sorted order.

Working Principle:
❖ The first element is considered sorted.
❖ Starting from index 1, each element is compared with previous elements.
❖ While previous elements are greater, they are shifted to the right.
❖ The current element is then inserted into its correct position.

64
Example:
Unsorted Array: {4, 1, 5, 2, 3}

Step 1 → {1, 4, 5, 2, 3}

Step 2 → {1, 4, 5, 2, 3}

Step 3 → {1, 2, 4, 5, 3}

Step 4 → {1, 2, 3, 4, 5}
Result: Sorted Array {1, 2, 3, 4, 5}

Works with Strings & Negative Numbers:

• Insertion Sort can handle any data type where comparison (<, >) is defined.

• Works with:

- Negative numbers (e.g., {-3, 5, -1, 2})

- Strings (e.g., {'cat', 'apple', 'bat'})

• Because sorting is purely based on comparisons.

Advantages:
• Simple and easy to implement.

• Adaptive – performs better on nearly sorted data.

• Stable and in-place.

Disadvantages:
• Slow for large datasets (O(n²)).

• Many shifts and comparisons required.

• Not suitable for large-scale applications.

Use Cases:
o Small or partially sorted arrays.
o Online sorting (data arriving one by one).
o Teaching and algorithm demonstrations.

Best Practices:
o Use for arrays < 25 elements.
o Effective inside hybrid algorithms like Timsort.

Comparison Insertion Sort vs Others:

 Bubble Sort: Slower, compares all adjacent elements.
 Selection Sort: Fewer swaps but not adaptive.

 Insertion Sort: Fastest on small or nearly sorted data.

65
Stable, simple, and space-efficient.

Example program:
#include<iostream>
#include<conio.h>
using namespace std;
void insertionsort(int arr[],int n)
{
for(int i=1;i<n;i++)
{
int curr=arr[i];
int prev=i-1;
while(prev>=0 && arr[prev]>curr)
{
arr[prev+1]=arr[prev];
prev--;
}
arr[prev+1]=curr;
}
}
int main()
{
int n=5;
int arr[]={4,1,5,2,3};
insertionsort( arr, n);
for (int i=0;i<n;i++)
{
cout<<arr[i] << “ ”;
}
return 0;
}
Output:
12345

Complexity analysis of Insertion sort:

► Time Complexity:

→ Best Case: O(n)

• Occurs when the input array is already sorted.

66
 • Each element is compared only once to its preceding element, and no shifts are
required. The number of comparisons is roughly proportional to the number of
elements (n).

→ Worst Case: O(n^2)

• Occurs when the input array is sorted in reverse order.

• Each element must be compared with all previously sorted elements and shifted to its
correct position, resulting in a quadratic number of comparisons and shifts.

→ Average Case: O(n^2)

• For randomly ordered inputs, the average performance is also quadratic, similar to the
worst case, as a significant number of comparisons and shifts are still typically
required.

► Space Complexity:

O(1):
Insertion Sort is an in-place sorting algorithm, meaning it requires a constant amount
of extra space regardless of the input size. It only uses a few temporary variables for
comparisons and element storage during shifts.

Summarization / Conclusion:
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item
at a time. It is an in-place comparison-based sorting algorithm, meaning it sorts the array by
comparing elements and doesn't require extra space proportional to the input size.

→ Insertion Sort builds the final sorted array one element at a time.
→ Best for small datasets and educational use.
→ Easy to understand and implement.
→ Not efficient for large, unsorted datasets.

 Merge sort
 Merge sort is a popular sorting algorithm known for its efficiency and stability.
 It follows the Divide and Conquer approach.
 It works by recursively dividing the input array into two halves, recursively sorting the two
halves and finally merging them back together to obtain the sorted array.

Key components:
• Divide: The algorithm starts with breaking up the array into smaller and smaller pieces until
one such sub-array only consists of one element.

• Conquer: The algorithm merges the small pieces of the array back together by putting the
lowest values first, resulting in a sorted array.

• The breaking down and building up of the array to sort the array is done recursively.

67
Table:

Merge Sort works by dividing the data, sorting the parts, and then merging them back together.

How it works?
1. Divide the unsorted array into two sub-arrays, half the size of the original.

2. Continue to divide the sub-arrays as long as the current piece of the array has more than one
element.

3. Merge two sub-arrays together by always putting the lowest value first.

4. Keep merging until there are no sub-arrays left.

Complexity Analysis of Merge Sort:

→ Time Complexity:

• Best Case: O(n log n), When the array is already sorted or nearly sorted.
• Average Case: O(n log n), When the array is randomly ordered.
• Worst Case: O(n log n), When the array is sorted in reverse order.

68
 → Auxiliary Space: O(n), Additional space is required for the temporary array used during
merging.

Pros / Advantages:
► Stability: Merge sort is a stable sorting algorithm, which means it maintains the relative order
of equal elements in the input array.

► Guaranteed worst-case performance: Merge sort has a worst-case time complexity of O(N
logN), which means it performs well even on large datasets.

► Simple to implement: The divide-and-conquer approach is straightforward.

Cons / Disadvantages:
► Space complexity: Merge sort requires additional memory to store the merged sub-arrays
during the sorting process.
► Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires
additional memory to store the sorted data. This can be a disadvantage in applications where
memory usage is a concern.

Example program:
#include <iostream>
using namespace std;

// Function to merge two subarrays

void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray

int L[n1], R[n2]; // Temporary arrays

// Copy data to temp arrays

for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

// Merge the temp arrays back into arr[left..right]

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] >= R[j]) {

69
 arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy remaining elements of L[], if any

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy remaining elements of R[], if any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// Function to divide array and call merge

void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;

mergeSort(arr, left, mid); // Sort first half

mergeSort(arr, mid + 1, right); // Sort second half

merge(arr, left, mid, right); // Merge the two halves

}

70
 }

// Main function
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";

for (int i = 0; i < size; i++)
cout << arr[i] << " ";

mergeSort(arr, 0, size - 1);

cout << "\nSorted array: ";

for (int i = 0; i < size; i++)
cout << arr[i] << " ";

return 0;
}
Output:
Original array: 38 27 43 3 9 82 10
Sorted array: 82 43 38 27 10 9 3

 Quick Sort
Quick Sort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot
and partitions the given array around the picked pivot by placing the pivot in its correct position in
the sorted array.

It works on the principle of divide and conquer, breaking down the problem into smaller sub-
problems.

Working:
There are mainly three steps in the algorithm:
1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can vary
(e.g., first element, last element, random element, or median).

71
 2. Partition the Array: Re arrange the array around the pivot. After partitioning, all elements
smaller than the pivot will be on its left, and all elements greater than the pivot will be on its
right. The pivot is then in its correct position, and we obtain the index of the pivot.

3. Recursively Call: Recursively apply the same process to the two partitioned sub-arrays (left
and right of the pivot).
4. Base Case: The recursion stops when there is only one element left in the sub-array, as a
single element is already sorted.

Choice of Pivot
There are many different choices for picking pivots.

• Always pick the first (or last) element as a pivot. The below implementation picks the last
element as pivot. The problem with this approach is it ends up in the worst case when array
is already sorted.

• Pick a random element as a pivot. This is a preferred approach because it does not have
a pattern for which the worst case happens.

• Pick the median element is pivot. This is an ideal approach in terms of time complexity
as we can find median in linear time and the partition function will always divide the input
array into two halves. But it takes more time on average as median finding has high constants.

Partition Algorithm
The key process in quicksort is a partition(). There are three common algorithms to partition. All
these algorithms have O(n) time complexity.
1. Naive Partition: Here we create copy of the array. First put all smaller elements and then all
greater. Finally, we copy the temporary array back to original array. This requires O(n) extra
space.

2. Lomuto Partition: We have used this partition in this article. This is a simple algorithm we
keep track of index of smaller elements and keep swapping. We have used it here in this
article because of its simplicity.
72
 3. Hoare's Partition: This is the fastest of all. Here we traverse array from both sides and keep
swapping greater element on left with smaller on right while the array is not partitioned.

Complexity Analysis of Quick Sort

► Time Complexity:

• Best Case: (Ω(n log n)), Occurs when the pivot element divides the array into two
equal halves.

• Average Case (θ(n log n)), On average, the pivot divides the array into two parts, but
not necessarily equal.

• Worst Case: (O(n²)), Occurs when the smallest or largest element is always chosen
as the pivot (e.g., sorted arrays).

► Auxiliary Space:

• Worst-case scenario: O(n) due to unbalanced partitioning leading to a skewed

recursion tree requiring a call stack of size O(n).

• Best-case scenario: O(log n) as a result of balanced partitioning leading to a

balanced recursion tree with a call stack of size O(log n).

Dry run Example:

o Say the array is:

10, 7, 8, 9, 1, 5

o Pivot = 5
o After first partition → 1, 5, 8, 9, 10, 7
o Then recursively sort left and right sides.
o Finally → 1, 5, 7, 8, 9, 10

Advantages:
→ Fast and efficient (Average time: O(n log n))

→ Works in-place (less memory needed)

→ Uses Divide and Conquer method

→ Good for large data sets

→ Used in C++ STL sort()

Disadvantages:
→ It has a worst-case time complexity of O(n2), which occurs when the pivot is chosen poorly.
→ It is not a good choice for small data sets.
→ It is not a stable sort, meaning that if two elements have the same key, their relative order
will not be preserved in the sorted output in case of quick sort, because here we are swapping
elements according to the pivot's position (without considering their original positions).

73
Example program:
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = 6;

quickSort(arr, 0, n - 1);

cout << "Sorted array: ";

for (int i = 0; i < n; i++)
cout << arr[i] << " ";

return 0;
}
Output:

74
 Sorted array: 1 5 7 8 9 10

Comparison Between Sorting Algorithms

Algorithm Average Time Best Worst Space Stability Remarks

Complexity Case Case

Very simple but slow;

Selection O(n²) O(n²) O(n²) O(1) No always compares all pairs
Sort even if data is nearly
sorted.

Insertion O(n²) O(n) O(n²) O(1) Yes Efficient for small or

Sort nearly sorted data sets.

Merge O(n O(n log Very consistent and

Sort O(n log n) log n) n) O(n) Yes stable; uses extra
memory.

Usually fastest in practice

Quick Sort O(n log n) O(n O(n²) O(log No for large data; bad pivot
log n) n) selection can slow it
down.

o On average, Quick Sort is the fastest because of its efficient in-place partitioning.
o It minimizes memory usage (only needs O(log n) extra space).
o It’s widely used in system-level implementations (like C++’s std::sort()).
• However…
o If you need stable sorting (i.e., order of equal elements preserved) → use Merge Sort.
o For small datasets or almost sorted lists, Insertion Sort can outperform both due to
very low overhead.

75
The End

76