Selection Sort Algorithm

The selection sort algorithm is a simple comparison-based sorting algorithm. It divides the input list into two parts: the sorted part and the unsorted part. The algorithm repeatedly finds the minimum element from the unsorted part and places it at the beginning of the sorted part. This process is repeated until the entire list is sorted.

Algorithm Steps:

1. Find the minimum element in the unsorted part of the list.
2. Swap the minimum element with the first element of the unsorted part.
3. Move the boundary of the sorted part one element to the right.
4. Repeat steps 1-3 until the entire list is sorted.

Pseudocode:

    procedure selectionSort(arr: array)
      n := length(arr)
      for i from 0 to n-1
          minIndex := i
          for j from i+1 to n-1
              if arr[j] < arr[minIndex]
                  minIndex := j
          swap(arr[i], arr[minIndex])
  

Code Explanation:

The selection sort algorithm is implemented using nested loops. The outer loop iterates through each element in the list, from the first element to the second-to-last element. The inner loop finds the minimum element from the unsorted part of the list by comparing each element with the current minimum element. If a smaller element is found, its index is stored as the new minimum index. After the inner loop completes, the minimum element is swapped with the first element of the unsorted part. This moves the boundary of the sorted part one element to the right. The process is repeated until the entire list is sorted.

Example:

Let's consider an example to understand the selection sort algorithm.

    Initial list: [7, 4, 2, 8, 1]
    Sorted list:  [1, 2, 4, 7, 8]
  

Complexity:

The selection sort algorithm has a time complexity of O(n^2) in all cases, where n is the number of elements in the list. This makes it inefficient for large lists. However, it has the advantage of performing a minimal number of swaps, as only one swap is performed in each iteration of the outer loop.

---