Simple Selection Sort program. Works flawlessly 85% of times but sometimes doesn't sort

Question

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

main()
{
    int ctr, inner, outer, didSwap, temp;
    int nums[10];
    time_t t;

    srand(time(&t));

    for (ctr = 0; ctr < 10; ctr++) {
        nums[ctr] = (rand() % 99) + 1;
    }

    printf("\nHere is the list before the sort:\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    // Sorting the array
    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;

        for (inner = outer + 1; inner < 10; inner++) {
            if (nums[inner] < nums[outer]) {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }

        if (didSwap == 0) {
            break;
        }
    }

    printf("\n\nHere is the list after sorting:\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    printf("\n");

    return 0;
}

It works most of the times but sometimes doesn't sort properly and sometimes doesn't sort at all.

P.S. If the code is incorrect then why does it work 85% of the times.

Snapshot of error

Answer 1

For some reason, you break if no swap is done for any particular element, thus leaving the other elements unsorted:

if (didSwap == 0) {
    break;
}

You need to remove the above conditional to make it work and sort all the elements. There is no need of such conditional in the standard selection sort algorithm as well.

Answer 2

You are breaking the outer loop when there is no swap. This will not gonna work so remove the didSwap and remove the below code

if (didSwap == 0) {
    break;
}

and the program should work fine.

Answer 3

Your code is a wrong implementation of the bubble sort.

If the first element of the array is the smaller one as the example in your question the code

if (didSwap == 0) {
    break;
}

breaks the loops at the first turn and nothing is sort.

A test similar to the one for didSwap exists in a bubble sort, but the implementation is different, it does not do if (nums[inner] < nums[outer]) but compare each element with the next.

If the code is incorrect then why does it work 85% of the times

I don't know from where these 85% comes (and is very probably false), of course all depends on the values in the array, but when nums[outer]is smaller than all the elements having a greater index your program stops, and the elements having a greater index are not sorted. In the example in your question the very first element is the smaller of the array so nothing at all is sort.

---

So two possibilities :

• to remove all concerning didSwap

• to implement a bubble sort

to have a bubble sort modify your internal loop to have for instance :

for (inner = outer + 1; inner < 8; inner++) {
    if (nums[inner] > nums[inner + 1]) {
        temp = nums[inner];
        nums[inner] = nums[inner + 1];
        nums[inner + 1] = temp;
        didSwap = 1;
    }
}

for instance to use the values you give in your question :

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

int main()
{
    int ctr, inner, outer, didSwap, temp;
#if 1
    int nums[10] = { 4, 6, 25, 9, 60, 59, 44, 65, 59, 90};
#else
    int nums[10];
    time_t t;

    srand(time(&t));

    for (ctr = 0; ctr < 10; ctr++) {
        nums[ctr] = (rand() % 99) + 1;
    }
#endif

    puts("\nHere is the list before the sort:");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    // Sorting the array
    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;

        for (inner = outer + 1; inner < 8; inner++) {
            if (nums[inner] > nums[inner + 1]) {
                temp = nums[inner];
                nums[inner] = nums[inner + 1];
                nums[inner + 1] = temp;
                didSwap = 1;
            }
        }

        if (didSwap == 0) {
            break;
        }
    }

    puts("\n\nHere is the list after sorting:");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%3d", nums[ctr]);
    }

    putchar('\n');

    return 0;
}

Compilation and execution :

pi@raspberrypi:/tmp $ gcc -Wall c.c
pi@raspberrypi:/tmp $ ./a.out

Here is the list before the sort:
  4  6 25  9 60 59 44 65 59 90

Here is the list after sorting:
  4  6  9 25 44 59 59 60 65 90
pi@raspberrypi:/tmp $