Selection Sort Explanation

Question

I've been working on a recursive function in C which takes an int array and its size and does a selection sort where the array should now be ordered from least to greatest:

void selection_sort(int integers[], size_t size)
{
    if (size == 0) {
        return;
    }

    int largest = 0;
    int largest_index = 0;
    int temp;

    for (int i = 0; i < size; ++i) {
        if (integers[i] > integers[largest_index]) {
            largest_index = i;
        }
    }
    temp = integers[largest_index];
    integers[largest_index] = integers[size - 1];
    integers[size - 1] = temp;

    selection_sort(integers, size - 1);
}

So if integers contains 17, 8, 14, 25, and 11, after calling selection_sort, it will now contain 8, 11, 14, 17, and 25. The code works as it should, however, I was trying to trace the logic out on paper and I don't think I'm thinking of it correctly because I'm not getting the numbers that I should. I was wondering if someone could thoroughly explain the logic of the function step-by-step. Any help would be appreciated!

Answer 1

Lets break out your code to understand its workflow.

your function takes two arguments one is array and other is size of the array

selection_sort(int integers[], size_t size)

Second part, if size of the array is zero then return

if (size == 0) {
        return;
    }

Third part, define variables

int largest = 0; //this variable is not used
int largest_index = 0; //this is index for largest array value
int temp; //temporary variable for swapping 

Fourth part finding the largest value index in array

for (int i = 0; i < size; ++i) { //Iterate array from 0 to size
        if (integers[i] > integers[largest_index]) { /*check if current index value is greater than largest value index */
            largest_index = i; /* if value is greater than current index value add index in largest_index variable */
        }

In first iteration for array [17, 8, 14, 25, 11] largest_index will be 3 (25).

Fifth part, Swap highest value and last element of the array

[17, 8, 14, 25, 11] will become [17, 8, 14, 11, 25]

 temp = integers[largest_index]; //take 25 in temp
    integers[largest_index] = integers[size - 1]; 
    integers[size - 1] = temp; //swap 11 with 25

Last part, call the function recursively with array of reduced size by 1 element

Example in first iteration array will [17, 8, 14, 11] and second iteration [11, 8, 14], it will keep decreasing array size till it returns(size becomes zero)

selection_sort(integers, size - 1);