Implementing Selection Sort in C

Question

I am trying to implement the Selection Sort Algorithm and here is my attempt:

int select(int arr[], int i)
{
    int j, minIndex;
    
    minIndex = i;
    for (j = i + 1; arr[j]; j++)
    {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    return minIndex;
}


void selectionSort(int arr[], int n)
{
    int i, iMin;
    
    for (i = 0; i < n - 1; i++)
    {
        iMin = select(arr, i);
        if (iMin != i)
        {
            int temp = arr[i];
            arr[i] = arr[iMin];
            arr[iMin] = temp;
        }
    }
}

Even though my code works fine, if there is an element in the array with value zero it fails. Here is an example case:

4 1 3 9 0

Output:

1 3 4 9 0

I know that my logic is correct, because it works with other cases, but why is it failing if there is a 0 in the array element?

Answer 1

1. Your loop condition is wrong:

for (j = i + 1; arr[j]; j++)

instead of arr[j] you need j < n.

2. Renamed select() to selectMin() to avoid conflict with existing function with that name. If you specify the length n before the array arr your can document how the two are related with current compilers.
3. Extracted the swap() function.
4. Minimized scope of variables.
5. size_t instead of int for indices as they are non-negative. The type difference also helps you distinguish between the indices of the array (size_t) the values of the array (int) which was the root cause of your troubles.
6. Hard-coded your test case and implemented a print() functions to verify correct result.

#include <stdio.h>
#include <stdlib.h>

void print(size_t n, int a[n]) {
    for(size_t i = 0; i < n; i++)
        printf("%d%s", a[i], i + 1 < n ? ", " : "\n");
}

size_t selectMin(size_t n, int arr[n], int i) {
    size_t minIndex = i;
    for (size_t j = i + 1; j < n; j++)
        if (arr[j] < arr[minIndex])
            minIndex = j;
    return minIndex;
}

void selectionSort(size_t n, int arr[n]) {
    for (size_t i = 0; i < n - 1; i++) {
        size_t iMin = selectMin(n, arr, i);
        if (iMin != i)
            swap(arr + i, arr + iMin);
    }
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void) {
    int a[] = {4, 1, 3, 9, 0};
    selectionSort(sizeof a / sizeof *a, a);
    print(sizeof a / sizeof *a, a);
}

and the output is:

0, 1, 3, 4, 9