DSA Selection Sort

Welcome to TheCodingCollege.com, your one-stop destination for mastering coding and programming concepts. In this article, we will dive into Selection Sort, a simple yet important sorting algorithm in Data Structures and Algorithms (DSA).

What is Selection Sort?

Selection Sort is a comparison-based sorting algorithm that works by dividing the array into two parts:

1. A sorted portion.
2. An unsorted portion.

The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion and swaps it with the first element of the unsorted portion, gradually growing the sorted portion.

How Does Selection Sort Work?

The process involves finding the minimum element from the unsorted array and swapping it with the first element. This process is repeated for the remaining unsorted portion.

Steps in Selection Sort

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

Example of Selection Sort

Let’s sort the array [64, 25, 12, 22, 11] in ascending order.

Initial Array: [64, 25, 12, 22, 11]

Pass 1:

• Find the smallest element in [64, 25, 12, 22, 11]: 11.
• Swap 11 with 64.
• Array: [11, 25, 12, 22, 64].

Pass 2:

• Find the smallest element in [25, 12, 22, 64]: 12.
• Swap 12 with 25.
• Array: [11, 12, 25, 22, 64].

Pass 3:

• Find the smallest element in [25, 22, 64]: 22.
• Swap 22 with 25.
• Array: [11, 12, 22, 25, 64].

Pass 4:

• Find the smallest element in [25, 64]: 25.
• No swap needed.

Sorted Array: [11, 12, 22, 25, 64].

Selection Sort Code Implementation

Python Code:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the minimum element in the unsorted portion
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the found minimum element with the first element
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
array = [64, 25, 12, 22, 11]
selection_sort(array)
print("Sorted Array:", array)

Output:

Sorted Array: [11, 12, 22, 25, 64]

Java Code:

class SelectionSort {
    static void selectionSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String args[]) {
        int arr[] = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.print("Sorted Array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Time Complexity of Selection Sort

Space Complexity: O(1)O(1) (In-place sorting).

Advantages and Disadvantages of Selection Sort

Advantages

1. Simple to understand and implement.
2. Works well for small datasets.
3. In-place sorting with no additional memory required.

Disadvantages

1. Inefficient for large datasets due to O(n2)O(n^2) time complexity.
2. Performs unnecessary comparisons even if the array is already sorted.

Applications of Selection Sort

1. Small Datasets: Suitable for scenarios with limited data.
2. Learning Sorting Concepts: Helps beginners understand sorting algorithms.
3. Memory-Constrained Environments: No extra space is required, making it ideal when memory usage is critical.

Comparison with Bubble Sort

Conclusion

Selection Sort is an essential algorithm for understanding sorting concepts in DSA. Although it is not the most efficient for large datasets, its simplicity makes it a great choice for beginners. Start practicing Selection Sort and explore advanced sorting techniques on TheCodingCollege.com to level up your programming skills!