Read elements from keyboard until a negative value! Insert those elements into an array such that the array is always sorted

Question

Read elements from keyboard until a negative value! Insert those elements into an array such that the array is always sorted.

I added the code and its outcome. I have a zero on the first position always, and I wanna get rid of it!

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

int a[100], nr_elem=0;

void InsertInAscendingOrder(int x){
    int i;
    int pos;

    for(i=0; i<nr_elem; i++){
        if(a[i]>x){
            pos = i;
            break;
        }
        else{
            a[nr_elem] = x;
        }
    }
    for(int k=nr_elem; k>=pos; k--){
        a[k] = a[k-1];
    }
    a[pos] = x;
    nr_elem++;
}

void printArray(){
    for(int i=0; i<nr_elem; i++){
        printf("%d  ", a[i]);
    }
}

int main()
{
    int x;

    do{
        InsertInAscendingOrder(x);
        printf("x=");
        scanf("%d", &x);
    }while(x>0);

    printArray();
    return 0;
}

Output:

x=10
x=13
x=4
x=90
x=5
x=17
x=-1
0  4  5  10  13  17  90

Answer 1

There are a few issues with your code. Notably, you're inserting x before it's initialized on the first loop iteration, and potentially on subsequent iterations because you haven't verified that scanf succeeded.

As a good practice, let's get rid of the 100 megic number and use a constant. We'll also check the return value of scanf. And we'll make sure the while loop can't overflow the array.

In InsertInAscendingOrder we can handle the special case of the first insertion by just inserting the value at index 0 and incrementing nr_elem.

Otherwise we'll look for the index where the first value larger than x resides, then use memmove to shift every other element before assigning to that index.

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

#define ARR_LIM 100

int a[ARR_LIM], nr_elem = 0;

void InsertInAscendingOrder(int x) {
    int i;
    int pos = nr_elem;

    if (nr_elem == 0) {
        a[0] = x;
        nr_elem++;
        return;
    }

    for (i = 0; i < nr_elem; i++) {
        if (a[i] > x) {
            pos = i;
            break;
        }
    }

    if (pos < nr_elem)
        memmove(&a[pos+1], &a[pos], sizeof(int) * (ARR_LIM-2-pos));

    a[pos] = x;
    nr_elem++;
}

void printArray() {
    for (int i = 0; i < nr_elem; i++) {
        printf("%d  ", a[i]);
    }
    printf("\n");
}

int main(void) {
    int x;

    do {
        printf("x=");

        if (scanf("%d", &x) != 1) {
            printf("Error on input\n");
            continue;
        }

        if (x < 0) break;

        InsertInAscendingOrder(x);
    } while (nr_elem <= ARR_LIM);

    printArray();
    return 0;
}

As a demonstration:

$ ./a.out
x=10
x=1
x=4
x=3
x=28
x=7
x=2
x=-1
1  2  3  4  7  10  28

As noted in comments, the above still exhibits two notable problems.

On erroneous input, the erroneous input will stay in the buffer to be read endlessly and continue resulting in errors. This can be resolved by using fgets to read a line of input and then attempt to use sscanf to read an int from it.

        char line[128] = "";
        fgets(line, 128, stdin);
        if (sscanf(line, "%d", &x) != 1) {
            printf("Error on input\n");
            continue;
        }

Secondly, you should try to avoid using global variables. Instead pass state to and from functions via arguments and return values. I have continued using them here because I felt it would be too much change and distract from the issues I have addressed.

It may help to bundle related pieces of data into a struct. E.g.

struct int_array {
    size_t num_elem;
    int arr[ARR_LIM];
};

For an idea of how an even more flexible struct (that allows for varying capacities) might look in a complete program, see below. Not a single global variable in sight.

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

#define ARR_LIM 100

typedef struct arr_info {
    size_t cap;
    size_t size;
    int *arr;
} arr_info;

void InsertInAscendingOrder(arr_info *arr, int x) {
    int i;
    int pos = arr->size;

    if (arr->size == 0) {
        arr->arr[0] = x;
        arr->size++;
        return;
    }

    for (i = 0; i < arr->size; i++) {
        if (arr->arr[i] > x) {
            pos = i;
            break;
        }
    }

    if (pos < arr->size)
        memmove(&arr->arr[pos+1], &arr->arr[pos], sizeof(int) * (arr->cap - 2 - pos));

    arr->arr[pos] = x;
    arr->size++;
}

void printArray(arr_info *arr) {
    for (size_t i = 0; i < arr->size; i++) {
        printf("%d  ", arr->arr[i]);
    }
    printf("\n");
}

int main(void) {
    arr_info a = {
      .cap = ARR_LIM,
      .size = 0,
      .arr = malloc(sizeof(int) * ARR_LIM)
    };

    if (a.arr == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }

    int x;

    do {
        printf("x=");

        char line[128] = "";
        fgets(line, 128, stdin);
        if (sscanf(line, "%d", &x) != 1) {
            printf("Error on input\n");
            continue;
        }

        if (x < 0) break;

        InsertInAscendingOrder(&a, x);
    } while (a.size < a.cap);

    printArray(&a);
    return 0;
}

Answer 2

For starters neither declaration from the header <stdlib.h> is used in your program. You may remove the header inclusion.

The function main without parameters shall be declared like

int main( void )

Using the global variables

int a[ARR_LIM], nr_elem = 0;

is unnecessary and a bad idea. Try to write more general functions that do not depend on global variables.

Within main you are using the uninitialized variable x in the first iteration of the while loop

int x;

do{
    InsertInAscendingOrder(x);
    printf("x=");
    scanf("%d", &x);
}while(x>0);

Also the condition of the loop should look like

}while(x>=0);

because 0 is an acceptable value.

Moreover within the while loop you need to check whether a call of scanf was successful and whether the bounds of the array were not broken.

Within the function InsertInAscendingOrder there can be again used uninitialized variable pos if neither actual element of the array is greater than x.

void InsertInAscendingOrder(int x){
    int i;
    int pos;

    for(i=0; i<nr_elem; i++){
        if(a[i]>x){
            pos = i;
            break;
        }
        else{
            a[nr_elem] = x;
        }
    }
    for(int k=nr_elem; k>=pos; k--){
        a[k] = a[k-1];
    }
    a[pos] = x;
    nr_elem++;
}

And within this for loop

for(int k=nr_elem; k>=pos; k--){
    a[k] = a[k-1];
}

when pos is equal to 0 there will be an access to memory beyond the array in this statement

a[k] = a[k-1];

that will be equivalent to

a[0] = a[-1];

There is no sense to use two separate loops within the function. The function can look simpler using only one loop.

Here is your updated program.

#include <stdio.h>

void InsertInAscendingOrder( int a[], size_t n, int x )
{
    if (n != 0)
    {
        size_t i = n - 1;

        for (; i != 0 && x < a[i - 1]; --i)
        {
            a[i] = a[i - 1];
        }

        a[i] = x;
    }
}

void printArray( const int a[], size_t n ) 
{
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d  ", a[i] );
    }
    putchar( '\n' );
}

int main( void )
{
    enum { N = 100 };
    int a[N];

    size_t n = 0;

    while (1)
    {
        int x;

        printf( "x (-1 - exit ): " );

        if (!( n < N && scanf( "%d", &x ) == 1 && x >= 0 )) break;

        InsertInAscendingOrder( a, ++n, x );
    }

    printArray( a, n );
}

The program output might look like

x (-1 - exit ): 10
x (-1 - exit ): 1
x (-1 - exit ): 4
x (-1 - exit ): 3
x (-1 - exit ): 28
x (-1 - exit ): 8
x (-1 - exit ): 2
x (-1 - exit ): -1
1  2  3  4  8  10  28

As you can see the function InsertInAscendingOrder is enough simple and contains only one loop.

void InsertInAscendingOrder( int a[], size_t n, int x )
{
    if (n != 0)
    {
        size_t i = n - 1;

        for (; i != 0 && x < a[i - 1]; --i)
        {
            a[i] = a[i - 1];
        }

        a[i] = x;
    }
}

In turn the function printArray can be written without introducing an intermediate variable as for example

void printArray( const int a[], size_t n )
{
    while ( n-- ) printf( "%d  ", *a++ );
    putchar( '\n' );
}