Selection Sort

This article provides a concise overview of the Selection Sort algorithm. Selection Sort is one of the simplest sorting methods, and it works by repeatedly finding the minimum element from the unsorted portion of an array and placing it at the beginning.

Definition

Selection Sort is an intuitive sorting algorithm. The core idea is that for every position in the array, we find the smallest element from the remaining unsorted portion and swap it with the element at the current position. Specifically, for the i-th iteration, we select the smallest element from the subarray starting at index i and exchange it with the element originally at index i.

Imagine an animation where the algorithm gradually builds a sorted section at the beginning of the array, one element at a time, by repeatedly selecting the smallest element from the unsorted part.

Properties

Stability

The stability of Selection Sort depends largely on its implementation:

If implemented using a linked list, where insertion and deletion at any location take constant time (i.e., $O(1)$ ), it is possible to avoid swapping. In this scenario, after selecting the minimum element (choosing the first occurrence when duplicates exist), you can insert it at the beginning of the unsorted portion without disrupting the original order of equal elements. This approach preserves stability.
On the other hand, when using an array implementation, insertion and deletion at arbitrary positions incur a time cost of $O(n)$ . As a result, the typical array-based implementation relies on swapping the elements. However, swapping can disturb the relative ordering of equal elements. Therefore, the standard array implementation of Selection Sort is not stable.

Time Complexity

Selection Sort operates in quadratic time in all cases. Its best-case, average-case, and worst-case time complexities are all $O(n^2)$ .

Code Implementation

Pseudocode

Below is the pseudocode for Selection Sort:

\begin{array}{ll} 1 & \textbf{Input: An array } A \textbf{ with } n \textbf{ elements.} \\ 2 & \textbf{Output: The array } A \textbf{ sorted in nondecreasing order.} \\ 3 & \textbf{Method:} \\ 4 & \textbf{for } i \gets 1 \textbf{ to } n-1 \\ 5 & \quad \text{set } \textit{min\_index} \gets i \\ 6 & \quad \textbf{for } j \gets i+1 \textbf{ to } n \\ 7 & \quad\quad \textbf{if } A[j] < A[\textit{min\_index}] \\ 8 & \quad\quad\quad \textit{min\_index} \gets j \\ 9 & \quad \text{swap } A[i] \textbf{ and } A[\textit{min\_index}] \\ \end{array}

Python Implementation

Below is a Python example implementing Selection Sort:

def selection_sort(arr):
    """
    Sorts an array in nondecreasing order using the selection sort algorithm.
    
    Parameters:
        arr (list): The list of elements to be sorted.
    
    Returns:
        list: The sorted list.
    """
    n = len(arr)
    for i in range(n - 1):
        # Assume the current element is the smallest.
        min_index = i
        
        # Find the minimum element in the remainder of the array.
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
                
        # Swap the found minimum element with the element at index i.
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr
 
# Example usage:
if __name__ == "__main__":
    example_array = [64, 25, 12, 22, 11]
    sorted_array = selection_sort(example_array)
    print("Sorted array:", sorted_array)

In this implementation, we iterate through the list, each time finding the smallest element in the unsorted portion and swapping it with the element at the current position. This process continues until the entire list is sorted.

By understanding and implementing Selection Sort, you gain foundational insight into sorting algorithms, which is an essential step as you delve deeper into data structures and algorithms.

Role of Sorting in Data Processing Shell Sort