Duration | Language | Tools | Linked Lecture |
|---|---|---|---|
50 minutes | C++ | Dev-C++ or Code::Blocks (online compiler as backup) | Lecture 20 (and 17–18) |
Mapped outcomes: CLO1 (problem solving) and CLO4 (C++ syntax and semantics) at psychomotor level P3 – Guided Response · PLO2, PLO3, PLO5
1. Lab Objectives
By the end of this 50-minute lab, you will be able to:
- Trace bubble sort and selection sort pass by pass.
- Write bubble sort (with the swapped flag) and selection sort in ascending and descending order.
- Use a sorted array to read the lowest, highest, median and top values.
- Sort two related arrays together so the pairs stay matched.
2. Word Bank
Word | Simple meaning | Real-world example |
|---|---|---|
Sort | Arrange in order | The UAF merit list |
Swap | Exchange two values using temp | Two students changing seats |
Pass | One full run of the inner loop | One walk along the line of students |
Median | The middle value of a sorted list | The middle mark of a class |
Parallel arrays | Two arrays where index i belongs to the same item | roll[i] and agg[i] of one applicant |
3. Background
Reminder // bubble sort (ascending) for (int pass = 1; pass < n; pass++) for (int j = 0; j < n - pass; j++) if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
// selection sort (ascending) for (int i = 0; i < n - 1; i++) { int minPos = i; for (int j = i + 1; j < n; j++) if (a[j] < a[minPos]) minPos = j; int t = a[i]; a[i] = a[minPos]; a[minPos] = t; } |
4. Time Plan (50 minutes)
Part | Activity | Time |
|---|---|---|
— | Briefing | 2 min |
A | Warm-up trace | 3 min |
B | Predict the output | 4 min |
C | Bug hunt (3 bugs) | 5 min |
D | Graded tasks 1–3 | 32 min |
E | Post-lab questions & submission | 4 min |
Part A: Warm-up Trace (3 min)
lab14_warmup.cpp #include <iostream> using namespace std;
int main() { int a[5] = {5, 1, 4, 2, 8}; for (int j = 0; j < 4; j++) { // one pass only if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } for (int k = 0; k < 5; k++) cout << a[k] << " "; cout << endl; return 0; } |
Write the array after each comparison (j = 0 … 3) and the output |
Part B: Predict the Output (4 min)
lab14_predict.cpp #include <iostream> using namespace std;
int main() { int a[5] = {29, 10, 14, 37, 13}; for (int i = 0; i < 2; i++) { // only two passes int minPos = i; for (int j = i + 1; j < 5; j++) if (a[j] < a[minPos]) minPos = j; int temp = a[i]; a[i] = a[minPos]; a[minPos] = temp; for (int k = 0; k < 5; k++) cout << a[k] << " "; cout << endl; } return 0; } |
My prediction (two lines) |
Part C: Bug Hunt (5 min)
bug1.cpp — not fully sorted
#include <iostream> using namespace std;
int main() { int a[5] = {5, 4, 3, 2, 1}; for (int pass = 1; pass < 4; pass++) for (int j = 0; j < 5 - pass; j++) if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } for (int k = 0; k < 5; k++) cout << a[k] << " "; cout << endl; return 0; } |
Wrong output, cause and fix |
bug2.cpp — values lost
#include <iostream> using namespace std;
int main() { int a[5] = {40, 10, 30, 20, 50}; for (int pass = 1; pass < 5; pass++) for (int j = 0; j < 5 - pass; j++) if (a[j] > a[j + 1]) { a[j] = a[j + 1]; a[j + 1] = a[j]; } for (int k = 0; k < 5; k++) cout << a[k] << " "; cout << endl; return 0; } |
Wrong output, cause and fix |
bug3.cpp — wrong selection sort
#include <iostream> using namespace std;
int main() { int a[5] = {29, 10, 14, 37, 13}; int minPos = 0; for (int i = 0; i < 4; i++) { for (int j = i + 1; j < 5; j++) if (a[j] < a[minPos]) minPos = j; int temp = a[i]; a[i] = a[minPos]; a[minPos] = temp; } for (int k = 0; k < 5; k++) cout << a[k] << " "; cout << endl; return 0; } |
Wrong output, cause and fix |
Part D: Graded Lab Tasks (32 min · 10 marks)
Rules Swap with a temp variable. Print the array after sorting to check your work. Save as lab14_task1.cpp, lab14_task2.cpp, lab14_task3.cpp. |
Task 1: Sorted Marks and the Median (Easy — 3 marks)
Read n (1–20, validated) and n marks (0–100, validated). Sort them in ascending order with bubble sort using the swapped flag. Print the sorted list, the lowest and highest marks and the median (the middle value for odd n; the average of the two middle values for even n).
Sample run 1 (even n) Number of students (1-20): 6 Marks 1: 72 Marks 2: 45 Marks 3: 105 Marks 3: 91 Marks 4: 66 Marks 5: 58 Marks 6: 84 Sorted: 45 58 66 72 84 91 Lowest: 45, highest: 91 Median: 69 |
Sample run 2 (odd n) Number of students (1-20): 5 Marks 1: 72 Marks 2: 45 Marks 3: 91 Marks 4: 66 Marks 5: 58 Sorted: 45 58 66 72 91 Lowest: 45, highest: 91 Median: 66 |
Task 2: Price List, Most Expensive First (Medium — 3 marks)
A mobile-accessories shop on Circular Road has 8 items. Read their prices (more than 0, validated) and sort them largest first with selection sort (search for the maximum). Print the sorted list, the three most expensive and the three cheapest prices.
Sample run Price of item 1 (Rs.): 1200 Price of item 2 (Rs.): 450 Price of item 3 (Rs.): 0 Price of item 3 (Rs.): 3800 Price of item 4 (Rs.): 799 Price of item 5 (Rs.): 2500 Price of item 6 (Rs.): 150 Price of item 7 (Rs.): 999 Price of item 8 (Rs.): 620 Most expensive first: 3800 2500 1200 999 799 620 450 150 Top 3: 3800, 2500, 1200 Cheapest 3: 150, 450, 620 |
Task 3: Admission Merit List (Challenge — 4 marks)
Read n applicants (1–15, validated). For each, read the roll number and aggregate % (0–100; ask again if invalid). Sort by aggregate highest first, moving the roll numbers with their aggregates. Print a merit list with rank, roll number and aggregate (2 decimals), then the closing merit (the aggregate of rank 3, or of the last rank if there are fewer than 3 applicants).
Sample run Number of applicants (1-15): 5 Roll number and aggregate % of applicant 1: 2101 78.45 Roll number and aggregate % of applicant 2: 2104 85.10 Roll number and aggregate % of applicant 3: 2109 101 Aggregate must be 0-100. Enter it again: 69.80 Roll number and aggregate % of applicant 4: 2113 91.25 Roll number and aggregate % of applicant 5: 2118 82.60 MERIT LIST Rank Roll Aggregate 1 2113 91.25 2 2104 85.10 3 2118 82.60 4 2101 78.45 5 2109 69.80 Closing merit (rank 3): 82.60 |
Part E: Post-Lab Questions (finish as homework if needed)
Q1. In Task 1, how many passes does your program use for marks that are already in order? Why?
Answer |
Q2. Why must the roll numbers be swapped in Task 3 at the same time as the aggregates?
Answer |
Q3. How many comparisons does selection sort make for 8 prices? Show the sum.
Answer |
Marking Rubric (10 marks)
Component | Marks | What earns full marks |
|---|---|---|
Task 1 | 3 | Validated input; bubble sort with flag; lowest, highest, median (odd and even). |
Task 2 | 3 | Selection sort for the maximum; correct top 3 and cheapest 3. |
Task 3 | 4 | Parallel arrays sorted together; neat merit list; closing merit. |
Parts A–C and the post-lab questions are checked in the viva. A program that does not compile gets at most half marks for that task.
Submission
- Show your running programs to the instructor before leaving.
- Copy the final code and outputs into your Lab Book (Practical 14 pages).
- Copying code from a classmate gets zero marks for both students.
Next practical: Practical 15 — Two-Dimensional Arrays (Matrices) (this week). |