Generic Bubble sort program using pointers

Question

From my Previous Question :

Segmentation Fault in Bubble Sort

I fixed the problem and I got the Following code

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

void bubble_sort (void* base, 
                  size_t num, 
                  size_t width,
                  int (*compar)(const void*,const void*)){
    int i,j,k;
    unsigned char *ptr = base;
    unsigned char tmp[256];

    if(num < 2 || width == 0)
        return;

    for(i = num-1; i >= 0; i--)
    {
        for(j = 1; j <= i; j++)
        {
            k = compar((void*)(ptr + width * (j-1)), (void*)(ptr + width * j));
            if(k > 0)
            {
                memcpy(tmp, ptr + width*(j-1), width);
                memcpy(ptr + width*(j-1), ptr + width*j, width);
                memcpy(ptr + width * j, tmp, width);
            }
        }
    }
}

int compare_int(const void *a, const void *b)
{
    int *c = (int *)a;
    int *d = (int *)b;
    return *c - *d;
}

int compare_string(const void *a, const void *b)
{
    const char *c = (char *)a;
    const char *d = (char *)b;
    return strcmp(c, d);
}

Now this works perfectly with :

1. Int, Long etc. Arrays like int a[] = {1, 3, 4, 52, 2, 3};
2. char arrays like char a[5][20] = { "jhsa", "asndb", "drtfe", "nhurh", "bvhr"};

But I want to implement it with char * arrays like:

1. char *a[] = { "jhsa", "asndb", "drtfe", "nhurh", "bvhr"}

Tried a bit and ran into segmentation fault
so need some help.

Answer 1

You're declaring the variable 'a' as a char pointer (string). But what you have is an array of strings.

Hence 'a' should be something like this

char *a[] = { "jhsa", "asndb", "drtfe", "nhurh", "bvhr"};

Also, you should give your variables more meaningful names. In this case strings or words would be clearer.

Answer 2

First note declaration:

char *a = { "jhsa", "asndb", "drtfe", "nhurh", "bvhr"};

is incorrect it should be like:

char *a[] = { "jhsa", "asndb", "drtfe", "nhurh", "bvhr"}; 

That is array of char pointers. And each index in a[i] points to an string literal.

The problem is in your comparison function. Your first two arrays are array of values whereas a[] is an array of pointers. read difference between char* str[] and char str[][] and how both stores in memory? to understand how memory organization of char* a[] is different than char[][] (a two dimension continue allocated memory organization).

What happens in compare_() functions you passes address of a[i] (but doesn't pass a[i] it self). It works find when a[i] is a values address e.g. for int[] and char[][] whereas in case of char*[] you are not passing address of value instead passing address of address of value. I think your main confusion is between passing between 2D chars array char[][] and and array of literal strings char*[].

First understand what are you passing to comparison function, suppose if you have following array then you are passing address of content x, y, z (that are &a[i]) but not x, y, z (that is a[i]).

           a      
        +--------+
 343    |        |
        | a[0]=x | 
        |        |
        +--------+
        |        |
 347    | a[1]=y |
        |        |
        +--------+
        |        |
 351    | a[2]=z |
        |        |
        |        |
        +--------+
   * you are passing &a[i]

Now look at memory organization in case of char a[5][20], due to continue memory organization value of &a[i] and a[i] are same. Check following code and its output:

#include<stdio.h>
int main(){
 char a[5][20] = { "jhsa", "asndb", "drtfe", "nhurh", "bvhr"};
 int i = 0;
 for(i = 0; i < 5; i++)
    printf(
        "&a[i] = %p, a[i] = %p, *a[i] = %c, string a[i] = \"%s\"\n", 
        (void*)&a[i], // you are passingg this &a[i]
        (void*)a[i],  // compare &a[i] and a[i] address value
        *a[i], 
        a[i]
    );
 return 0;
}

Output:

$ gcc x.c -Wall -pedantic -o x
$ ./x
&a[i] = 0x7fff1dfb28b0, a[i] = 0x7fff1dfb28b0, *a[i] = j, string a[i] = "jhsa"
&a[i] = 0x7fff1dfb28c4, a[i] = 0x7fff1dfb28c4, *a[i] = a, string a[i] = "asndb"
&a[i] = 0x7fff1dfb28d8, a[i] = 0x7fff1dfb28d8, *a[i] = d, string a[i] = "drtfe"
&a[i] = 0x7fff1dfb28ec, a[i] = 0x7fff1dfb28ec, *a[i] = n, string a[i] = "nhurh"
&a[i] = 0x7fff1dfb2900, a[i] = 0x7fff1dfb2900, *a[i] = b, string a[i] = "bvhr"

Although &a[i] and a[i] are not same but value-wise same. To understand that are differences read Difference between &str and str, when str is declared as char str[10]?.

But value of &a[i] and a[i] are not same in case of char*[] Check following code: y.c (similar to above x.c) and its output:

#include<stdio.h>
int main(){
 char *a[] = {"jhsa", "asndb", "drtfe", "nhurh", "bvhr"};
 int i = 0;
 for(i = 0; i < 5; i++)
    printf("&a[i] = %p, a[i] = %p, *a[i] = %c, string a[i] = \"%s\"\n", 
        (void*)&a[i],
        (void*)a[i], 
        *a[i], 
        a[i]); 
 return 0;
}

output:

$ gcc y.c -Wall -pedantic -o y
$ ./y
&a[i] = 0x7fffa4674730, a[i] = 0x400690, *a[i] = j, string a[i] = "jhsa"
&a[i] = 0x7fffa4674738, a[i] = 0x400695, *a[i] = a, string a[i] = "asndb"
&a[i] = 0x7fffa4674740, a[i] = 0x40069b, *a[i] = d, string a[i] = "drtfe"
&a[i] = 0x7fffa4674748, a[i] = 0x4006a1, *a[i] = n, string a[i] = "nhurh"
&a[i] = 0x7fffa4674750, a[i] = 0x4006a7, *a[i] = b, string a[i] = "bvhr"

Now, notice values are different for &a[i] and a[i] (infact offset address values shows segments are different &a[i] get address space in stack whereas a[i] gets address space where string literal stores, but that is different matter).

So, in string comparison function: int compare_string() that statement return strcmp(c, d); will not work for char*[] and it should be something like return strcmp(*c, *d); (although it was working for char[][] where value of &[i] and a[i] are same first case I compiled code using -Wall and -pedantic it doesn't emits any warning so I believe no problem to use it as string address - but I am not sure too). And hence you need a separate version of compare_string_ for char*[] in which you call strcmp(*c, *d);. But now problem is function argument are cont void* and dereferencing cont is undefined behaviour. To rectify your code I removed const from every where and add a new function int compare_string_v2( void *a, void *b) for char* a[] as follows:

int compare_string_v2( void *a,  void *b)
{
    char **c = a;
    char **d = b;
    return strcmp(*c, *d);
}

just compile your code as: $ gcc code.c -Wall -pedantic -o code it should work fine. Here you can check @working instance of code

Answer 3

You can use this code, the simpler the better ! First write Isless Function in your main(), some thing like this:

static int IsLess(void* num1, void* num2)
{
   return (*(int*)num1 > *(int*)num2) ? TRUE : FALSE;
}

then use this code.

static void Swap(void* ptr1, void* ptr2, size_t _sizeof)
{
void* temp = malloc(_sizeof);
memcpy(temp,ptr2, _sizeof);
memcpy(ptr2,ptr1, _sizeof);
memcpy(ptr1,temp, _sizeof);
free(temp);
}
static void BubbleUp(int _end, void* _arr[], size_t _sizeofitem, fp _IsLess)
{ 
size_t j;
for(j = 0; j < _end; ++j)
{
    if(_IsLess((char*)_arr + j*_sizeofitem, (char*)_arr + (j+1)*_sizeofitem))
    {
        Swap((char*)_arr + j*_sizeofitem, (char*)_arr + (j+1)*_sizeofitem, _sizeofitem);
    }
}
}
void SortGen(void* _arr, size_t _sizeofitem, size_t _numOfItems, fp _IsLess)
{
int i;
if(_arr == NULL)
{
    return;
}
for(i = (int)_numOfItems -1; i >= 0; i--)
{
    BubbleUp(i, _arr, _sizeofitem, _IsLess);
}
}