Selection Sort

Selection Sort Algorithm

The Selection Sort algorithm is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and swapping it with the element at the beginning of the sorted part. This process is repeated until the entire list is sorted.

Here is the step-by-step explanation of the Selection Sort algorithm:

1. Start with an unsorted list of elements.
2. Set the first element as the current minimum.
3. Compare the current minimum with the next element in the list.
4. If the next element is smaller than the current minimum, update the current minimum to the next element.
5. Repeat steps 3-4 for the remaining elements in the list, finding the new minimum if a smaller element is encountered.
6. After iterating through the entire list, swap the current minimum with the first element of the unsorted part.
7. Move the boundary of the sorted and unsorted parts by incrementing the index of the sorted part.
8. Repeat steps 2-7 until the entire list is sorted.

Here is an example to illustrate the Selection Sort algorithm:

Consider an unsorted list: [5, 2, 9, 1, 3]

First iteration:

• The current minimum is 5 (at index 0).
• Compare 5 with 2, 9, 1, and 3. The minimum is still 2.
• Swap 5 with 2, resulting in [2, 5, 9, 1, 3].

Second iteration:

• The current minimum is 5 (at index 1).
• Compare 5 with 9, 1, and 3. The minimum is 1.
• Swap 5 with 1, resulting in [2, 1, 9, 5, 3].

Third iteration:

• The current minimum is 9 (at index 2).
• Compare 9 with 5 and 3. The minimum is still 3.
• Swap 9 with 3, resulting in [2, 1, 3, 5, 9].

Fourth iteration:

• The current minimum is 5 (at index 3).
• Compare 5 with 9. The minimum remains the same.
• No swap is needed.

Fifth iteration:

• The current minimum is 9 (at index 4).
• No comparisons are needed since it is the last element.

The sorted list is [1, 2, 3, 5, 9].

This process continues until the entire list is sorted. The smallest element is repeatedly found and swapped with the element at the beginning of the unsorted part, gradually building the sorted part of the list.

It’s important to note that Selection Sort is not the most efficient sorting algorithm, especially for large lists, as it has a quadratic time complexity. However, it is easy to understand and implement, making it suitable for small lists or educational purposes.

Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and placing it at the beginning. It divides the list into two parts: the sorted part at the left end and the unsorted part at the right end.

Here’s how Selection Sort works step-by-step with an example:

Suppose we have an unsorted list of integers: [5, 2, 8, 3, 1].

Start with the first element of the list. Assume it is the minimum element for now.

Iterate through the remaining unsorted part of the list and compare each element with the assumed minimum. If you find a smaller element, update the minimum element to the new value.

In our example, we compare 5 with 2, and since 2 is smaller, we update the minimum element to 2.

After iterating through the unsorted part, we have found the actual minimum element. Swap this minimum element with the first element of the unsorted part.

In our example, we swap 5 and 2, resulting in [2, 5, 8, 3, 1].

Now, the first element is in its correct position in the sorted part. Move to the next element (previously the second element) of the unsorted part and repeat steps 2-4.

In our example, we compare 5, 8, 3, and 1 with the remaining unsorted part and find that 1 is the smallest element. We swap 5 and 1, resulting in [1, 2, 8, 3, 5].

Repeat steps 2-4 until the entire list is sorted.

Using Selection Sort, the example list [5, 2, 8, 3, 1] would be sorted as follows:

Pass 1: [1, 2, 8, 3, 5]
Pass 2: [1, 2, 8, 3, 5]
Pass 3: [1, 2, 3, 8, 5]
Pass 4: [1, 2, 3, 5, 8]

In this case, it took four passes to sort the list completely. Selection Sort has a worst-case time complexity of O(n^2), where n is the number of elements in the list. Similar to Bubble Sort, it is not very efficient for large lists but can be useful for small datasets or partially sorted lists.

Code snippet

// Initial array
[10, 5, 2, 1, 8, 7, 3, 6, 4]

// Find the smallest number and swap it with the number at index 0
[2, 5, 10, 1, 8, 7, 3, 6, 4]

// Find the smallest number and swap it with the number at index 1
[2, 1, 10, 5, 8, 7, 3, 6, 4]

// Continue until the array is sorted
[1, 2, 5, 10, 8, 7, 3, 6, 4]

Selection Sort Applications

Selection Sort, despite its simplicity and relatively slow performance compared to more advanced sorting algorithms, can still be useful in certain scenarios and applications. Here are a few common applications where Selection Sort might be employed:

1. Educational Purposes: Selection Sort is often used as an introductory sorting algorithm in computer science and programming courses. Its straightforward implementation and easy-to-understand logic make it an ideal algorithm for teaching basic sorting concepts.
2. Small Input Sizes: Selection Sort can be efficient for sorting small lists or arrays where the number of elements is relatively small. Since the algorithm has a time complexity of O(n^2), it becomes less practical as the input size increases. However, for small datasets, the simplicity and ease of implementation of Selection Sort can outweigh its slower performance.
3. Partially Sorted Lists: In scenarios where the input list is partially sorted or contains a few misplaced elements, Selection Sort can be advantageous. The algorithm performs the same number of comparisons and swaps regardless of the input order. This property makes it suitable for situations where the cost of swapping elements is higher than the cost of comparisons, as it minimizes the number of swaps required.
4. Online Streaming Data: Selection Sort can be useful for sorting data as it arrives in an online streaming fashion, where new elements are continuously added to the existing list. The algorithm allows for incremental sorting, where the new elements can be inserted at the correct position in the already sorted part of the list. However, it is important to note that more efficient algorithms like Insertion Sort or Heap Sort are generally preferred for this purpose.
5. Benchmarking: Selection Sort can serve as a reference point or a baseline for comparing the performance of other sorting algorithms. By implementing and measuring the time taken by more advanced algorithms, researchers and developers can evaluate the improvements achieved and compare them against the relatively slow Selection Sort.

In practical applications, where performance and efficiency are crucial factors, other sorting algorithms such as Quick Sort, Merge Sort, or Heap Sort are typically preferred over Selection Sort. However, Selection Sort still has its place in certain specific scenarios where simplicity, ease of implementation, or unique input characteristics make it a viable choice.

Selection Sort Complexity

The time and space complexity of the Selection Sort algorithm can be described as follows:

Time Complexity:

• Best-case complexity: O(n^2)
• Average-case complexity: O(n^2)
• Worst-case complexity: O(n^2)

In Selection Sort, for each element in the input list of size n, the algorithm scans the remaining unsorted portion of the list to find the minimum (or maximum) element and swaps it with the current element. This process is repeated for each element, resulting in nested loops. The outer loop iterates n times, and for each iteration, the inner loop performs (n – i) comparisons, where i represents the current iteration. As a result, the total number of comparisons becomes (n – 1) + (n – 2) + … + 1, which simplifies to (n * (n – 1)) / 2. Thus, the number of comparisons is proportional to n^2.

Space Complexity:

• The space complexity of Selection Sort is O(1) because it only requires a constant amount of additional space to store temporary variables used for swapping elements. The algorithm performs in-place sorting, meaning it modifies the input list directly without requiring additional data structures.

Selection Sort has a quadratic time complexity, making it inefficient for large input sizes. However, it can be suitable for small lists or scenarios where other factors, such as simplicity or partially sorted input, outweigh the performance considerations. It is important to note that there are more efficient sorting algorithms available, such as Quick Sort, Merge Sort, or Heap Sort, which have better average and worst-case time complexities.

Selection sort in Python code example

 def selection_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        # Find the minimum element in the remaining unsorted part
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                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 usage
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)

In this example, the selection_sort function takes an array (arr) as input and performs the Selection Sort algorithm on it. The function iterates through the array, finding the minimum element in the remaining unsorted part and swapping it with the first element of the unsorted part. This process is repeated until the entire array is sorted.

The example usage demonstrates sorting an array [64, 25, 12, 22, 11] using the selection_sort function. The sorted array [11, 12, 22, 25, 64] is then printed.

About The Author