Selection Sort Solution for TCS NQT

Company: TCS NQT · Difficulty: Easy · Topics: Array, Sorting

Problem Statement

Implement the selection sort algorithm to sort an array of integers in ascending order. Selection sort is an in-place comparison sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right and a sublist of the remaining unsorted items.

Examples

Example 1:

Input: arr = [64, 25, 12, 22, 11]

Output: [11, 12, 22, 25, 64]

Explanation:

Pass 1: Find minimum (11) and swap with first element → [11, 25, 12, 22, 64]
Pass 2: Find minimum in remaining (12) and swap with second element → [11, 12, 25, 22, 64]
Pass 3: Find minimum in remaining (22) and swap with third element → [11, 12, 22, 25, 64]
Pass 4: Find minimum in remaining (25) and swap with fourth element → [11, 12, 22, 25, 64]
Pass 5: Last element (64) is already in place

Example 2:

Input: arr = [5, 2, 4, 6, 1, 3]

Output: [1, 2, 3, 4, 5, 6]

Explanation: The array is sorted by repeatedly finding the minimum element.

Example 3:

Input: arr = [1]

Output: [1]

Explanation: Single element array is already sorted.

Example 4:

Input: arr = [3, 3, 3, 3]

Output: [3, 3, 3, 3]

Explanation: Array with duplicate elements remains the same after sorting.

Intuition

Selection sort works by dividing the array into two parts:

1. Sorted region: Initially empty, grows from left to right

2. Unsorted region: Initially contains all elements, shrinks from left to right

In each iteration:

1. Find the minimum element in the unsorted region

2. Swap it with the first element of the unsorted region

3. Expand the sorted region by one element

4. Repeat until the unsorted region is empty

Approach

Approach 1: Standard Selection Sort

1. Use two nested loops

2. Outer loop runs n-1 times (we need n-1 swaps)

3. Inner loop finds the minimum element in the unsorted region

4. Swap the minimum element with the first element of unsorted region

Approach 2: Selection Sort with Index Tracking

1. Keep track of the minimum element's index instead of value

2. This can be more efficient for some cases

Approach 3: Bidirectional Selection Sort

1. Find both minimum and maximum in each pass

2. Place minimum at the beginning and maximum at the end

3. This reduces the number of passes by half

Dry Run

Let's trace through Example 1: arr = [64, 25, 12, 22, 11]

Pass 1:

Find minimum in [64, 25, 12, 22, 11]: min = 11 at index 4
Swap arr[0] with arr[4]: [11, 25, 12, 22, 64]
Sorted region: [11], Unsorted region: [25, 12, 22, 64]

Pass 2:

Find minimum in [25, 12, 22, 64]: min = 12 at index 2
Swap arr[1] with arr[2]: [11, 12, 25, 22, 64]
Sorted region: [11, 12], Unsorted region: [25, 22, 64]

Pass 3:

Find minimum in [25, 22, 64]: min = 22 at index 3
Swap arr[2] with arr[3]: [11, 12, 22, 25, 64]
Sorted region: [11, 12, 22], Unsorted region: [25, 64]

Pass 4:

Find minimum in [25, 64]: min = 25 at index 3
Swap arr[3] with arr[3]: [11, 12, 22, 25, 64] (no change)
Sorted region: [11, 12, 22, 25], Unsorted region: [64]

Pass 5:

Find minimum in [64]: min = 64 at index 4
Swap arr[4] with arr[4]: [11, 12, 22, 25, 64] (no change)
Final result: [11, 12, 22, 25, 64]

Key Insights

1. In-place: No extra space required (O(1) space complexity)

2. Unstable: May change the relative order of equal elements

3. Simple: Easy to understand and implement

4. Consistent: Always performs the same number of comparisons regardless of input

5. Inefficient: O(n²) time complexity makes it slow for large arrays

Edge Cases

1. Empty array: Return empty array

2. Single element: Return the element as is

3. Already sorted: Will still perform all comparisons

4. Reverse sorted: Will still perform all comparisons

5. Duplicate elements: Will work correctly but may not preserve order

Time and Space Complexity

Time Complexity: O(n²) in all cases (best, average, worst)
Space Complexity: O(1) - in-place sorting algorithm