COL106: Data Structures and Algorithms
Lab 12: Sorting & Graphs
Instructions
• You must ensure that your attendance is marked in the lab.
• You should start the lab by running the sample programs provided in the Lab Activity Sheet (Section 2) and
experiment with them to understand their behavior. You can then solve the practice problems provided
(Section 3) in the Activity Sheet.
1. Lab Notes
Sorting is one of the most fundamental operations in computer science. It is the process of arranging a collection
of items in a specific order (usually ascending or descending). Efficient sorting is critical because it optimizes the
usefulness of other algorithms, such as binary search, which require sorted input data.
In this lab, we explore various comparison-based and non-comparison-based sorting algorithms, evaluate their
theoretical bounds, and analyze their performance, stability, and memory overhead.
A graph is a non-linear data structure consisting of a finite set of vertices (also called nodes) connected by edges.
Unlike trees, graphs allow arbitrary connections between nodes, including cycles, disconnected components, and
multiple edges. This generality makes graphs the natural model for a vast range of real-world systems, from road
networks and social connections to dependency graphs and web link structures.
1.1 Properties of Sorting Algorithms
When selecting a sorting algorithm, several properties must be considered:
• Time Complexity: The number of operations required, typically analyzed in the best, average, and worst
cases. Comparison-based sorts have a theoretical lower bound of Ω(n log n).
• Space Complexity (In-place): An in-place sorting algorithm requires only O(1) auxiliary space beyond the
input array.
• Stability: A stable sorting algorithm preserves the relative order of equal elements. If two elements have
the same key, their initial relative order is maintained.
• Adaptivity: An adaptive algorithm performs better when the input data is already partially sorted.
1.2 Comparison-Based Sorting Algorithms
These algorithms sort by comparing pairs of elements.
1.2.1 Elementary Sorts (O(n2 ))
• Bubble Sort: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in
the wrong order. It is stable and in-place.
• Selection Sort: Divides the array into a sorted and an unsorted region. Repeatedly selects the minimum
element from the unsorted region and moves it to the end of the sorted region. It is in-place but not stable.
• Insertion Sort: Builds the sorted array one element at a time by picking the next element and inserting it
into its correct position in the already sorted part. It is stable, in-place, and highly adaptive (O(n) best case).
1
1.2.2 Efficient Sorts (O(n log n))
Merge Sort: A divide-and-conquer algorithm that recursively splits the array into halves until they are trivially
sorted (size 1), then merges the sorted halves.
• Time: Θ(n log n) in all cases.
• Space: O(n) auxiliary space.
• Stability: Stable.
Quick Sort: A divide-and-conquer algorithm that picks a ‘pivot‘ element and partitions the array such that ele-
ments smaller than the pivot come before it, and elements larger come after it.
• Time: O(n log n) expected, O(n2 ) worst case.
• Space: O(log n) average for the recursion stack.
• Stability: Not stable (standard in-place implementation).
Heap Sort: Converts the array into a max-heap structure, then repeatedly extracts the maximum element and
places it at the end.
• Time: O(n log n) in all cases.
• Space: O(1) in-place.
• Stability: Not stable.
1.3 Non-Comparison Based Sorting
These algorithms bypass the Ω(n log n) lower bound by using integer arithmetic and hashing-like techniques,
rather than direct comparisons.
• Counting Sort: Counts the frequency of each distinct element, computes prefix sums, and places elements
in the output array. Runs in O(n + k ) time where k is the range of inputs. Requires O(k ) extra space.
• Radix Sort: Sorts elements digit by digit, starting from the least significant digit (LSD) to the most significant
(MSD), using a stable sub-routine like Counting Sort. Runs in O(d(n + k )) where d is the number of digits.
1.4 Complexity Summary
Algorithm Best Time Average Time Worst Time Space Stable
Insertion Sort O(n) O ( n2 ) O ( n2 ) O (1) Yes
Selection Sort O ( n2 ) O ( n2 ) O ( n2 ) O (1) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n log n) O ( n2 ) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O (1) No
Counting Sort O(n + k) O(n + k) O(n + k) O(n + k) Yes
1.5 Graphs
A graph G is formally defined as a pair G = (V, E), where V is a set of vertices and E ⊆ V × V is a set of edges.
Each edge represents a connection between two vertices.
1.5.1 Key Terminology
• Vertex (Node): A fundamental unit of the graph.
• Edge: A connection between two vertices. An edge (u, v) connects vertex u to vertex v.
• Adjacency: Two vertices are adjacent if there exists an edge between them.
• Degree: The number of edges incident to a vertex. In a directed graph, we distinguish in-degree (edges
entering) and out-degree (edges leaving).
• Path: A sequence of vertices v1 , v2 , . . . , vk such that consecutive vertices are connected by an edge.
2
• Cycle: A path that begins and ends at the same vertex.
• Connected Graph: An undirected graph in which there is a path between every pair of vertices.
• Strongly Connected: A directed graph in which every vertex is reachable from every other vertex.
• Weight: A numeric value associated with an edge (in a weighted graph).
1.5.2 Types of Graphs
• Undirected Graph: Edges have no direction; (u, v) and (v, u) represent the same edge.
• Directed Graph (Digraph): Each edge has a direction; (u, v) is a one-way edge from u to v.
• Weighted Graph: Each edge carries a numerical weight.
• Unweighted Graph: All edges are treated as having equal weight.
• Cyclic Graph: Contains at least one cycle.
• Acyclic Graph / DAG: A directed graph with no cycles.
1.5.3 Graph Representations
Adjacency Matrix. A V × V matrix A where A[i ][ j] = 1 if there is an edge from vertex i to vertex j, and 0
otherwise. For weighted graphs, A[i ][ j] stores the edge weight.
Metric Value
Space O (V 2 )
Edge lookup O (1)
Enumerate neighbours O (V )
Best suited for dense graphs where E ≈ V 2 .
Adjacency List. An array of V lists, where adj[u] contains all vertices adjacent to u.
// Adjacency list for 4 vertices
vector<int> adj[4];
adj[0] = {1, 2};
adj[1] = {0, 3};
adj[2] = {0, 3};
adj[3] = {1, 2};
Metric Value
Space O (V + E )
Edge lookup O(deg(v))
Enumerate neighbours O(deg(v))
Best suited for sparse graphs where E ≪ V 2 .
1.5.4 Applications of Graphs
• Shortest path finding: Navigation systems (GPS), network routing protocols.
• Social networks: Modelling friendships, follower relationships, communities.
• Dependency resolution: Build systems (Makefiles), package managers.
• Web crawling: The World Wide Web as a directed graph of hyperlinks.
• Connected components: Image segmentation, circuit analysis.
• Cycle detection: Deadlock detection in operating systems.
3
1.5.5 Graph ADT
The Graph ADT supports at least the following operations:
Accessor Methods:
• vertices(): Returns the set of all vertices.
• edges(): Returns the set of all edges.
• degree(v): Returns the degree of vertex v.
• neighbors(v): Returns all vertices adjacent to v.
• hasEdge(u, v): Returns true if edge (u, v) exists.
Update Methods:
• addVertex(v): Inserts a new vertex v.
• addEdge(u, v): Inserts an edge between u and v.
• removeVertex(v): Removes vertex v and all incident edges.
• removeEdge(u, v): Removes the edge (u, v).
4
2. Lab Activity Sheet
2.1 Problem 1: Quick Sort Implementation
Problem Statement:
Implement the Quick Sort algorithm to sort an array of integers in ascending order. You must use an in-place
partitioning strategy (such as Lomuto’s or Hoare’s partition scheme).
Test Cases:
1. Input: nums = [5, 2, 9, 1, 5, 6]
Output: [1, 2, 5, 5, 6, 9]
2. Input: nums = [10, 8, 4, 3, 1]
Output: [1, 3, 4, 8, 10]
Solution:
Below is the C++ implementation using the Lomuto partition scheme. The pivot is chosen as the last element of
the array segment.
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 class Solution {
7 private:
8 int partition(vector<int>& arr, int low, int high) {
9 int pivot = arr[high]; // Choosing the last element as pivot
10 int i = low - 1; // Index of smaller element
11
12 for (int j = low; j < high; j++) {
13 // If current element is smaller than or equal to pivot
14 if (arr[j] <= pivot) {
15 i++;
16 swap(arr[i], arr[j]);
17 }
18 }
19 swap(arr[i + 1], arr[high]);
20 return i + 1;
21 }
22
23 void quickSort(vector<int>& arr, int low, int high) {
24 if (low < high) {
25 // pi is partitioning index, arr[pi] is now at right place
26 int pi = partition(arr, low, high);
27
28 // Separately sort elements before and after partition
29 quickSort(arr, low, pi - 1);
30 quickSort(arr, pi + 1, high);
31 }
32 }
33
34 public:
35 void sortArray(vector<int>& nums) {
36 if ([Link]()) return;
37 quickSort(nums, 0, [Link]() - 1);
38 }
39 };
Test Case Execution:
Trace for nums = [4, 1, 3, 2] with Lomuto partition:
5
Call Pivot State / Result
qSort(0, 3) arr[3] = 2 arr becomes [1, 2, 3, 4], returns pi = 1
qSort(0, 0) N/A Base case reached, no change
qSort(2, 3) arr[3] = 4 arr stays [1, 2, 3, 4], returns pi = 3
qSort(2, 2) N/A Base case reached, no change
Complexity Analysis
Time Complexity:
• Average Case: O(n log n). The partition index roughly divides the array into two equal halves.
• Worst Case: O(n2 ). This occurs if the array is already sorted and we pick the last element as the pivot,
leading to heavily unbalanced recursive calls.
Space Complexity: O(log n) average for the recursion stack, up to O(n) in the worst case.
Bonus Task: Modify the code to use a randomized pivot (pick a random index, swap it with the last element,
and proceed with Lomuto partition). How does this affect the likelihood of hitting the O(n2 ) worst-case?
2.2 Problem 2: Constructing an Adjacency List
Problem Statement:
You are given an undirected graph with n vertices and a list of edges. Each edge is represented as a pair of integers
[u, v], indicating a connection between vertex u and vertex v. Convert this representation into an Adjacency List.
Constraints
• 1 ≤ n ≤ 105
• 0 ≤ | E| ≤ 105
• 0 ≤ u, v < n
Solution:
Below is the C++ implementation using std::vector to represent the adjacency list.
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 class GraphBuilder {
7 public:
8 vector<vector<int>> buildAdjacencyList(int n, vector<vector<int>>& edges) {
9 // Initialize a vector of vectors for n vertices
10 vector<vector<int>> adj(n);
11
12 for (const auto& edge : edges) {
13 int u = edge[0];
14 int v = edge[1];
15
16 // For undirected graphs, add both directions
17 adj[u].push_back(v);
18 adj[v].push_back(u);
19 }
20 return adj;
21 }
22 };
6
Example
Input:
n = 4, edges = [[0,1], [1,2], [2,3], [0,2]]
Output:
[[1, 2], [0, 2], [1, 3, 0], [2]]
Test Case Execution: Adjacency List Construction
Trace for n = 4 and edges = [[0,1], [1,2], [2,3], [0,2]]:
Edge Processed Adjacency List State (adj) Explanation
Initial State [ [], [], [], [] ] Initialize n empty vectors.
[0, 1] [ [1], [0], [], [] ] Add 1 to adj[0] and 0 to adj[1].
[1, 2] [ [1], [0, 2], [1], [] ] Add 2 to adj[1] and 1 to adj[2].
[2, 3] [ [1], [0, 2], [1, 3], [2] ] Add 3 to adj[2] and 2 to adj[3].
[0, 2] [ [1, 2], [0, 2], [1, 3, 0], [2] ] Add 2 to adj[0] and 0 to adj[2].
Final Structure Analysis:
• Space Complexity: O(V + E) because we store each vertex and each edge twice (for undirected).
• Efficiency: Neighbors of any vertex u can now be enumerated in O(deg(u)) time.
7
3. Practice Problems
3.1 Problem 1: Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color
are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library’s sort function.
Constraints
• n == [Link]
• 1 ≤ n ≤ 300
• nums[i] is either 0, 1, or 2.
Example 1
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2
Input: nums = [2,0,1]
Output: [0,1,2]
Can you come up with a one-pass algorithm using only constant extra space?
3.2 Problem 2: Merge Intervals
Given an array of intervals where intervals[i] = [starti , endi ], merge all overlapping intervals, and return an
array of the non-overlapping intervals that cover all the intervals in the input.
Constraints
• 1 ≤ [Link] ≤ 104
• intervals[i].length == 2
• 0 ≤ starti ≤ endi ≤ 104
Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
3.3 Problem 3: Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting the entire array? (Hint: QuickSelect or Min-Heap)
8
Constraints
• 1 ≤ k ≤ [Link] ≤ 105
• −104 ≤ nums[i ] ≤ 104
Example 1
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
3.4 Problem 4: Largest Number
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
Constraints
• 1 ≤ [Link] ≤ 100
• 0 ≤ nums[i ] ≤ 109
Example 1
Input: nums = [10,2]
Output: "210"
Example 2
Input: nums = [3,30,34,5,9]
Output: "9534330"
3.5 Problem 5: Sort Characters By Frequency
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character
is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Constraints
• 1 ≤ [Link] ≤ 5 × 105
• s consists of uppercase and lowercase English letters and digits.
Example 1
Input: s = "tree"
Output: "eert"
Explanation: ’e’ appears twice while ’r’ and ’t’ both appear once. So ’e’ must appear before both ’r’ and
’t’. Therefore "eetr" is also a valid answer.
9
Example 2
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both ’c’ and ’a’ appear three times, so both "cccaaa" and "aaaccc" are valid answers.
3.6 Problem 6: Maximum Gap*
Given an integer array nums, return the maximum difference between two successive elements in its sorted form.
If the array contains less than two elements, return 0.
You must write an algorithm that runs in linear time and uses linear extra space. (Hint: Radix Sort or Bucket Sort)
Constraints
• 1 ≤ [Link] ≤ 105
• 0 ≤ nums[i ] ≤ 109
Example 1
Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference
3.
Example 2
Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
3.7 Problem 7: Mutual Neighbors Query
You are given an initially empty undirected graph with n vertices labeled from 0 to n − 1.
Design a data structure that supports the following operations:
• addEdge(u, v): Adds an undirected edge between u and v. If the edge already exists, do nothing.
• removeEdge(u, v): Removes the edge between u and v if it exists.
• commonNeighbors(u, v): Returns the number of vertices that are adjacent to both u and v.
Constraints
• 1 ≤ n ≤ 105
• At most 105 operations will be performed.
• 0 ≤ u, v < n, u ̸= v
10
Example 1
Input:
n = 5
["addEdge","addEdge","addEdge","commonNeighbors"]
[[0,1],[0,2],[1,2],[0,1]]
Output:
[null,null,null,1]
Explanation:
Neighbors of 0 = {1,2}, neighbors of 1 = {0,2}. Common = {2}.
Example 2
Input:
n = 4
["addEdge","addEdge","commonNeighbors","removeEdge","commonNeighbors"]
[[0,1],[1,2],[0,2],[1,2],[0,2]]
Output:
[null,null,1,null,0]
Example 3
Input:
n = 3
["commonNeighbors","addEdge","commonNeighbors"]
[[0,1],[0,2],[0,1]]
Output:
[0,null,0]
3.8 Problem 8: Dynamic Degree Tracker
You are given an initially empty directed graph with n vertices labeled from 0 to n − 1.
Design a data structure that supports the following operations:
• addEdge(u, v): Adds a directed edge from u to v. Ignore if it already exists.
• removeEdge(u, v): Removes the edge from u to v if it exists.
• inDegree(v): Returns the number of incoming edges to vertex v.
• outDegree(v): Returns the number of outgoing edges from vertex v.
• hasEdge(u, v): Returns true if edge (u, v) exists, otherwise false.
Constraints
• 1 ≤ n ≤ 105
• At most 105 operations
• No self-loops
Example 1
Input:
n = 3
["addEdge","addEdge","inDegree","outDegree"]
[[0,1],[2,1],[1],[2]]
Output:
[null,null,2,1]
11
Example 2
Input:
n = 2
["addEdge","hasEdge","removeEdge","hasEdge"]
[[0,1],[0,1],[0,1],[0,1]]
Output:
[null,true,null,false]
Example 3
Input:
n = 4
["addEdge","addEdge","removeEdge","inDegree","outDegree"]
[[0,1],[1,2],[0,1],[1],[1]]
Output:
[null,null,null,0,1]
3.9 Problem 9: Graph Edge Weight Manager
You are given an initially empty weighted undirected graph with n vertices.
Design a data structure that supports:
• addEdge(u, v, w): Adds an edge between u and v with weight w. If the edge exists, update its weight.
• removeEdge(u, v): Removes the edge if it exists.
• getWeight(u, v): Returns the weight of edge (u, v), or −1 if it does not exist.
• maxNeighborWeight(u): Returns the maximum weight among all edges incident to u. Return −1 if u has no
neighbors.
Constraints
• 1 ≤ n ≤ 105
• At most 105 operations
• 1 ≤ w ≤ 109
Example 1
Input:
n = 3
["addEdge","addEdge","getWeight","maxNeighborWeight"]
[[0,1,5],[0,2,10],[0,1],[0]]
Output:
[null,null,5,10]
Example 2
Input:
n = 2
["addEdge","addEdge","getWeight"]
[[0,1,3],[0,1,7],[0,1]]
Output:
[null,null,7]
12
Example 3
Input:
n = 2
["maxNeighborWeight","addEdge","removeEdge","maxNeighborWeight"]
[[0],[0,1,4],[0,1],[0]]
Output:
[-1,null,null,-1]
3.10 Problem 10: The Bitset Matrix
In a dense graph where n ≤ 5000, a standard int Adjacency Matrix uses O(V 2 ) space. If each int is 4 bytes, this
requires nearly 100 MB. You must optimize the storage to fit within a strict 4 MB limit.
Design a data structure that supports:
• hasEdge(u, v): Returns true if there is an edge between u and v, otherwise false.
The graph is undirected and initialized with a static list of edges.
Constraints
• 1 ≤ n ≤ 5000
• 0 ≤ | E| ≤ 107
• Maximum Memory Allowed: 4 MB
• At most 106 queries
Example 1
Input:
n = 4, edges = [[0,1], [1,2]]
["hasEdge", "hasEdge"]
[[0,1], [0,2]]
Output:
[true, false]
Example 2
Input:
n = 5, edges = [[0,4], [4,1], [2,3]]
["hasEdge", "hasEdge"]
[[4,0], [1,2]]
Output:
[true, false]
Example 3
Input:
n = 5000, edges = [[0,4999]]
["hasEdge", "hasEdge"]
[[0,4999], [1,1]]
Output:
[true, false]
3.11 Problem 11: Neighbors in a Sparse World
You are given a very large graph (n = 105 ) but with very few edges (| E| = 105 ). This is a sparse graph. You must
choose a representation that handles the high vertex count while allowing efficient neighbor enumeration.
13
Design a data structure that supports:
• neighbors(u): Returns a list of all vertices adjacent to vertex u.
The graph is undirected and initialized with a list of edges.
Constraints
• 1 ≤ n ≤ 105
• 1 ≤ | E| ≤ 105
• 0≤u<n
Example 1
Input:
n = 5, edges = [[0,1], [0,2], [0,3]]
["neighbors"]
[[0]]
Output:
[[1, 2, 3]]
Example 2
Input:
n = 10, edges = [[1,2], [2,3], [3,4]]
["neighbors"]
[[2]]
Output:
[[1, 3]]
Example 3
Input:
n = 10^5, edges = [[0, 99999]]
["neighbors"]
[[99999]]
Output:
[[0]]
3.12 Problem 12: Dynamic Weight Updates
In a weighted undirected graph, edge weights can be updated frequently. You must design a system that can
handle these updates and provide the current weight of any edge instantly.
Design a data structure that supports:
• updateWeight(u, v, w): If the edge (u, v) exists, update its weight to w. Otherwise, create the edge with
weight w.
• getWeight(u, v): Returns the current weight of edge (u, v), or −1 if it does not exist.
Constraints
• 1 ≤ n ≤ 1000
• 1 ≤ w ≤ 109
• getWeight must run in O(1) time.
14
Example 1
Input:
n = 2
["updateWeight", "updateWeight", "getWeight"]
[[0,1,500], [0,1,100], [0,1]]
Output:
[null, null, 100]
Example 2
Input:
n = 3
["updateWeight", "getWeight"]
[[1,2,50], [0,2]]
Output:
[null, -1]
Example 3
Input:
n = 10
["updateWeight", "updateWeight", "getWeight"]
[[5,5,10], [2,3,25], [2,3]]
Output:
[null, null, 25]
15