SCTR’s Pune Institute of Computer Technology
Department of Computer Engineering
Laboratory Manual
Course: Data Structures Lab (DSL) Class: S.Y. B. Tech.
Assignment No: 02
An E-commerce website has a range of products having Product id, name,
manufacturer, price and quality rating out of 5. Write a C++/Java Program
to display products as…
Title/Problem 1. In Increasing order of Product id (Use Bubble Sort)
Statement:
2. In Increasing order of Product price (Use Selection Sort)
3. In Decreasing order of Product Quality Rating (Insertion
Sort)
The students will learn…
Learning 1. To understand Bubble, Selection and Insertion Sort Algorithms.
Objectives: 2. To use class, objects and array for storing products details.
3. To compute the Time and Space Complexities of Algorithms.
The students will be able…
Learning 1. To implement Bubble, Selection and Insertion Sort Algorithms.
Outcomes: 2. To write class, objects and array for storing products list.
3. To analyze the Time and Space Complexities of Sorting Algorithms.
OS/Programming
OS FOSS-Ubuntu20, Fedora32,33. Tools: Eclipse, VScode.
tools used:
A] Theory:
This assignment needs a class (Products) and its array of objects to store details of products
as Product id, name, manufacturer, price and quality rating out of 5. (Data Members) along with
Bubble, Selection and Insertion Sort functions (Member Functions) as given below.
Class Products
{
int Prod_id; //………….. Data Members
char Prod_name[10];
char Manufacturer[10];
int Price;
int Quality;
public:
void bubble_Sort(); // Member Functions
void selection_Sort();
void insertion_Sort();
}List[10]; //……..……Array of Objects/List of Products
Class
Think of a class as a blueprint or template.
It defines the structure and behavior (properties and methods) that the objects created from
the class will have.
For example, a class called Car might define properties like color, model, and methods
like drive() or stop().
Object
An object is an instance of a class.
It’s a specific example created using the class blueprint.
For example, if Car is the class, then your red Toyota Corolla is an object of the class Car.
Each object has its own values for the properties defined by the class.
Quick analogy:
Class: A cookie cutter shape.
Object: A cookie made using that cookie cutter.
What is an array of objects?
It’s like a container (an array, list, or similar data structure) that stores multiple objects.
Each element in this array is an object created from a class.
You can access each object in the array using an index and call its methods or access its
properties.
Why use an array of objects?
To manage and organize many objects easily.
Example: Suppose you have a Student class and want to store multiple student objects in
one place — an array of Student objects is perfect.
Here we have range of products having their details as Product id, name, manufacturer,
price and quality rating out of 5. So one Object will store details of one product.
B] Algorithms:
1. Bubble Sort:
Here’s the explanation of the Bubble Sort algorithm along with its pseudo-code:
🔹 Bubble Sort Algorithm (Explanation)
Bubble Sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements
if they are in the wrong order. This process is repeated until the list is sorted.
Steps:
1. Start from the first element and compare it with the next.
2. If the first element is greater than the second, swap them.
3. Move to the next pair and repeat step 2 until the end of the array.
4. Repeat the entire process for all elements until no swaps are needed.
Pseudo-code
procedure bubble_Sort(A)
n ← length(A)
repeat
swapped ← false
for i ← 1 to n - 1 do
if A[i - 1] > A[i] then
swap A[i - 1] and A[i]
swapped ← true
end if
end for
until not swapped
end procedure
Bubble Sort Example:
Given Array: [5, 1, 4, 2, 8]
How Bubble Sort Works:
Pass 1:
Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
Compare 5 and 8 → no swap
Pass 2:
Compare 1 and 4 → no swap
Compare 4 and 2 → swap → [1, 2, 4, 5, 8]
Compare 4 and 5 → no swap
Pass 3:
Compare 1 and 2 → no swap
Compare 2 and 4 → no swap
Pass 4:
All elements already in order → loop ends early
Final sorted array: [1, 2, 4, 5, 8]
Output
Original array: 5, 1, 4, 2, 8
Sorted array: 1, 2, 4, 5, 8
2. Selection Sort:
Here's the explanation of the Selection Sort algorithm, along with its pseudo-code:
🔹 Selection Sort Algorithm (Explanation)
Selection Sort works by repeatedly finding the minimum element from the unsorted portion of the
array and placing it at the beginning.
Steps:
1. Start with the first element. Assume it's the minimum.
2. Compare it with the rest of the array to find the true minimum.
3. Swap the minimum element with the first element.
4. Repeat the process for the next position, treating the previous elements as sorted.
🔹 Pseudo-code
procedure selection_Sort(A)
n ← length(A)
for i ← 0 to n - 2 do
minIndex ← i
for j ← i + 1 to n - 1 do
if A[j] < A[minIndex] then
minIndex ← j
end if
end for
if minIndex ≠ i then
swap A[i] and A[minIndex]
end if
end for
end procedure
Selection Sort Example
Given Array: [29, 10, 14, 37, 13]
🔹 How Selection Sort Works Step-by-Step:
Pass 1:
Find the smallest from index 0 to 4 → smallest is 10
Swap 29 and 10 → [10, 29, 14, 37, 13]
Pass 2:
Find the smallest from index 1 to 4 → smallest is 13
Swap 29 and 13 → [10, 13, 14, 37, 29]
Pass 3:
Find the smallest from index 2 to 4 → smallest is 14 (already in place)
No swap → [10, 13, 14, 37, 29]
Pass 4:
Find the smallest from index 3 to 4 → smallest is 29
Swap 37 and 29 → [10, 13, 14, 29, 37]
Final sorted array: [10, 13, 14, 29, 37]
Output:
Original array: 29 10 14 37 13
Sorted array: 10 13 14 29 37
3. Insertion Sort:
Here's a complete breakdown of the Insertion Sort algorithm, including its algorithm explanation
and pseudo-code:
🔹 Insertion Sort Algorithm (Explanation)
Insertion Sort works similarly to how you sort playing cards in your hand:
1. Start with the second element.
2. Compare it to the elements before it.
3. Insert it into the correct position by shifting larger elements one position to the right.
4. Repeat until the array is sorted.
🔹 Pseudo-code
procedure insertion_Sort(A)
n ← length(A)
for i ← 1 to n - 1 do
key ← A[i]
j←i-1
while j ≥ 0 and A[j] > key do
A[j + 1] ← A[j]
j←j-1
end while
A[j + 1] ← key
end for
end procedure
Insertion Sort Example
Given Array: [9, 5, 1, 4, 3]
🔹 Step-by-Step Explanation
We start from the second element and insert each element into its correct position in the sorted part
of the array.
Pass 1 (i = 1):
key = 5, compare with 9 → shift 9
Insert 5 before 9
→ [5, 9, 1, 4, 3]
Pass 2 (i = 2):
key = 1, compare with 9 → shift 9
compare with 5 → shift 5
Insert 1 before 5
→ [1, 5, 9, 4, 3]
Pass 3 (i = 3):
key = 4, compare with 9 → shift 9
compare with 5 → shift 5
Insert 4 before 5
→ [1, 4, 5, 9, 3]
Pass 4 (i = 4):
key = 3, compare with 9 → shift 9
compare with 5 → shift 5
compare with 4 → shift 4
Insert 3 before 4
→ [1, 3, 4, 5, 9]
Final Sorted Array: [1, 3, 4, 5, 9]
Output
Original array: 9 5 1 4 3
Sorted array: 1 3 4 5 9
Time and Space Complexity:
🔹 1. Bubble Sort
Case Time Complexity Explanation
Best Case O(n) When the array is already sorted (optimized version)
Average O(n²) Two nested loops required
Worst Case O(n²) When the array is in reverse order
Case Time Complexity Explanation
Space O(1) In-place sorting, no extra space used
🔹 2. Selection Sort
Case Time Complexity Explanation
Best Case O(n²) Always scans the full array
Average O(n²) No early stopping
Worst Case O(n²) Always scans full array to find min
Space O(1) In-place sorting
🔹 3. Insertion Sort
Case Time Complexity Explanation
Best Case O(n) When the array is already sorted
Average O(n²) Shifts half of the elements on average
Worst Case O(n²) When the array is in reverse order
Space O(1) In-place sorting
🔹 Summary Table
Algorithm Best Time Average Time Worst Time Space
Algorithm Best Time Average Time Worst Time Space
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Notes: All three are in-place algorithms (no extra memory).
Conclusion: In this way the products details stored in object array are sorted based on different
parameters using Bubble, Selection and Insertion Sort Algorithms.
Review Questions:
1. What is the use of class and object in Object Oriented Programming?
2. When we need to use array of objects for problem solving?
3. What is the difference between Bubble Sort and Selection Sort?
4. Explain the Time and Space complexity of Sorting Algorithms?
5. Write Quick Sort Algorithm? How it works?
