Area 05 · Data structures and algorithms
Sort and search lab
Sort a list of integers with your own insertion sort, then compare how much work binary and linear search do to find values.
- Spec no.
- HO-09
- Level
- Warm-up
- Time box
- 1 h
- Reference
- Java · C#
- Grading
- Self-assessed · rubric is ours, not DICT's
01 Coverage
| Area | Sub-skills practised | Role |
|---|---|---|
| 01 Data manipulation | Array handling, Validation | Also |
| 05 Data structures and algorithms | Sorting, Searching, Complexity | Primary |
Sign up to start coding practice
Read the task freely. An account is required before editing and running a solution. Code runs also need an internet connection.
Sign up or sign in02 Requirements
- Line 1 holds integers separated by spaces. Print Ignored: x for each token that is not an integer.
- Sort with your own insertion sort (no library sort) and print Sorted: followed by the values.
- For each find v line, run a binary search and a linear search on the sorted array.
- Count binary probes (middle elements looked at) and linear checks (elements compared until found, or all of them).
- Print v: index i (binary probes p, linear checks c) or v: not found (...).
03 Input and output
- Line 1: integers
- Then find v lines
- Ignored lines
- Sorted: ...
- One result line per find
42 7 19 x 3 88 25 61
find 25
find 50
find 3Ignored: x
Sorted: 3 7 19 25 42 61 88
25: index 3 (binary probes 1, linear checks 4)
50: not found (binary probes 3, linear checks 7)
3: index 0 (binary probes 3, linear checks 1)Match the sample exactly first, then write at least two test inputs of your own.
04 Edge cases to test
- The smallest value (binary needs several probes; linear needs one)
- A value bigger than all
- An empty list
- A non-numeric find value
05 Starter outline and hints
parse tokens → list (report bad ones) → arrayinsertionSort(a)for each find: binarySearch with probe count; linearChecksprint
Hint 1
Insertion sort: take a[i], shift bigger elements right, drop it into the gap.
06 Practice rubric
| Criterion | Sub-skills | Look for | Pts |
|---|---|---|---|
| Insertion sort | Sorting | Correct, in place, no library call. | 30 |
| Binary search | Searching | Right index, right probe count, no overflow in the midpoint. | 30 |
| Linear search and counts | SearchingComplexity | Counts match the sample, including not-found. | 20 |
| Parsing | ValidationArray handling | Bad tokens reported and skipped. | 20 |
| Total | 100 | ||
Our own weighting for practice. It is not the DICT scoring scheme.
07 Self-check
Tick only what you have verified by running your own program.
Loading saved checks…
08 Reference solution
Both versions compiled and reproduced the sample output on Java 21 and .NET 8 when this site was built. Reference solutions are in Java and C#. The 2023 FAQ copy also lists C, C++ and Visual Basic 6.0 / .NET; the same structure carries over, but you will need your language's own file and database APIs.
Try the whole brief first. The reference is one correct approach, not the only one, and reading it early removes most of the practice value.
09 Exam-day habits
- Work without internet search to simulate exam conditions.
- Type the sample input yourself and compare your output line by line before you look at the reference.