Why Selection sort can be stable or unstable

Selection Sort: Understanding Stability in Sorting Algorithms

Explore the stability of Selection Sort, why it's typically unstable, and how a minor modification can make it stable, with practical examples and diagrams.

Sorting algorithms are fundamental to computer science, and understanding their properties, such as stability, is crucial. Selection Sort is a simple, in-place comparison sorting algorithm. While often considered unstable, its stability can actually depend on the specific implementation. This article delves into what stability means for a sorting algorithm, why Selection Sort is typically unstable, and how a slight modification can achieve stability.

What is Sorting Stability?

A sorting algorithm is considered stable if it preserves the relative order of equal elements. In simpler terms, if two elements have the same value, and one appears before the other in the original unsorted list, a stable sort will ensure they maintain that same relative order in the sorted list. If their relative order can change, the sort is unstable.

flowchart TD
    A[Original Array] --> B{Are there duplicate elements?}
    B -- Yes --> C{Do equal elements maintain relative order?}
    C -- Yes --> D[Stable Sort]
    C -- No --> E[Unstable Sort]
    B -- No --> F[Stability is not a concern]

Decision flow for determining sorting stability

Consider an array of objects where each object has a value and an original index (or some other identifier). For example, [(5, 'A'), (2, 'B'), (5, 'C')]. A stable sort would always place (5, 'A') before (5, 'C') in the sorted output, because 'A' appeared before 'C' in the original array. An unstable sort might place (5, 'C') before (5, 'A').

Why Standard Selection Sort is Unstable

The standard implementation of Selection Sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning of the sorted part. This process typically involves swapping the minimum element with the element at the current position. It's this swapping mechanism that introduces instability.

Let's trace an example to illustrate the instability:

Original Array: [(5, 'A'), (2, 'B'), (5, 'C')]

Pass 1:

1. Find minimum in [(5, 'A'), (2, 'B'), (5, 'C')]. The minimum is (2, 'B').
2. Swap (2, 'B') with (5, 'A') (the element at the current position, index 0).
3. Array becomes: [(2, 'B'), (5, 'A'), (5, 'C')]

Notice that (5, 'A') and (5, 'C') have maintained their relative order so far. However, if the minimum element was one of the duplicates, the swap could disrupt the order.

Consider another example where instability is more apparent:

Original Array: [(10, 'A'), (20, 'B'), (10, 'C')]

Pass 1 (index 0):

1. Minimum in [(10, 'A'), (20, 'B'), (10, 'C')] is (10, 'A') (at index 0). No swap needed as it's already in place.
2. Array: [(10, 'A'), (20, 'B'), (10, 'C')]

Pass 2 (index 1):

1. Minimum in [(20, 'B'), (10, 'C')] (unsorted part) is (10, 'C').
2. Swap (10, 'C') with (20, 'B') (element at current position, index 1).
3. Array becomes: [(10, 'A'), (10, 'C'), (20, 'B')]

Here, (10, 'A') and (10, 'C') were originally in the order 'A' then 'C'. After sorting, they are still 'A' then 'C'. This specific example appears stable, but it's due to the values and positions. The mechanism of swapping can lead to instability.

def selection_sort_unstable(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j][0] < arr[min_idx][0]: # Compare values
                min_idx = j
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Example of instability
data = [(5, 'A'), (2, 'B'), (5, 'C')]
print(f"Original: {data}")
sorted_data = selection_sort_unstable(data)
print(f"Sorted (unstable): {sorted_data}")

data2 = [(10, 'A'), (20, 'B'), (10, 'C')]
print(f"Original: {data2}")
sorted_data2 = selection_sort_unstable(data2)
print(f"Sorted (unstable): {sorted_data2}")

Standard Selection Sort implementation (Python)

Making Selection Sort Stable

To make Selection Sort stable, instead of swapping the minimum element with the element at the current position, we need to insert the minimum element into its correct place. This involves shifting all elements between the current position and the minimum element's original position one step to the right.

Let's re-trace the example [(5, 'A'), (2, 'B'), (5, 'C')] with a stable approach:

Original Array: [(5, 'A'), (2, 'B'), (5, 'C')]

Pass 1 (index 0):

1. Find minimum in [(5, 'A'), (2, 'B'), (5, 'C')]. The minimum is (2, 'B') at index 1.
2. Store (2, 'B') temporarily.
3. Shift elements from index 0 up to (but not including) index 1 one position to the right: (5, 'A') moves from index 0 to index 1.
4. Insert (2, 'B') at index 0.
5. Array becomes: [(2, 'B'), (5, 'A'), (5, 'C')]

In this case, the result is the same as the unstable version, but the mechanism is different. The key is that (5, 'A') and (5, 'C') maintain their relative order because (5, 'A') was shifted, not swapped out of place by (5, 'C').

Consider the example [(10, 'A'), (20, 'B'), (10, 'C')] again with the stable approach:

Original Array: [(10, 'A'), (20, 'B'), (10, 'C')]

Pass 1 (index 0):

1. Minimum in [(10, 'A'), (20, 'B'), (10, 'C')] is (10, 'A') at index 0.
2. No shift/insertion needed as it's already at the correct position.
3. Array: [(10, 'A'), (20, 'B'), (10, 'C')]

Pass 2 (index 1):

1. Minimum in [(20, 'B'), (10, 'C')] (unsorted part) is (10, 'C') at index 2.
2. Store (10, 'C') temporarily.
3. Shift elements from index 1 up to (but not including) index 2 one position to the right: (20, 'B') moves from index 1 to index 2.
4. Insert (10, 'C') at index 1.
5. Array becomes: [(10, 'A'), (10, 'C'), (20, 'B')]

In this stable version, (10, 'A') and (10, 'C') are now (10, 'A') then (10, 'C'). This is still stable, but the crucial difference is that the mechanism ensures stability even in cases where the unstable version would fail. For instance, if the minimum was (10, 'C') and it was swapped with (10, 'A'), the order would be reversed.

def selection_sort_stable(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j][0] < arr[min_idx][0]: # Compare values
                min_idx = j
        
        # If the minimum element is not at the current position 'i'
        # we need to shift elements to make space for it.
        if min_idx != i:
            # Store the minimum element
            min_val = arr[min_idx]
            
            # Shift elements from min_idx-1 down to i, one position to the right
            for k in range(min_idx, i, -1):
                arr[k] = arr[k-1]
            
            # Place the minimum element at position i
            arr[i] = min_val
    return arr

# Example of stable behavior
data = [(5, 'A'), (2, 'B'), (5, 'C')]
print(f"Original: {data}")
sorted_data = selection_sort_stable(data)
print(f"Sorted (stable): {sorted_data}")

data2 = [(10, 'A'), (20, 'B'), (10, 'C')]
print(f"Original: {data2}")
sorted_data2 = selection_sort_stable(data2)
print(f"Sorted (stable): {sorted_data2}")

Stable Selection Sort implementation (Python)