DSA interview question

Selection Sort

Easy · Algorithms · Topics: sorting, algorithm

The problem

A warehouse robot reorganises boxes on a shelf by weight, lightest first. Picking up and moving a box is slow and expensive, while reading a box's label is cheap. Selection sort fits this constraint: on each pass it scans the unsorted part to find the smallest item, then makes a single swap to put it in place. It always needs about n²/2 comparisons, but never more than n − 1 swaps, the fewest moves of any simple sorting algorithm. It's also the easiest algorithm to reason about, which is why it's usually the first one taught.

Example: [4, 1, 3, 9, 7] → [1, 3, 4, 7, 9].

Function signature

void selectionSort(vector<int>& a);  // sorts a in non-decreasing order, in place

Test cases

Input `a`	Output	Explanation
`[4, 1, 3, 9, 7]`	`[1, 3, 4, 7, 9]`
`[5, 2, 9, 1, 5, 6]`	`[1, 2, 5, 5, 6, 9]`	Duplicates are fine
`[3, -1, 0, -7]`	`[-7, -1, 0, 3]`	Negative values
`[1, 2, 3]`	`[1, 2, 3]`	Already sorted: still O(n²) comparisons, but no swaps
`[4, 3, 2, 1]`	`[1, 2, 3, 4]`	Reverse order
`[42]`	`[42]`
`[]`	`[]`

(Confirm: sort in place in non-decreasing order; the code also cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

"Implement selection sort."
Theory: "How does selection sort work? Is it stable? What's its complexity? When would you use it?"
Comparison questions: "Selection vs bubble vs insertion sort, which is best for nearly sorted data?"

Clarifying questions to ask

Ascending or descending?
In place, or can I return a new array?
Does stability matter (keeping equal elements in their original order)?
How large is the input? (Selection sort is only reasonable for small n.)

Follow-ups to expect

"What's the time complexity?"
"How many swaps does it make?"
"Is it stable?"
"Is it in place?"
"Can you make it stable?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview