Array re-sort algorithm

Question

I need to take out element of with index i and re-sort the array after that. For example if I have 1 2 3 4 in the array and take out the 3, I need to get 1 2 4 with the NULL elements at the end.

The elements I need to take of:

INVENTORY_AMOUNT_ARRAY[i];
INVENTORY_PRICES_ARRAY[i];
INVENTORY_NAMES_ARRAY[i];

My array definitions:

static intmax_t INVENTORY_AMOUNT_ARRAY[MAX_SIZE_OF_ARRAYS];
static intmax_t INVENTORY_PRICES_ARRAY[MAX_SIZE_OF_ARRAYS];
static char     INVENTORY_NAMES_ARRAY[MAX_SIZE_OF_ARRAYS][MAX_SIZE_OF_ARRAYS];

My function:

void cache_remove_product() {
    int i = 0;
    for (; (strlen(INVENTORY_NAMES_ARRAY[i])) != 0; i++){}
    printf("Enter the product's name u want to remove:");
    char temp_string_for_prname[MAX_SIZE_OF_STRINGS];
    scanf("%s", &temp_string_for_prname);
    for (int i = 0; (strlen(INVENTORY_NAMES_ARRAY[i])) != 0; i++) {
        if ((strcmp(temp_string_for_prname, INVENTORY_NAMES_ARRAY[i])) == 0) {
            memset(INVENTORY_NAMES_ARRAY[i], 0, sizeof(INVENTORY_NAMES_ARRAY[i]));
            INVENTORY_PRICES_ARRAY[i] = 0;
            INVENTORY_AMOUNT_ARRAY[i] = 0;
            int j = 0;
            for (;;) {
            }       
        }
    }
}

I need the algorithm to be placed in the blank for

Answer 1

Suppose you were to delete all of the array like this. One moves forward in the array, and at every data, tests if it should be deleted: yes. It will move all the array back one spot every time. The running time to delete n objects is n(n+1)/2 which is O(n^2).

We could do better by having a lazy delete operation which remembers the spot but doesn't delete until it absolutely has to. This runs in one pass O(n).

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

struct inventory {
    char name[128];
    uint64_t amount;
    uint32_t cent_price;
};
static const size_t max_size_of_strings = sizeof ((struct inventory *)0)->name;
struct database {
    struct inventory data[32];
    size_t size;
} db;
static const size_t max_size_of_arrays = sizeof db.data / sizeof *db.data;

typedef int (*predicate_fn)(const struct inventory *, const void *);

static void keep_if(const predicate_fn keep, const void *const param) {
    struct inventory *erase = 0, *i, *retain = 0, *end;
    int keep0 = 1, keep1 = 0;
    assert(keep);
    for(i = db.data, end = i + db.size; i < end; keep0 = keep1, i++) {
        keep1 = !!keep(i, param);
        if(!(keep0 ^ keep1)) continue; /* Not a falling/rising edge. */
        if(keep1) { /* Rising edge. */
            assert(erase && !retain);
            retain = i;
        } else if(erase) { /* Falling edge. */
            size_t n = (size_t)(i - retain);
            assert(erase < retain && retain < i);
            memmove(erase, retain, sizeof *i * n);
            erase += n;
            retain = 0;
        } else { /* Falling edge, (first time only.) */
            erase = i;
        }
    }
    if(!erase) return; /* All elements were kept. */
    if(keep1) { /* Delayed move when the iteration ended; repeat. */
        size_t n = (size_t)(i - retain);
        assert(retain && erase < retain && retain < i);
        memmove(erase, retain, sizeof *i * n);
        erase += n;
    }
    /* Adjust the size. */
    assert((size_t)(erase - db.data) <= db.size);
    db.size = (size_t)(erase - db.data);
}

static int strcmp_name(const struct inventory *item, const void *const vname) {
    const char *const name = vname;
    return strcmp(name, item->name);
}

int main(void) {
    size_t i;
    strcpy(db.data[0].name, "A"); db.data[0].amount = 0;
    strcpy(db.data[1].name, "B"); db.data[1].amount = 1;
    strcpy(db.data[2].name, "A"); db.data[2].amount = 2;
    strcpy(db.data[3].name, "B"); db.data[3].amount = 3;
    strcpy(db.data[4].name, "A"); db.data[4].amount = 4;
    strcpy(db.data[5].name, "B"); db.data[5].amount = 5;
    strcpy(db.data[6].name, "C"); db.data[6].amount = 6;
    strcpy(db.data[7].name, "B"); db.data[7].amount = 7;
    strcpy(db.data[8].name, "B"); db.data[8].amount = 8;
    strcpy(db.data[9].name, "B"); db.data[9].amount = 9;
    strcpy(db.data[10].name, "B"); db.data[10].amount = 10;
    strcpy(db.data[11].name, "B"); db.data[11].amount = 11;
    strcpy(db.data[12].name, "B"); db.data[12].amount = 12;
    strcpy(db.data[13].name, "A"); db.data[13].amount = 13;
    strcpy(db.data[14].name, "C"); db.data[14].amount = 14;
    db.size = 15;
    keep_if(&strcmp_name, "B"); /* strcmp returns false if matched */
    for(i = 0; i < db.size; i++) {
        const struct inventory *const item = db.data + i;
        printf("%llu, %d, %s\n", item->amount, item->cent_price, item->name);
    }
    return 0;
}

I've simplified the code with a struct so all the data is in one object. (I assume the second MAX_SIZE_OF_ARRAYS in INVENTORY_NAMES_ARRAY should be MAX_SIZE_OF_STRINGS.)

Answer 2

There are multiple issues in the code:

• the first loop is useless, just remove it

• you must tell scanf() a maximum count of characters to store into the destination array to avoid undefined behavior on invalid input. There is no simple way to do this with scanf() is the length of the array is not an explicit constant. I suggest using fgets() this way:

  char prname[MAX_SIZE_OF_STRINGS + 1];
  if (!fgets(prname, sizeof prname, stdin))
      return;
  size_t len = strlen(prname);
  if (len > 0 && prname[len - 1] == '\n')
      prname[--len] = '\0';
  if (len == 0)
      return;
  

• the test for end of array can be simplified as

  for (int i = 0; INVENTORY_NAMES_ARRAY[i][0] != '\0'; i++) {
  

• to remove the matching entry from all arrays, you must copy each of the following entries to the previous position and clear the last entry.

Note that there is no need to re-sort the array as removing an element by shifting all subsequent elements one position does not change the relative order of the remaining elements.

Here is a modified version:

#include <stdio.h>

static intmax_t INVENTORY_AMOUNT_ARRAY[MAX_SIZE_OF_ARRAYS];
static intmax_t INVENTORY_PRICES_ARRAY[MAX_SIZE_OF_ARRAYS];
static char     INVENTORY_NAMES_ARRAY[MAX_SIZE_OF_ARRAYS][MAX_SIZE_OF_ARRAYS];

void cache_remove_product(void) {
    int i, j;
    printf("Enter the product's name u want to remove:");
    char prname[MAX_SIZE_OF_STRINGS + 1];
    if (!fgets(prname, sizeof prname, stdin))
        return;
    size_t len = strlen(prname);
    if (len > 0 && prname[len - 1] == '\n')
        prname[--len] = '\0';
    if (len == 0)
        return;
    // remove all matching entries
    for (i = 0; INVENTORY_NAMES_ARRAY[i][0] != '\0';) {
        if (strcmp(prname, INVENTORY_NAMES_ARRAY[i]) == 0) {
            // move subsequent entries
            for (j = i; j < MAX_SIZE_OF_ARRAYS - 1; j++) {
                strcpy(INVENTORY_NAMES_ARRAY[j], INVENTORY_NAMES_ARRAY[j + 1]);
                INVENTORY_PRICES_ARRAY[j] = INVENTORY_PRICES_ARRAY[j + 1];
                INVENTORY_NAMES_ARRAY[j] = INVENTORY_NAMES_ARRAY[j + 1];
                if (INVENTORY_NAMES_ARRAY[j][0] == '\0')
                    break;
            }
            INVENTORY_NAMES_ARRAY[j][0] = '\0';
        } else {
            i++;
        }
    }
}

Answer 3

You can try to swap the chosen item to the end of array one-by-one then make it null.

For example : you have given {1, 2, 3, 4, 5, 6, 7} you want to remove 3 you make the swap operation between 3 to 7 like :
step 0 {1, 2, 3, 4, 5, 6, 7}
step 1 {1, 2, 4, 3, 5, 6, 7}
step 2 {1, 2, 4, 5, 3, 6, 7}
step 3 {1, 2, 4, 5, 6, 3, 7}
step 4 {1, 2, 4, 5, 6, 7, 3}
after that you can just assign last index of the array is null.
array[lengthOfArray - 1] = NULL;
We could just swap the last element and the chosen element but if we do that our array won't be sorted anymore.