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?

CodePudding user response：

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

CodePudding user response：

The loop

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

is problematic because of the loop condition arr[j]. As a condition it's equivalent to arr[j] != 0. C doesn't have any concept of "null values" like e.g. C# or Java.

You need to pass the array length to the select function, you can't rely on the array data itself to know when and where the array ends.

Using the array data itself will either lead to premature loop end if the data contains zeros. Or will go out of bounds if the array data doesn't contain any zeros.