Selection Sort: Step-by-Step Guide with Example Code

Selection Sort: A Simple Way to Sort Numbers

Selection Sort is an algorithm that sorts an array by repeatedly selecting the smallest element from the unsorted part of the array and swapping it into its correct position. It’s simple, intuitive, and often used for small datasets.

Step-by-Step Example of Selection Sort:

Let’s sort this array:
[5, 3, 8, 4, 2]

1. Step 1: Find the smallest element in the array: 2.
   • Swap 2 with 5 (first element).
   • Array after step: [2, 3, 8, 4, 5]
2. Step 2: Find the smallest element in the remaining array: 3.
   • No swap needed since 3 is already in place.
   • Array stays: [2, 3, 8, 4, 5]
3. Step 3: Find the smallest element in the remaining unsorted part: 4.
   • Swap 4 with 8.
   • Array after step: [2, 3, 4, 8, 5]
4. Step 4: Find the smallest element in the remaining part: 5.
   • Swap 5 with 8.
   • Array after step: [2, 3, 4, 5, 8]
5. Step 5: Only one element left, so no more swaps are needed.
   • Final sorted array: [2, 3, 4, 5, 8]

Key Points:

• Selection Sort works by finding the minimum element in the unsorted portion and placing it in its correct position.
• Time Complexity: O(n²) for the best, average, and worst cases.
• Space Complexity: O(1) (in-place sorting).
• Easy to understand but inefficient for large datasets.

Pros of Selection Sort:

• Simple and easy to implement.
• In-place sorting, meaning it doesn’t require extra space apart from the array.
• Good for small datasets where the cost of comparison is minimal.

Cons of Selection Sort:

• Inefficient for large datasets due to its O(n²) time complexity.
• Does not adapt to partially sorted data—always performs the same number of comparisons regardless of the array’s order.

Java Code for Selection Sort:

Step-by-Step Explanation:

1. Array Initialization:

int[] arr = {5, 3, 8, 4, 2};

This creates an array of numbers that we want to sort. In our case, the array is {5, 3, 8, 4, 2}. These are the elements we will be sorting using the Selection Sort algorithm.

2. The selectionSort Method:

public static void selectionSort(int[] arr) {

This method does the sorting. It takes the array arr as input and sorts it in ascending order using the Selection Sort algorithm.

3. Outer Loop (Iterating Over Array Elements):

for (int i = 0; i < n - 1; i++) {

The outer loop controls how many times we go through the array. We need to repeat the sorting process n-1 times (where n is the size of the array). This ensures that after each pass, the next smallest element gets placed in its correct position.

4. Inner Loop (Finding the Minimum Element):

for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[minIndex]) {
        minIndex = j;
    }
}

The inner loop compares each element in the unsorted part of the array (starting from index i + 1) to find the smallest element. It updates the minIndex whenever a smaller element is found.

5. Swapping Elements:

if (minIndex != i) {
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

After the inner loop, if the smallest element isn’t already in the current position (i.e., minIndex != i), we swap the smallest element (found at minIndex) with the element at index i. This places the smallest element in its correct sorted position.

6. Printing the Array:

public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

This method prints the array to the console so you can see the result before and after sorting. It loops through the array and prints each element followed by a space.

How the Code Works:

Start with the Unsorted Array: {5, 3, 8, 4, 2}

First Pass (Outer Loop – 1st Run, i = 0):

We need to find the smallest element between index 0 and 4.

• Compare 5 and 3:
  3 is smaller, so minIndex becomes 1.
• Compare 3 and 8:
  No change (3 is still the smallest).
• Compare 3 and 4:
  No change (3 is still the smallest).
• Compare 3 and 2:
  2 is smaller, so minIndex becomes 4.

Swap 5 and 2:
Array after swap: {2, 3, 8, 4, 5}

Second Pass (Outer Loop – 2nd Run, i = 1):

Find the smallest element between index 1 and 4.

• Compare 3 and 8:
  No change (3 is the smallest).
• Compare 3 and 4:
  No change (3 is still the smallest).
• Compare 3 and 5:
  No change (3 is still the smallest).

No swap needed:
Array remains {2, 3, 8, 4, 5}

Third Pass (Outer Loop – 3rd Run, i = 2):

Find the smallest element between index 2 and 4.

• Compare 8 and 4:
  4 is smaller, so minIndex becomes 3.
• Compare 4 and 5:
  No change (4 is the smallest).

Swap 8 and 4:
Array after swap: {2, 3, 4, 8, 5}

Fourth Pass (Outer Loop – 4th Run, i = 3):

Find the smallest element between index 3 and 4.

• Compare 8 and 5:
  5 is smaller, so minIndex becomes 4.

Swap 8 and 5:
Array after swap: {2, 3, 4, 5, 8}

Final Sorted Array:

{2, 3, 4, 5, 8}

Visualization provided by VisuAlgo

Visualization provided by Wikimedia Commons

Let’s Discuss the Time and Space Complexity of the Selection Sort Algorithm

Time Complexity

Time complexity describes how the algorithm’s runtime changes as the input size grows. Let’s analyze the time complexity of Selection Sort in detail:

1. Best Case (Already Sorted):

• If the array is already sorted, Selection Sort still goes through all comparisons because it doesn’t check if the array is sorted during execution.
• Outer Loop: Runs n-1 times.
• Inner Loop: Compares all elements to find the smallest.
• Complexity: O(n²) (even if the array is sorted, all comparisons are still made).

2. Average Case:

• On average, the algorithm performs a significant number of comparisons, but swaps occur less frequently than in Bubble Sort.
• Total Comparisons: Approximately n(n−1)\2.
• Swaps: Only n-1 swaps are performed in total.
• Complexity: O(n²).

3. Worst Case (Reverse Sorted):

• If the array is in descending order, Selection Sort performs the maximum number of comparisons but still only n-1 swaps.
• Outer Loop: Runs n-1 times.
• Inner Loop: Each pass finds the smallest element from the unsorted part.
• Complexity: O(n²).

Space Complexity

Space complexity refers to the amount of extra memory the algorithm uses.

• Selection Sort does not require any additional storage beyond the input array.
• Only a temporary variable (for swapping) is needed.
• Complexity: O(1) (constant space).

Summary Table

Comparison with Other Sorting Algorithms

• Efficient for Small Arrays:
  Selection Sort is simple to understand and implement, making it suitable for small datasets or educational purposes.
• Not Suitable for Large Arrays:
  Due to its O(n²) time complexity, Selection Sort is inefficient for large datasets compared to more advanced algorithms like:
  • Merge Sort: O(n log n)
  • Quick Sort: O(n log n)

Summary:

• Selection Sort repeatedly finds the smallest element in the unsorted portion of the array and places it in its correct position.
• Unlike Bubble Sort, it minimizes the number of swaps (only n-1 swaps) but performs the same number of comparisons.
• Best for small arrays, but not efficient for large data sets due to its quadratic time complexity.

Bubble Sorting