Selection Sort Algorithm

Selection Sort Algorithm

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest, depending on the order) element from the unsorted part of the array and placing it in its correct position in the sorted part of the array. The algorithm performs in-place sorting, meaning it doesn't require additional memory outside of the input array.

How Selection Sort Works

The basic idea of Selection Sort is to divide the array into two parts:

1. The sorted portion at the beginning of the array.
2. The unsorted portion that remains to be sorted.

In each iteration, Selection Sort finds the smallest (or largest) element from the unsorted portion of the array and swaps it with the first unsorted element, effectively growing the sorted portion.

Steps of the Algorithm:

1. Start with the first element of the array as the current position of the sorted portion.
2. Search for the smallest (or largest) element in the unsorted portion of the array.
3. Swap the smallest (or largest) element found with the element at the current position.
4. Move the boundary between the sorted and unsorted portions one step forward (i.e., move to the next element).
5. Repeat steps 2 to 4 until all elements are sorted.

Pseudocode:

for i = 0 to n-1
    min_index = i
    for j = i+1 to n
        if array[j] < array[min_index]
            min_index = j
    swap array[i] with array[min_index]

• Outer loop: It runs from 0 to n-1, where n is the size of the array. This loop controls the boundary of the sorted portion of the array.
• Inner loop: It runs from i+1 to n to find the smallest element in the unsorted portion.
• Swap: The smallest element found is swapped with the first unsorted element (at index i).

Example:

Let's walk through an example to better understand how Selection Sort works.

Suppose we have an array:
[64, 25, 12, 22, 11]

First Pass:

• The unsorted portion is [64, 25, 12, 22, 11].

• The smallest element in the unsorted portion is 11 (index 4).

• Swap 11 with the first element (index 0), so the array becomes:

  [11, 25, 12, 22, 64]

Second Pass:

• The unsorted portion is [25, 12, 22, 64].

• The smallest element is 12 (index 2).

• Swap 12 with the second element (index 1), so the array becomes:

  [11, 12, 25, 22, 64]

Third Pass:

• The unsorted portion is [25, 22, 64].

• The smallest element is 22 (index 3).

• Swap 22 with the third element (index 2), so the array becomes:

  [11, 12, 22, 25, 64]

Fourth Pass:

• The unsorted portion is [25, 64].

• The smallest element is 25 (index 3).

• Swap 25 with the fourth element (index 3), no change in the array.

  [11, 12, 22, 25, 64]

Fifth Pass:

• The unsorted portion is [64], and it's already sorted.

The array is now fully sorted:
[11, 12, 22, 25, 64]

Time Complexity:

• Best Case: O(n²)
• Worst Case: O(n²)
• Average Case: O(n²)

Explanation:

• The algorithm always requires two nested loops: the outer loop runs n times, and the inner loop runs n-1, n-2, ..., 1 times. This results in a time complexity of O(n²), regardless of whether the array is already sorted or not.
• Selection Sort is not adaptive, meaning it doesn't take advantage of already sorted portions of the array.

Space Complexity:

• Space Complexity: O(1)

Explanation:

• Selection Sort is an in-place sorting algorithm, meaning it does not require any extra space other than a few variables to keep track of indices and the current element. It sorts the array in-place with constant additional space.

Advantages of Selection Sort:

• Simplicity: Selection Sort is very easy to understand and implement.
• In-place Sorting: It does not require additional memory, which makes it space-efficient.
• No extra swaps: The algorithm only performs one swap per iteration, so it is efficient in terms of swap operations.

Disadvantages of Selection Sort:

• Inefficient for large datasets: The algorithm has a time complexity of O(n²), making it inefficient for sorting large arrays compared to more advanced algorithms like Merge Sort or Quick Sort.
• Not adaptive: Selection Sort does not adapt to the input data and will always run in O(n²) time regardless of the initial order of the array.
• Not stable: It is not a stable sorting algorithm, meaning that equal elements may not retain their relative order after sorting.

Conclusion:

Selection Sort is a very simple but inefficient algorithm, particularly for large arrays. It is more suitable for small datasets or as a teaching tool to understand basic sorting principles. For practical use on large datasets, more efficient algorithms like Quick Sort, Merge Sort, or Heap Sort are preferred.