CODEWITHSUNDEEP
cloopsfor-looptimecomplexity-theory
youztouz
youztouz

Reputation: 13

how do i get a lower time complexity with a nested loop

Hi everyone i'm working on c and my code looks like this, basically it's an array and in every array[j] there is a number from 1 to 8, not in order and i'm trying to find where 1 is, and do some operations, then find 2 and do other operations etc.. till number 8:

for(i=1;i<9;i++)
   for(j=0;j<8;j++)
     if(array[j]==i)
       //and operations to do but they are not needed now;

I'm trying to find another way of doing this with less time spent in the cycle as the complexity can be (n^2). Someone advided me a hasing system to order things but i don't know if it's good enough. Thanks to everyone!

Upvotes: 0

Views: 155

Answers (2)

user3629249
user3629249

Reputation: 16540

suggest the code have an outer loop going through the arrays of 8 structs

For each array of 8 structs, loop through that 8, placing the index into that array of structs into a separate array of 8 integers according to the value in the first field of each struct.

Then a loop that goes through that array of 8 offsets, one by one, performing the desired operation for that specified struct instance.

Upvotes: 0

sebastian
sebastian

Reputation: 412

Quicksort has an average complexity of O(n log(n)). Sort the pair (value, index) by index so you can access them in O(1).

struct pair
{
    int val;
    int index;
};

int pair_compare(const void* a, const void* b)
{
    struct pair* x = (struct pair*)a;
    struct pair* y = (struct pair*)b;

    return x->val > y->val;
}

int main()
{
    int arr[8] = {4,2,1,3,6,5,8,7};
    
    struct pair* pairs = (struct pair*) calloc(8, sizeof(*pairs));

    int i;

    for(i = 0; i < 8; ++i)
    {
        pairs[i].val = arr[i];
        pairs[i].index = i;
    }

    qsort(pairs, 8, sizeof(*pairs), pair_compare);

    for(i = 0; i < 8; ++i)
    {
        printf("val: %d\tindex: %d\n", pairs[i].val, pairs[i].index);
    }

    free(pairs);

    return 0;
}

Upvotes: 3

Related Questions