Having issues with generic Insertion Sort implementation

[vittorioc98]

Hello guys, i hope you are all good!

If you have time for me, I'm implementing a generic library using Insertion Sort:

#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <time.h>
#include <stdio.h>
#include <stddef.h>

#define INIT_ARR_SIZE 10

int _Char_comparator(void *p1, void *p2);
void _Char_swap(void *p1, void *p2);
void insertionSort(void *a, int start, int end, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic);
int binarySearch(void *arr, void *item, int left, int right, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic);
void print_char_array(char **a, int size);

int main(int argc, char const *argv[])
{
    int _char_index = 0;
    
    char **_char_arr = (char **)malloc(INIT_ARR_SIZE * sizeof(char *));
    char *line = (char *)malloc(100 * sizeof(char));
    
    FILE *_file = fopen("/Users/vitto/Desktop/words.txt", "r");
    while (fscanf(_file, "%[^\n]", line) != EOF)
    {
        getc(_file);
        _char_arr[_char_index] = strcpy((char *)calloc(strlen(line) + 1, sizeof(char)), line);
        _char_index++;
    }
    fclose(_file);
    
    printf("\n------------BEFORE----------------\n");
    print_char_array(_char_arr, INIT_ARR_SIZE);
    
    insertionSort(_char_arr, 0, INIT_ARR_SIZE, _Char_comparator, _Char_swap, sizeof(char *));
    
    printf("\n------------AFTER----------------\n");
    print_char_array(_char_arr, INIT_ARR_SIZE);
    
    for (int i = 0; i < INIT_ARR_SIZE; i++){
        printf("i try to dealloc the index: %d\n", i);
        free(_char_arr[i]);
    }
    
    free(_char_arr);

    return 0;
}

// INSETION SORT DEFINITION

void insertionSort(void *a, int start, int end, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic)
{
    int i, loc, j;
    
    for (i = (start + 1); i < end; ++i)
    {
        j = i - 1;
        
        void *selected = a + (i * atomic);
        
        loc = binarySearch(a, selected, start, j, comparator, swap, atomic);
        
        while (j >= loc)
        {
            swap(a + ((j + 1) * atomic), a + (j * atomic));
            j--;
        }
    }
}

int binarySearch(void *arr, void *item, int left, int right, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic)
{
    if (right <= left)
        return (comparator(item, arr + (left * atomic)) > 0) ? (left + 1) : left;
    
    int mid = (left + right) / 2;
    
    if (comparator(item, arr + (mid * atomic)) == 0)
        return mid + 1;
    
    if (comparator(item, arr + (mid * atomic)) > 0)
        return binarySearch(arr, item, mid + 1, right, comparator, swap, atomic);
    
    return binarySearch(arr, item, left, mid - 1, comparator, swap, atomic);
}

//COMPARATOR
int _Char_comparator(void *p1, void *p2)
{
    return strcmp(((char **)p1)[0], ((char **)p2)[0]);
}

//SWAP FUNCTION

void _Char_swap(void *p1, void *p2)
{
    char *t = (char *)malloc(100 * sizeof(char));
    strcpy(t, p1);
    strcpy(p1, p2);
    strcpy(p2, t);
    free(t);
}

/* PRINTING FUNCTIONS */

void print_char_array(char **a, int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("pointer: %p, word: %s\n", &a[i],  a[i]);
    printf("\n");
}

I'm testing only chars for now.
Im pulling data from a txt file which have lines of random words like this:

the
of
to
and
a
in
is
it
you
that
he
was
for
on
are
with
as

The sorting works, but sometimes some array slots are empty.. like this execution:

------------BEFORE----------------
pointer: 0x100300290, word: the
pointer: 0x100300298, word: of
pointer: 0x1003002a0, word: to
pointer: 0x1003002a8, word: and
pointer: 0x1003002b0, word: a
pointer: 0x1003002b8, word: in
pointer: 0x1003002c0, word: is
pointer: 0x1003002c8, word: it
pointer: 0x1003002d0, word: you
pointer: 0x1003002d8, word: that


------------AFTER----------------
pointer: 0x100300290, word: a
pointer: 0x100300298, word: and
pointer: 0x1003002a0, word: 
pointer: 0x1003002a8, word: is
pointer: 0x1003002b0, word: it
pointer: 0x1003002b8, word: of
pointer: 0x1003002c0, word: that
pointer: 0x1003002c8, word: the
pointer: 0x1003002d0, word: to
pointer: 0x1003002d8, word: you

As you can see, the 3rd index is empty.. i think that the issues is in the swap, but i'm not sure because i'm properly use the strcpy, i can't see any issue there.

and at the end, when i try to dealloc the al arr[i], it gives me this error:

prova(1509,0x10007f000) malloc: *** error for object 0x100102f00: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug

I accept any suggestion any kind of criticism to improve the code.
Thank you all !!!

[salem c]

> char **_char_arr = (char **)malloc(INIT_ARR_SIZE * sizeof(char *));
Remove the cast on the return result of malloc.
If it complains about "cannot convert void*", then it means you're using a C++ compiler to compile your C code.
You should compile it with a C compiler.

    char *t = (char *)malloc(100 * sizeof(char));
    strcpy(t, p1);
    strcpy(p1, p2);
    strcpy(p2, t);
    free(t);

The problem here is if you swap a short string with a long string, you're going to end up overwriting memory.

[seeplus]

Why is _Char_swap() trying to copy/swap null-terminated c strings? Why not just swap the pointers of _char_array?

Also, what's with starting variable names with a _? Much of the standard library uses names starting with _. At some point you might run into problems. It's best to avoid starting names with _.

If you use calloc() rather than malloc(), then 1) you can specify directly the number of elements and their size - rather than having to a multiplication and 2) the allocated memory is initialised to 0.

[seeplus]

There are issues re the use of pointers. Don't pass by void* to avoid having to pass the right pointer type! If the correct pointer type is passed, then adding to the pointer doesn't need to know the size - the add adds correctly in units of the type.

Using VS2019, this compiles and runs OK as c:

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable : 5105)

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

#define INIT_ARR_SIZE 20
#define LINE_SIZE 100

typedef int(*Comp)(char**, char**);
typedef void(*Swap)(char**, char**);

int _Char_comparator(char** p1, char** p2);
void _Char_swap(char** p1, char** p2);
void insertionSort(char** a, int start, int end, Comp comp, Swap swap);
int binarySearch(char** arr, char** item, int left, int right, Comp comp, Swap swap);
void print_char_array(char** a, int size);

int main(int argc, char const* argv[])
{
	int _char_index = 0;

	char** _char_arr = (char**)calloc(INIT_ARR_SIZE, sizeof(char*));
	char* line = (char*)calloc(LINE_SIZE, sizeof(char));

	FILE* _file = fopen("untitled.txt", "r");

	if (_file == NULL)
		return puts("Cannot open file"), 1;

	for (; _char_index < INIT_ARR_SIZE && fscanf(_file, "%[^\n]", line) != EOF; getc(_file))
		_char_arr[_char_index++] = strcpy((char*)calloc(strlen(line) + 1, sizeof(char)), line);

	fclose(_file);

	printf("\n------------BEFORE----------------\n");
	print_char_array(_char_arr, _char_index);

	insertionSort(_char_arr, 0, _char_index, _Char_comparator, _Char_swap);

	printf("\n------------AFTER--------- -------\n");
	print_char_array(_char_arr, _char_index);

	for (int i = 0; i < _char_index; ++i)
		free(_char_arr[i]);

	free(_char_arr);
	free(line);

	return 0;
}

// INSETION SORT DEFINITION
void insertionSort(char** a, int start, int end, Comp comparator, Swap swap)
{
	for (int i = (start + 1); i < end; ++i) {
		int j = i - 1;
		char** selected = a + i;
		int loc = binarySearch(a, selected, start, j, comparator, swap);

		for (; j >= loc; --j)
			swap(a + j + 1, a + j);
	}
}

int binarySearch(char** arr, char** item, int left, int right, Comp comparator, Swap swap)
{
	if (right <= left)
		return (comparator(item, arr + left) > 0) ? (left + 1) : left;

	int mid = (left + right) / 2;

	if (comparator(item, arr + mid) == 0)
		return mid + 1;

	if (comparator(item, arr + mid) > 0)
		return binarySearch(arr, item, mid + 1, right, comparator, swap);

	return binarySearch(arr, item, left, mid - 1, comparator, swap);
}

//COMPARATOR
int _Char_comparator(char** p1, char** p2)
{
	return strcmp(p1[0], p2[0]);
}

//SWAP FUNCTION
void _Char_swap(char** p1, char** p2)
{
	char* t = *p1;

	*p1 = *p2;
	*p2 = t;
}

/* PRINTING FUNCTIONS */

void print_char_array(char** a, int size)
{
	for (int i = 0; i < size; ++i)
		printf("pointer: %p, word: %s\n", &a[i], a[i]);

	puts("");
}

------------BEFORE----------------
pointer: 0047EEC0, word: the
pointer: 0047EEC4, word: of
pointer: 0047EEC8, word: to
pointer: 0047EECC, word: and
pointer: 0047EED0, word: a
pointer: 0047EED4, word: in
pointer: 0047EED8, word: is
pointer: 0047EEDC, word: it
pointer: 0047EEE0, word: you
pointer: 0047EEE4, word: that
pointer: 0047EEE8, word: he
pointer: 0047EEEC, word: was
pointer: 0047EEF0, word: for
pointer: 0047EEF4, word: on
pointer: 0047EEF8, word: are
pointer: 0047EEFC, word: with
pointer: 0047EF00, word: as


------------AFTER--------- -------
pointer: 0047EEC0, word: a
pointer: 0047EEC4, word: and
pointer: 0047EEC8, word: are
pointer: 0047EECC, word: as
pointer: 0047EED0, word: for
pointer: 0047EED4, word: he
pointer: 0047EED8, word: in
pointer: 0047EEDC, word: is
pointer: 0047EEE0, word: it
pointer: 0047EEE4, word: of
pointer: 0047EEE8, word: on
pointer: 0047EEEC, word: that
pointer: 0047EEF0, word: the
pointer: 0047EEF4, word: to
pointer: 0047EEF8, word: was
pointer: 0047EEFC, word: with
pointer: 0047EF00, word: you

[vittorioc98]

Hello seeplus

It works but im a bit confused about this line: void _Char_swap(char** p1, char** p2)

My idea is: I need to swap 2 char pointer. Why should i declare the function with char**??
When i call the function, I'm passing 2 pointer to a single array of char, not a 2D array, for example here: swap(a + j + 1, a + j);. Im not passing the entire 2D array.

Another example here: void insertionSort(char** a, int start, int end, Comp comp, Swap swap); I'm declaring the function that needs a 2D array, and when i call the function i actually pass 2D array: insertionSort(_char_arr, 0, _char_index, _Char_comparator, _Char_swap); "_char_arr" is actually a pointer to a 2D array.

I hope i was clear to explain my thoughs and thank you for the help.

[seeplus]

I'm passing 2 pointer to a single array of char

array of char is of type char*. So a pointer to this is char**.

Also note that params are passed by value. So any changes to these are not reflected back to the calling function. If a pointer to a pointer, then dereference the pointer once and what is then changed is reflected back to the caller.

In this case, don't think of these as a 2D array. Think of them as an array of pointers to pointers. If you used a type say String that had a def of char* for the words, then used String instead of char* and String* for pointer to String, you then have _char_array of type String* as opposed to char**.

Not using correct pointers was one issue with the original code.

[Ganado]

Separate from your actual issue, but you should avoid using a leading underscore for an identifier in the global scope. (Especially underscore followed by capital letter, which is always reserved.)

[vittorioc98]

It's all clear. Thank you for the all advices you have given to me.

P.S I going to remove the undescore declaration sorry ahahah.

[dhayden]

vittorioc98, the main problem is that you're sorting all INIT_ARR_SIZE items in the array instead of only the _char_index items that were actually filled. Every reference to INIT_ARR_SIZE after line 24 should be _char_index instead.

Also, INIT_ARR_SIZE is 10, meaning you have space for 10 items in the array, but your sample input has 17 words. So you access the array out of bounds and it crashes, at least on my computer. I changed it to 100.

Exactly what does binarySearch do? Is right the last item in the search space, or one past the last item? When the item isnt' found, does it return the location just before where it goes, or just after? These are important details and I strongly recommend that you document them in a comment. Right now when you find the item, you return the position one past the location, and if you don't find it, you return the left bound or left+1? Also you should only make one call to comparator() in each call to binarySeach. Sometimes you call it twice.

That's all too confusing to me, so I rewrote it to do this:

// Search for item in p between left and right. "Right" is one index
// past the last valid item.  Returns the location of "item" if found,
// or the location of the next greatest item. 

In C++ it's always good to express the upper bound as "one past the end" since this is what the standard library does. You'll grow to expect this convention.

Here is your code with these changes.

#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <time.h>
#include <stdio.h>
#include <stddef.h>

#define INIT_ARR_SIZE 100

int char_comparator(void *p1, void *p2);
void char_swap(void *p1, void *p2);
void insertionSort(void *a, int start, int end, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic);
int binarySearch(void *arr, void *item, int left, int right, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic);
void print_char_array(char **a, int size);

int main(int argc, char const *argv[])
{
    int char_index = 0;

    char **char_arr = (char **)malloc(INIT_ARR_SIZE * sizeof(char *));
    char *line = (char *)malloc(100 * sizeof(char));
    
    while (fscanf(stdin, "%[^\n]", line) != EOF)
    {
        getc(stdin);
        char_arr[char_index] = strcpy((char *)calloc(strlen(line) + 1, sizeof(char)), line);
        char_index++;
    }
    
    printf("\n------------BEFORE----------------\n");
    print_char_array(char_arr, char_index);

    insertionSort(char_arr, 0, char_index, char_comparator, char_swap, sizeof(char *));
    
    printf("\n------------AFTER----------------\n");
    print_char_array(char_arr, char_index);
    
    for (int i = 0; i < char_index; i++){
	free(char_arr[i]);
    }
    
    free(char_arr);

    return 0;
}

// INSETION SORT DEFINITION

void insertionSort(void *p, int start, int end, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic)
{
    int i, loc, j;
    char *a = (char*)p;		// for pointer arithmentic
    
    for (i = (start + 1); i < end; ++i)
    {
        j = i - 1;
        
        void *selected = a + (i * atomic);
        
        loc = binarySearch(a, selected, start, i, comparator, swap, atomic);
        
	printf("\n%s goes before %s at position %d\n", *(char **)selected, *(char**)(a+loc*atomic), loc);
        while (j >= loc)
        {
            swap(a + ((j + 1) * atomic), a + (j * atomic));
            j--;
        }
	print_char_array((char **)p, end);

    }
}

// Search for item in p between left and right. "Right" is one index
// past the last valid item.  Returns the location of "item" if found,
// or the location just past where it should go.
int binarySearch(void *p, void *item, int left, int right, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic)
{
    char *arr = (char*)p;	// for pointer arithmetic

    // printf("BinarySearch(%s, %d, %d)\n", *(char**)item, left, right);
    if (right <= left)
        return left;
    
    int mid = (left + right) / 2;
    int comp = comparator(item, arr + (mid * atomic));

    if (comp == 0) {
        return mid;
    } else if (comp > 0) {
        return binarySearch(arr, item, mid + 1, right, comparator, swap, atomic);
    } else {
	return binarySearch(arr, item, left, mid, comparator, swap, atomic);
    }
}

//COMPARATOR
int char_comparator(void *p1, void *p2)
{
    return strcmp(((char **)p1)[0], ((char **)p2)[0]);
}

//SWAP FUNCTION

void char_swap(void *p1, void *p2)
{
    char **s1 = (char**)p1;
    char **s2 = (char**)p2;
    char *t = *s1;
    *s1 = *s2;
    *s2 = t;
}

/* PRINTING FUNCTIONS */

void print_char_array(char **a, int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("pointer: %p, word: %s\n", &a[i],  a[i]);
    printf("\n");
}

[seeplus]

If you pass as a 'proper' type - char, char* or char** instead of void*, you don't also need to use atomic. You can just add/subtract from the pointer.

char_arr is of type char** - but is passed as void* to functions and then cast to char* !

[dhayden]

I think the point is to make InsertionSort() generic so it will work with any size and type of data. I cast the void* to char* to allow pointer arithmetic in the function that doesn't know the type of the data. Here is another version that sorts an array of ints as well. I've removed some of the debugging code, notable the call to print_char_array() inside InsertionSort()

#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <time.h>
#include <stdio.h>
#include <stddef.h>

#define INIT_ARR_SIZE 100

int char_comparator(void *p1, void *p2);
void char_swap(void *p1, void *p2);
void insertionSort(void *a, int start, int end, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic);
int binarySearch(void *arr, void *item, int left, int right, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic);
void print_char_array(char **a, int size);

int main(int argc, char const *argv[])
{
    int char_index = 0;

    char **char_arr = (char **)malloc(INIT_ARR_SIZE * sizeof(char *));
    char *line = (char *)malloc(100 * sizeof(char));
    
    while (fscanf(stdin, "%[^\n]", line) != EOF)
    {
        getc(stdin);
	if (strcmp(line, ".END.") == 0) break;
        char_arr[char_index] = strcpy((char *)calloc(strlen(line) + 1, sizeof(char)), line);
        char_index++;
    }
    
    printf("\n------------BEFORE----------------\n");
    print_char_array(char_arr, char_index);

    insertionSort(char_arr, 0, char_index, char_comparator, char_swap, sizeof(char *));
    
    printf("\n------------AFTER----------------\n");
    print_char_array(char_arr, char_index);
    
    for (int i = 0; i < char_index; i++){
	free(char_arr[i]);
    }
    
    free(char_arr);

    // Now do it again with an array of integers
    void print_int_array(int *array, int size);
    int int_comparator(void *p1, void *p2);
    void int_swap(void *p1, void *p2);

    int arr[100];
    int sz{0};
    while (scanf("%d", &arr[sz]) == 1) {
	++sz;
    }

    printf("\n------------BEFORE----------------\n");
    print_int_array(arr, sz);

    insertionSort(arr, 0, sz, int_comparator, int_swap, sizeof(int));
    
    printf("\n------------AFTER----------------\n");
    print_int_array(arr, sz);

    
    return 0;
}

void print_int_array(int *array, int size)
{
    for (int i=0; i<size; ++i) {
	printf("%d\n", array[i]);
    }
}

int int_comparator(void *p1, void *p2)
{
    int *i1 = (int*)p1;
    int *i2 = (int*)p2;
    if (*i1 < *i2) return -1;
    if (*i1 > *i2) return 1;
    return 0;
}

void int_swap(void *p1, void *p2)
{
    int *i1 = (int*)p1;
    int *i2 = (int*)p2;
    int tmp = *i1;
    *i1 = *i2;
    *i2 = tmp;
}


    // INSETION SORT DEFINITION

void insertionSort(void *p, int start, int end, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic)
{
    int i, loc, j;
    char *a = (char*)p;		// for pointer arithmentic
    
    for (i = (start + 1); i < end; ++i)
    {
        j = i - 1;
        
        void *selected = a + (i * atomic);
        
        loc = binarySearch(a, selected, start, i, comparator, swap, atomic);
        
        while (j >= loc)
        {
            swap(a + ((j + 1) * atomic), a + (j * atomic));
            j--;
        }
    }
}

// Search for item in p between left and right. "Right" is one index
// past the last valid item.  Returns the location of "item" if found,
// or the location just past where it should go.
int binarySearch(void *p, void *item, int left, int right, int (*comparator)(void *, void *), void (*swap)(void *, void *), size_t atomic)
{
    char *arr = (char*)p;	// for pointer arithmetic

    fflush(stdout);
    if (right <= left)
        return left;
    
    int mid = (left + right) / 2;
    int comp = comparator(item, arr + (mid * atomic));

    if (comp == 0) {
        return mid;
    } else if (comp > 0) {
        return binarySearch(arr, item, mid + 1, right, comparator, swap, atomic);
    } else {
	return binarySearch(arr, item, left, mid, comparator, swap, atomic);
    }
}

//COMPARATOR
int char_comparator(void *p1, void *p2)
{
    return strcmp(((char **)p1)[0], ((char **)p2)[0]);
}

//SWAP FUNCTION

void char_swap(void *p1, void *p2)
{
    char **s1 = (char**)p1;
    char **s2 = (char**)p2;
    char *t = *s1;
    *s1 = *s2;
    *s2 = t;
}

/* PRINTING FUNCTIONS */

void print_char_array(char **a, int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("pointer: %p, word: %s\n", &a[i],  a[i]);
    printf("\n");
}

Input:

the
of
to
and
a
in
is
it
you
that
he
was
for
on
are
with
as
.END.
1234
4
5
3
587
3
1
6
-33

Output:

------------BEFORE----------------
pointer: 0x6000003d0, word: the
pointer: 0x6000003d8, word: of
pointer: 0x6000003e0, word: to
pointer: 0x6000003e8, word: and
pointer: 0x6000003f0, word: a
pointer: 0x6000003f8, word: in
pointer: 0x600000400, word: is
pointer: 0x600000408, word: it
pointer: 0x600000410, word: you
pointer: 0x600000418, word: that
pointer: 0x600000420, word: he
pointer: 0x600000428, word: was
pointer: 0x600000430, word: for
pointer: 0x600000438, word: on
pointer: 0x600000440, word: are
pointer: 0x600000448, word: with
pointer: 0x600000450, word: as


------------AFTER----------------
pointer: 0x6000003d0, word: a
pointer: 0x6000003d8, word: and
pointer: 0x6000003e0, word: are
pointer: 0x6000003e8, word: as
pointer: 0x6000003f0, word: for
pointer: 0x6000003f8, word: he
pointer: 0x600000400, word: in
pointer: 0x600000408, word: is
pointer: 0x600000410, word: it
pointer: 0x600000418, word: of
pointer: 0x600000420, word: on
pointer: 0x600000428, word: that
pointer: 0x600000430, word: the
pointer: 0x600000438, word: to
pointer: 0x600000440, word: was
pointer: 0x600000448, word: with
pointer: 0x600000450, word: you

------------BEFORE----------------
1234
4
5
3
587
3
1
6
-33

------------AFTER----------------
-33
1
3
3
4
5
6
587
1234