Selection Sort

Selection sort is a simple sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front of the list, and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Let's consider an example with the list [29, 10, 14, 37, 13]. We'll go through the selection sort process, illustrating each step with ASCII art.

Initial List:

29  10  14  37  13

1st Iteration (Find the minimum element and swap it with the first element):

• Minimum: 10

• Swap 10 and 29

10  29  14  37  13
   ^^^^^^^^^^^^^^^^

2nd Iteration (Find the minimum element in the remaining list and swap with the 2nd element):

• Minimum: 13

• Swap 13 and 29

10  13  14  37  29
       ^^^^^^^^^^^

3rd Iteration (Find the minimum in the rest and swap with the 3rd element):

• No swap needed as 14 is already in correct position

10  13  14  37  29
           ^^^^^^^

4th Iteration (Find the minimum in the last two and swap if needed):

• Minimum: 29

• Swap 29 and 37

10  13  14  29  37
               ^^^

5th Iteration:

• Not needed as the list is already sorted

The final sorted list is [10, 13, 14, 29, 37].

In each iteration, the range of the unsorted list (denoted by ^) gets smaller as the smallest elements get sorted to the front. This process continues until the entire list is sorted.

Here is the pseudo code for the Selection Sort algorithm:

SelectionSort(A: array of values)
    n = length(A)

    for i = 0 to n-1
        // Set current element as minimum
        min_index = i

        // Check the rest of the array to find the minimum
        for j = i+1 to n-1
            if A[j] < A[min_index]
                min_index = j

        // Swap the found minimum element with the current element
        if min_index != i
            swap A[i] and A[min_index]

This pseudo-code outlines the basic process of the Selection Sort:

1. Iterate over the array, treating each element as the current minimum.

2. For each position i in the array, find the smallest element in the rest of the array (from i+1 to n-1).

3. If the found minimum is not the element at position i (i.e., there's a smaller element found in the rest of the array), swap the elements.

4. Repeat this process until the entire array is sorted.

Here's the C code for the Selection Sort algorithm:

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_index, temp;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++) {
        // Find the minimum element in unsorted array
        min_index = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }

        // Swap the found minimum element with the first element
        temp = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i=0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Explanation of the code:

1. Function Declaration: The function selectionSort is declared which takes an array arr[] and its size n as arguments.

2. Outer Loop: The first for loop runs from the start of the array to the second-to-last element. It represents the current position in the array where we're placing the smallest unsorted element.

3. Finding Minimum Element: Inside this loop, we initialize min_index to the current position i. Then, another nested for loop starts from the next element to the end of the array. This inner loop is used to find the index of the minimum element in the unsorted part of the array.

4. Swapping Elements: After finding the minimum element in the unsorted part, we swap it with the element at the current position i. We use a temporary variable temp for this purpose.

5. Printing the Array: The printArray function is a utility to print the elements of an array.

6. Driver Code: In main, we declare an array arr[] and determine its size. We then call selectionSort with this array, and finally, print the sorted array.

This C code effectively sorts an array using the Selection Sort algorithm, which is an in-place comparison sort. The algorithm is not suitable for large datasets as its average and worst-case complexity are of O(n^2), where n is the number of items.

The complexity analysis of the Selection Sort algorithm involves evaluating both its time complexity and space complexity.

Time Complexity

1. Best, Average, and Worst Cases:

   • Best Case: Even in the best case, where the array is already sorted, the algorithm still goes through the entire array to check if the element is the minimum in the remaining part of the array. So, the best-case complexity is O(n^2).

   • Average Case: On average, the algorithm performs the same number of comparisons, which is O(n^2).

   • Worst Case: The worst-case scenario is also O(n^2), which happens when the array is in reverse order.

The key operation in the time complexity analysis is the number of comparisons. For each element in the array, the algorithm searches the rest of the array to find the minimum element. If the array has n elements, the first element is compared with n-1 elements, the second with n-2, and so on, leading to n(n-1)/2 comparisons, which simplifies to O(n^2).

1. Nested Loops:

   • The outer loop runs n-1 times, and for each iteration of the outer loop, the inner loop runs n-i times (where i is the current iteration of the outer loop). This nested loop structure contributes to the quadratic time complexity.

Space Complexity

• Space Complexity: The space complexity of Selection Sort is O(1), which means it is a constant space, in-place sorting algorithm. Regardless of the size of the input, the algorithm requires the same amount of additional space (for variables like i, j, min_index, and temp). This makes it an in-place sorting algorithm.

Important to note

• Selection Sort is not a scalable sorting algorithm for large datasets due to its quadratic time complexity (O(n^2)).

• It is, however, an in-place sort with minimal additional memory usage, making its space complexity desirable at O(1).

• Its performance is not affected by the initial arrangement of elements in the array, as it always performs O(n^2) comparisons.