Selection Sort Algorithm in DSA Java - Build from Scratch

Selection Sort Algorithm

📖 Scenario: You have a list of numbers that are not in order. You want to arrange them from smallest to largest, like sorting books by their height on a shelf.

🎯 Goal: Build a program that uses the Selection Sort Algorithm to sort a list of numbers in ascending order.

📋 What You'll Learn

Create an integer array called numbers with the exact values: 64, 25, 12, 22, 11

Create an integer variable called n that stores the length of the numbers array

Use nested for loops with variables i and j to implement the selection sort logic

Swap elements in the array to sort it in ascending order

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Sorting is used in many real-life situations like organizing files, arranging products by price, or sorting names alphabetically.

💼 Career

Understanding sorting algorithms like selection sort is fundamental for software development and technical interviews.

1

Create the initial array

Create an integer array called numbers with these exact values: 64, 25, 12, 22, 11

DSA Java

// Your code here

Hint

Use int[] numbers = {64, 25, 12, 22, 11}; to create the array.

2

Add array length variable

Create an integer variable called n that stores the length of the numbers array

DSA Java

public class SelectionSort {
    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};
        // Your code here
    }
}

Hint

Use int n = numbers.length; to get the array size.

3

Implement selection sort logic

Use nested for loops with variables i and j to find the minimum element and swap it with the element at index i in the numbers array

DSA Java

public class SelectionSort {
    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};
        int n = numbers.length;
        // Use nested for loops to sort the array
    }
}

Hint

Use two loops: outer loop with i, inner loop with j. Find the smallest element and swap it with numbers[i].

4

Print the sorted array

Use a for loop with variable i to print each element of the numbers array separated by spaces

DSA Java

public class SelectionSort {
    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};
        int n = numbers.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (numbers[j] < numbers[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = numbers[minIndex];
            numbers[minIndex] = numbers[i];
            numbers[i] = temp;
        }
        // Print sorted array elements separated by spaces
    }
}

Hint

Use System.out.print(numbers[i] + " "); inside a loop to print all elements.

Practice

1. What is the main idea behind the Selection Sort algorithm?

easy

A. Repeatedly find the smallest element and move it to the front

B. Divide the list into halves and sort each half recursively

C. Swap adjacent elements if they are in wrong order repeatedly

D. Use a heap data structure to sort elements efficiently

Solution

1. Step 1: Understand Selection Sort process

   Selection Sort works by finding the smallest element in the unsorted part and swapping it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Unlike divide and conquer or adjacent swaps, Selection Sort directly selects the minimum each time.

3. Final Answer:

   Repeatedly find the smallest element and move it to the front -> Option A

4. Quick Check:

   Selection Sort = Find min and swap [OK]

Hint: Selection Sort picks smallest element each pass [OK]

Common Mistakes:

• Confusing Selection Sort with Bubble Sort
• Thinking it divides the list recursively
• Assuming it uses extra data structures

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[minIndex] in Java during Selection Sort?

easy

A. arr[i] = arr[minIndex]; arr[minIndex] = arr[i];

B. swap(arr[i], arr[minIndex]);

C. temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;

D. arr[i], arr[minIndex] = arr[minIndex], arr[i];

Solution

1. Step 1: Understand Java swap syntax

   Java does not have a built-in swap function; we use a temporary variable to swap values.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; correctly uses a temporary variable. arr[i] = arr[minIndex]; arr[minIndex] = arr[i]; overwrites arr[i] before saving it. swap(arr[i], arr[minIndex]); is invalid syntax. arr[i], arr[minIndex] = arr[minIndex], arr[i]; is Python style, not Java.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; -> Option C

4. Quick Check:

   Use temp variable to swap in Java [OK]

Hint: Use temp variable to swap in Java [OK]

Common Mistakes:

• Trying to swap without temp variable
• Using Python or other language syntax
• Overwriting one element before saving it

3. What will be the output array after running Selection Sort on int[] arr = {29, 10, 14, 37, 13};?

medium

A. [10, 14, 13, 29, 37]

B. [29, 10, 14, 37, 13]

C. [13, 10, 14, 29, 37]

D. [10, 13, 14, 29, 37]

Solution

1. Step 1: Perform first pass to find minimum

   Minimum is 10, swap with 29: [10, 29, 14, 37, 13]

2. Step 2: Perform second pass to find next minimum

   Minimum in remaining is 13, swap with 29: [10, 13, 14, 37, 29]

3. Step 3: Continue sorting

   Next minimum is 14 (already in place), then 29 and 37 sorted: [10, 13, 14, 29, 37]

4. Final Answer:

   [10, 13, 14, 29, 37] -> Option D

5. Quick Check:

   Selection Sort output = sorted array [OK]

Hint: Selection Sort outputs sorted array ascending [OK]

Common Mistakes:

• Not swapping correctly after finding minimum
• Confusing indices during swaps
• Stopping sorting early

4. Consider this buggy Selection Sort snippet:

for (int i = 0; i < arr.length; i++) {
  int minIndex = i;
  for (int j = i + 1; j < arr.length; j++) {
    if (arr[j] > arr[minIndex]) {
      minIndex = j;
    }
  }
  int temp = arr[i];
  arr[i] = arr[minIndex];
  arr[minIndex] = temp;
}

What is the error?

medium

A. The inner loop condition should be j <= arr.length

B. The comparison should be arr[j] < arr[minIndex] to find minimum

C. The swap is done before finding minimum

D. The outer loop should start from 1 instead of 0

Solution

1. Step 1: Analyze the comparison in inner loop

   The code uses arr[j] > arr[minIndex], which finds the maximum, not minimum.

2. Step 2: Correct the comparison for Selection Sort

   Selection Sort requires finding the minimum, so comparison should be arr[j] < arr[minIndex].

3. Final Answer:

   The comparison should be arr[j] < arr[minIndex] to find minimum -> Option B

4. Quick Check:

   Selection Sort finds minimum, so use < comparison [OK]

Hint: Use less than to find minimum in Selection Sort [OK]

Common Mistakes:

• Using greater than instead of less than
• Changing loop bounds incorrectly
• Swapping before finding minimum

5. You want to sort an array but only partially: after Selection Sort runs for 2 passes on int[] arr = {20, 5, 15, 10, 25}, what is the array state?

hard

A. [5, 10, 15, 25, 20]

B. [5, 10, 15, 20, 25]

C. [5, 15, 10, 20, 25]

D. [5, 15, 10, 25, 20]

Solution

1. Step 1: First pass finds minimum

   Minimum is 5, swap with 20: [5, 20, 15, 10, 25]

2. Step 2: Second pass finds next minimum in remaining

   Minimum in [20, 15, 10, 25] is 10, swap with 20: [5, 10, 15, 20, 25]

3. Step 3: Array after 2 passes

   Array is [5, 10, 15, 20, 25]

4. Final Answer:

   [5, 10, 15, 25, 20] -> Option A

5. Quick Check:

   Two passes partially sort array [OK]

Hint: Each pass places one smallest element correctly [OK]

Common Mistakes:

• Not swapping correctly after each pass
• Confusing which elements are sorted
• Assuming full sort after 2 passes