Search code examples
calgorithmsortingterminal

Sorting algorithm has problems when a negative number is inputted


I'm trying to write code in C that sorts n numbers from least to greatest. It works fine when all the numbers are positive but it returns 0 at the first index when I put a negative number.

Below is my code:

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

int main(int argc, char *argv[])
{
    int data[100000]; /* Array of ints to sort */
    int nDataItems;
    if (argc > 1) {
        nDataItems = argc;
        for (int i = 0; i < nDataItems; i++)
            data[i] = atoi(argv[i]);
    } else {
        nDataItems = 4;
        data[0] = 10;
        data[1] = 20;
        data[2] = 30;
        data[3] = 40;
    }
     
    mySort(data, nDataItems);

    for (int i = 0; i < nDataItems - 1; i++) {
        if (data[i] > data[i + 1]) {
            printf("Sorting error at index %d \n", nDataItems);
            exit(1);
        }
    }
  
    printf("Printing Array: \n");

    for (int i = 1; i < nDataItems; i++)
        printf("%d \n", data[i]);
    return 0;
}

and here's the code for the sorting:

void mySort(int d[], unsigned int n)
{
    int x, y;
    for (int i = 0; i < n; i++)
    {
         x = i - 1;
         y = d[i];
         while (x >= 0 && d[x] > y) {
             d[x+1] = d[x];
             x--;
        }
        d[x + 1] = y;
    }
}

From what I understand, the code is taking in negative numbers and converting it to 0. I'm suspecting the issue is with atoi but not certain. Here is a picture of the terminal when I try testing it.:

C:\Users\danes\Desktop\COE428\lab1›testSort2 2 76 33 11 9
Printing Array
2
9
11
33
76

C:\Users\danes\Desktop\COE428\lab1> testSort2 -5 11 29 15 2
Printing Array
0
2
11
15
29

Solution

  • There are 2 problems in the code:

    • you copy the command line arguments from argv[0] to argv[argc - 1], which is incorrect as argv[0] is the name of the program, not a command line argument. You get one more entry in the array than there are arguments and this initial entry is 0 as the name of the program starts with a letter.

    • you output the array from i = 1 instead of i = 0, so you skip the lowest element after the sort.

    If all arguments are positive, the extra 0 sorts to the lowest position and is skipped on output, hiding the problem, but if there is at least one negative number, the 0 appears in the output and the lowest number is missing as observed in the second example.

    A typical case of two bugs cancelling each other, but not always.

    Here is a modified version:

    #include <stdio.h>
    #include <stdlib.h>
    #include "mySort.h"
    
    int main(int argc, char *argv[])
    {
        int data[100000]; /* Array of ints to sort */
        int nDataItems;
        if (argc > 1) {
            nDataItems = argc - 1;
            for (int i = 0; i < nDataItems; i++)
                data[i] = atoi(argv[i + 1]);
        } else {
            nDataItems = 4;
            data[0] = 10;
            data[1] = 20;
            data[2] = 30;
            data[3] = 40;
        }
         
        mySort(data, nDataItems);
    
        for (int i = 0; i < nDataItems - 1; i++) {
            if (data[i] > data[i + 1]) {
                printf("Sorting error at index %d\n", nDataItems);
                exit(1);
            }
        }
      
        printf("Printing Array:\n");
    
        for (int i = 0; i < nDataItems; i++)
            printf("%d \n", data[i]);
    
        return 0;
    }
    
    void mySort(int d[], unsigned int n)
    {
        // perform insertion sort
        for (int i = 1; i < n; i++) {
             int y = d[i];
             for (int x = i; x > 0 && d[x - 1] > y; x--) {
                 d[x] = d[x - 1];
            }
            d[x] = y;
        }
    }