Two-Way Insertion Sort not sorting

Question

This is supposed to be a Two-Way insertion sort, but it's not sorting. I'm also supposed to print out the number of assignments for sorting, but right now I just want it to sort.

A separate output array of size 2n+1 is set aside. Initially x[0] is placed into the middle element of the array n. Continue inserting elements until you need to insert between a pair of elements in the array. As before you need to make room for the new element by shifting elements. Unlike before, you can choose to shift all smaller elements one step to the left or all larger elements one step to the right since there is additional room on both sides of the array. The choice of which shift to perform depends on which would require shifting the smallest amount of elements.

I can't find much on the internet about this sort except that no one uses it.

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

void printArray(int arr[], int len) {
    for (int j = 0; j < len; j++)
        printf("%d ", arr[j]);

    printf("\n");
}

int main() {
    FILE *in;
    int size_arr = 0;
    char ch;

    if ((in = fopen("data_a5.txt", "r")) == NULL) {
        printf("Error!");
        exit(1);
    }
    do {
        ch = fgetc(in);
        if (ch == '\n')
            size_arr++;
    } while (ch != EOF);
    rewind(in);

    int arr[size_arr];
    int sort_arr[2 * size_arr + 1];

    int n = 0;
    while (!feof(in)) {
        fscanf(in, "%d", &arr[n]);
        n++;
    }
    fclose(in);

    for (n = 0; n < 2 * size_arr; n++) {
        sort_arr[n] = 0;
    }

    sort_arr[size_arr] = arr[0];

    for (n = 1; n < size_arr; n++) {
        int index = size_arr;
        if (arr[n] <= sort_arr[size_arr]) {
            while (!(arr[n] <= sort_arr[index]) && sort_arr[index] != 0 && index >= 0) {
                index--;
            }
        }
        if (arr[n] > sort_arr[size_arr]) {
            while (!(arr[n] <= sort_arr[index]) && sort_arr[index] != 0 && index < 2 * size_arr) {
                index++;
            }
        }

        if (sort_arr[index] == 0) {
            sort_arr[index] = arr[n];
        } else {
            int next_R, next_L = index;
            while (sort_arr[next_R] != 0 && next_R <= 2 * size_arr) {
                next_R++;
            }
            while (sort_arr[next_L] != 0 && next_L >= 0) {
                next_L--;
            }
            int R_move = next_R - index;
            int L_move = index - next_L;
            if (R_move > L_move) {
                while (L_move <= index) {
                    sort_arr[L_move] = sort_arr[L_move + 1];
                    L_move++;
                }
                sort_arr[index] = arr[n];
            } else {
                while (R_move >= index) {
                    sort_arr[R_move] = sort_arr[R_move - 1];
                    R_move--;
                }
                sort_arr[index] = arr[n];
            }
        }
    }
    printArray(arr, size_arr);
    return 0;
}

You should get familiar with a debugger to figure out where it goes wrong. — xander, Jul 24 '17 at 06:25
You should read [Why is “while ( !feof (file) )” always wrong?](https://stackoverflow.com/q/5431941/3684343) — mch, Jul 24 '17 at 06:37
`for(n = 0; n < 2*size_arr; n++){ sort_arr[n] = 0; }` should be `memset(sort_arr, 0, sizeof sort_arr);` or the end statement should be `n < 2 * size_arr + 1`. — mch, Jul 24 '17 at 06:41

score 1 · Answer 1 · answered Jul 24 '17 at 06:42

I'm not sure this solves all problems but it is a problem you must fix.

This code

    int next_R, next_L = index;
    while(sort_arr[next_R] != 0 && next_R <= 2*size_arr)

has undefined behavior as next_R is uninitialized.

Maybe you want:

    int next_R = index, next_L = index;
                 ^^^^^
    while(sort_arr[next_R] != 0 && next_R <= 2*size_arr)

In any case you have to initialize next_R before using it.

I also find this line strange:

printArray(arr, size_arr);
           ^^^

Seems you are printing the original array instead of the sorted array.

May be you want:

printArray(sort_arr, size_arr);
           ^^^^^

BLUEPIXY · Answer 2 · 2017-07-24T13:20:24.043

like this

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

void printArray(int arr[], int len){
    while(len--)
        printf("%d ", *arr++);
    printf("\n");
}

int main(void){
    int size_arr = 10;
    int arr[size_arr];
    int sort_arr[2 * size_arr + 1];

    for(int i = 0; i < size_arr; ++i)
        arr[i] = -50 + rand() % (100 + 1);
    puts("before:");
    printArray(arr, size_arr);

    int left, right;
    sort_arr[left = right = size_arr] = arr[0];

    for (int n = 1; n < size_arr; ++n){
        int v = arr[n];
        if(v <= sort_arr[left]){
            sort_arr[--left] = v;
        } else if(v >= sort_arr[right]){
            sort_arr[++right] = v;
        } else {
            int L = left, R = right, M, MV;
            while(L <= R){
                M = L + (R-L)/2;
                MV = sort_arr[M];
                if(MV < v)
                    L = M + 1;
                else if(v < MV)
                    R = M - 1;
                else
                    break;
            }
            //M: insert position
            enum { LEFT, RIGHT } CHOICE;
            if(v == MV){
                int ML = M, MR = M;
                while(sort_arr[ML-1] == sort_arr[ML])
                    --ML;
                while(sort_arr[MR] == sort_arr[MR+1])
                    ++MR;
                if( ML-left >= right-MR){
                    M = MR+1;
                    CHOICE = RIGHT;
                } else {
                    M = ML;
                    CHOICE = LEFT;
                }
            } else if(v > MV){
                ++M;
                CHOICE = M-left+1 > right-M;// ? RIGHT : LEFT;
            } else {
                CHOICE = M-left-1 > right-M;// ? RIGHT : LEFT;
            }
            if(CHOICE == RIGHT){
                memmove(sort_arr + M+1, sort_arr + M, (right-M+1)*sizeof(v));
                sort_arr[M] = v;
                ++right;
            } else {
                memmove(sort_arr + left-1, sort_arr + left, (M-left)*sizeof(v));
                sort_arr[M-1] = v;
                --left;
            }
        }
    }
    puts("after:");
    printArray(sort_arr + left, size_arr);
    return 0;
}

chqrlie · Accepted Answer · 2017-07-24T14:10:38.253

There are some problems in your code:

when you scan the file in the first pass, you should count the number of integers instead of the number of characters.
when inserting, your loops are off by one: the tests should read while (L_move < index) and while (R_move >= index)
while (!feof(in)) is always wrong, you should instead write while (fscanf(in, "%d", &arr[n]) == 1) {...
you should probably allocate the arrays arr and sort_arr instead of defining them as VLAs with automatic storage to prevent undefined behavior on large input files.
you should use binary search into the sorted portion, otherwise your algorithm has a basic complexity of O(N²) that dwarfs the small gain obtained from the minimisation of the insertion phase.

Here is the code:

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

void print_array(const int arr[], int len) {
    for (int j = 0; j < len; j++)
        printf("%d%c", arr[j], " \n"[j == len - 1]);
}

int main(void) {
    FILE *in;
    int size_arr, n, start;
    int value;

    if ((in = fopen("data_a5.txt", "r")) == NULL) {
        printf("Cannot open input file %s\n", "data_a5.txt");
        exit(1);
    }
    for (size_arr = 0; fscanf(in, "%d", &value) == 1; size_arr++)
        continue;

    rewind(in);

    int *arr = calloc(2 * size_arr + 1, sizeof(*arr));
    if (arr == NULL) {
        printf("Cannot allocate memory for %d entries\n", size_arr);
        exit(1);
    }

    start = size_arr;
    for (n = 0; n < size_arr && fscanf(in, "%d", &value) == 1; n++) {
        /* insert value into the sorted array */
        int a, b;
        for (a = start, b = start + n; a < b;) {
            int mid = a + (b - a) / 2;
            if (arr[mid] < value) {
                a = mid + 1;
            } else {
                b = mid;
            }
        }
        /* insert value at offset b */
        if (b - start < start + n - b) {
            /* shift left portion to the left */
            for (int i = start--; i < b; i++) {
                arr[i - 1] = arr[i];
            }
            b--;
        } else {
            /* shift right portion to the right */
            for (int i = start + n + 1; --i > b;) {
                arr[i] = arr[i - 1];
            }
        }
        arr[b] = value;
    }
    fclose(in);

    print_array(arr + start, n);
    free(arr);
    return 0;
}

Two-Way Insertion Sort not sorting

3 Answers3