Selection Sort - potatoscript/dsa GitHub Wiki

🧩 Selection Sort – The Picker

Selection Sort is an intuitive yet inefficient sorting algorithm. It works by repeatedly finding the smallest (or largest) element from the unsorted portion of the list and swapping it with the first unsorted element. The algorithm's name comes from the fact that it "selects" the smallest element from the remaining unsorted part of the array and places it in the correct position.

While Selection Sort is easy to understand and implement, it’s not very efficient for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort. However, it’s a good starting point for understanding sorting concepts.

---

📖 How Does Selection Sort Work?

Step-by-Step Explanation:

1. Start with the first element in the array.
2. Find the smallest element in the unsorted portion of the array.
3. Swap the smallest element found with the first element.
4. Move the "boundary" of the sorted portion one step forward.
5. Repeat steps 1-4 for the remaining unsorted portion until the entire list is sorted.

---

🚀 Example of Selection Sort

Let’s take an unsorted array to demonstrate the Selection Sort algorithm:

[5, 2, 9, 1, 5, 6]

Step-by-Step Walkthrough:

1. First pass:

   • Start with the entire array: [5, 2, 9, 1, 5, 6]
   • The smallest element in the entire array is 1.
   • Swap 1 with the first element, 5:
     Array becomes: [1, 2, 9, 5, 5, 6]

2. Second pass:

   • Now, consider the sub-array [2, 9, 5, 5, 6] (ignoring the first element, 1).
   • The smallest element is 2.
   • No need to swap since 2 is already in its correct position.
   • Array remains: [1, 2, 9, 5, 5, 6]

3. Third pass:

   • Now, consider the sub-array [9, 5, 5, 6].
   • The smallest element is 5.
   • Swap 9 with 5:
     Array becomes: [1, 2, 5, 9, 5, 6]

4. Fourth pass:

   • Now, consider the sub-array [9, 5, 6].
   • The smallest element is 5.
   • Swap 9 with 5:
     Array becomes: [1, 2, 5, 5, 9, 6]

5. Fifth pass:

   • Now, consider the sub-array [9, 6].
   • The smallest element is 6.
   • Swap 9 with 6:
     Array becomes: [1, 2, 5, 5, 6, 9]

6. Sixth pass:

   • Now, consider the sub-array [9], which is already sorted, so no swaps are needed.

The final sorted array is:

[1, 2, 5, 5, 6, 9]

---

🧑‍💻 C# Code for Selection Sort

Here is the C# implementation of Selection Sort:

using System;

public class SelectionSortExample
{
    // Method for Selection Sort
    public static void SelectionSort(int[] arr)
    {
        int n = arr.Length;
        
        // Loop through each element
        for (int i = 0; i < n - 1; i++)
        {
            int minIndex = i;
            
            // Find the smallest element in the remaining unsorted array
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            
            // Swap the smallest found element with the element at position i
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    // Main method to run and test Selection Sort
    public static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 5, 6 };
        
        Console.WriteLine("Unsorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
        
        // Call the SelectionSort method
        SelectionSort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
    }
}

🧑‍💻 Explanation of Code:

1. The method SelectionSort takes an integer array as input.
2. The first loop iterates over each element of the array, treating each element as the "boundary" between the sorted and unsorted portions.
3. The second loop finds the smallest element in the unsorted portion and swaps it with the current boundary element.
4. The process repeats until the entire array is sorted.

🧑‍💻 Output:

When you run the code, the output will look like this:

Unsorted array:
5 2 9 1 5 6 

Sorted array:
1 2 5 5 6 9 

---

📊 Time Complexity of Selection Sort

• Best Case: O(n²) – This is the case when the array is already sorted. Selection Sort still compares every element, resulting in quadratic time complexity.
• Worst Case: O(n²) – This is the case when the array is sorted in reverse order. Even in this case, Selection Sort performs the same number of comparisons and swaps.
• Average Case: O(n²) – On average, Selection Sort will take quadratic time because it always performs a fixed number of comparisons, regardless of the array's initial state.

💡 Space Complexity of Selection Sort

• Space Complexity: O(1) – Selection Sort is an in-place sorting algorithm, meaning it does not require additional space to sort the array. It swaps elements within the array itself.

---

⚡ Why Use Selection Sort?

While Selection Sort is not the most efficient sorting algorithm, it has some advantages:

• Simplicity: It is easy to understand and implement, making it great for educational purposes.
• Constant Space: It only requires a constant amount of extra space, so it’s memory efficient.
• No Extra Memory: Unlike algorithms like Merge Sort or Quick Sort, it doesn't need additional arrays or data structures, making it good for environments with memory constraints.

However, for large datasets, you may want to consider more efficient algorithms like Merge Sort, Quick Sort, or Heap Sort.

---