CODEWITHSUNDEEP
calgorithminsertion-sort
KarimS
KarimS

Reputation: 3902

c - implementing insertion algorithm

i have implemented insertion algorithm in c programming language, but i have faced a little problem when tried to extend it to both increasing and decreasing order, the problem is about that a little piece of code is repeat :

typedef int order_t;

#define INCREASING  0
#define DEACREASING 1

extern void insertion_sort(int *const arr, size_t arr_size, order_t order) {
    register size_t i, j;
    register int key;

    for(i = 1; i < arr_size; ++i) {
        key = arr[i];

        if(order == INCREASING) 
            for(j = i - 1; j >= 0 && arr[j] > key; --j) {
                arr[j+1] = arr[j];
            }
        else {
            for(j = i - 1; j >= 0 && arr[j] < key; --j) {
                arr[j+1] = arr[j];
            }
        }

        arr[j+1] = key;
    }
}

there is a ways to do so the for statement and a[j+1] = arr[j] inside the for will be written only one time?

Upvotes: 1

Views: 88

Answers (2)

pablo1977
pablo1977

Reputation: 4433

And what about a little change in your constants? 

typedef int order_t;

#define INCREASING  (+1)
#define DEACREASING (-1)

extern void insertion_sort(int *const arr, size_t arr_size, order_t order) {
    register size_t i, j;
    register int key;

    for(i = 1; i < arr_size; ++i) {
        key = arr[i];

        for(j = i - 1; j >= 0 && ((arr[j] - key) * order < 0); --j) {
            arr[j+1] = arr[j];
        }

        arr[j+1] = key;
    } 
 }

Upvotes: 0

SoleZero
SoleZero

Reputation: 46

for(i = 1; i < arr_size; ++i) {
    key = arr[i];

    for(j = i - 1; j >= 0 && (order == INCREASING ? (arr[j] > key) : (arr[j] < key)) ; --j) {
         arr[j+1] = arr[j];
    }

    arr[j+1] = key;
}

Upvotes: 3

Related Questions