Merge sort of characters in string C

Question

I have this working merge-sort algorithm in C. But it works only for integers. When I tried to change int to char, i'm getting segfault.

Can you please help me, what should I change in this code, so I could use MergeSort like this:

char*str = "test_string";
MergeSort(str, 0, strlen(str)-1);

void Merge(int *array, int left, int mid, int right){

    int tempArray[right-left+1];
    int pos=0,lpos = left,rpos = mid + 1;

    while(lpos <= mid && rpos <= right){
            if(array[lpos] <= array[rpos]){
                    tempArray[pos++] = array[lpos++];
            }
            else{
                    tempArray[pos++] = array[rpos++];
            }
    }

    while(lpos <= mid)  tempArray[pos++] = array[lpos++];
    while(rpos <= right)tempArray[pos++] = array[rpos++];

    int iter;
    for(iter = 0;iter < pos; iter++){
            array[iter+left] = tempArray[iter];
    }

    return;
}

void MergeSort(int *array, int left, int right){
    int mid = (left+right)/2;

    if(left<right){
            MergeSort(array,left,mid);
            MergeSort(array,mid+1,right);
            Merge(array,left,mid,right);
    }
    return;
}

I'm lost. Thanks!

Hi. Asking people to spot errors in your code is not especially productive. You should use the debugger (or add print statements) to isolate the problem, by tracing the progress of your program, and comparing it to what you expect to happen. As soon as the two diverge, then you've found your problem. (And then if necessary, you should construct a minimal test-case.) — Oliver Charlesworth
– Oliver Charlesworth, Commented Dec 12, 2013 at 2:00

Mad Physicist · Accepted Answer · 2013-12-12 02:30:34Z

4

Change your declaration of array from int * to char * in both functions. Make tempArray a char[] instead of an int[]. You are trying to read memory that is 4x (or 8x) out of bounds at the end of the array, hence the seg-fault. Put another way, char is 1 byte (usually) while int is 4 or 8, so you are looking at items of a different size stacked next to each other. Also, do not pass in a const * for your string. Declaring a string as char*str = "test_string"; implies read-only memory on some systems. Use char str[] = "test_string"; instead. If you are not using strictly C, you can use C++ templates to make a function that works for int and char: http://www.codeproject.com/Articles/257589/An-Idiots-Guide-to-Cplusplus-Templates-Part-1

edited Dec 12, 2013 at 2:30

answered Dec 12, 2013 at 2:04

Mad Physicist

116k29 gold badges202 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Marek Teuchner Over a year ago

Thanks, I tried these changes, but still getting segfault. I'm using strictly C, so I can't use the C++ Template.

Iwillnotexist Idonotexist Over a year ago

I doubt that's the only reason why the segfault's happening. He's passing a const char* string literal (which is almost always in read-only protected memory) to a function that tries to modify it. If he were to use char str[] = "MyString", it would have a chance of working.

Iwillnotexist Idonotexist Over a year ago

@Marek Teuchner No problems!

Mad Physicist Over a year ago

@IwillnotexistIdonotexist, incorporated your advice into the answer. Thanks for the good point.

Prafulla Kumar Sahu · Accepted Answer · 2016-03-23 11:10:53Z

#include <stdio.h>

#include<ctype.h>

#include<string.h>

int Run_count=-1;

int main ( int argc , char *argv[] )
{ 

    /* if you dont want to use argv, put the elements in A yourself,
    size being the number of string*/

    /*L --> left side, R --> right side*/

    int i = 0;

    int size = argc-1;

    char *A[argc-1];

    for(i=1;i<=argc;i++){*(A+i-1) = argv[i];}

    Caller(A,size);

    for(i=0;i<size;i++){

        printf("%s\n", A[i]);

    }

    printf("%d",Run_count);
}

int Caller(char* A[] , int n){

    Run_count++;

    int sizeL, sizeR ,i;

    char *L[n/2+1] , *R[n-n/2+1];

    if (n < 2){return 1;}

    sizeL = n/2;
    sizeR = n - sizeL;

    for(i=0;i<sizeL;i++)  {L[i] = *(A+i);}
    for(i=0;i<n - n/2;i++)  {R[i] = *(A+i+n/2);}

    Caller( L, sizeL);
    Caller( R, sizeR);
    merger( L,sizeL, R,sizeR, A);
}

void merger(char* L[], int lengthL , char* R[] , int lengthR , char *A[]){

    int i, j, k ,t =0 ;

    for(k = 0 , j = 0; k < lengthL && j < lengthR ;t++){

        if(compare(*(L+k),*(R+j))){
            *(A+t) = *(L+k);
            k++;}

        else{*(A+t) = *(R+j);j++;}
    }

    while(k < lengthL ){
        *(A+t) = *(L+k); 
        k++;t++;
        }

    while(j < lengthR ){
        *(A+t) = *(R+j);
        j++;t++;}
}

int compare(char *line1 , char *line2 )
{
    int i;

    for(i = 0;*(line1 + i) != '\0' && *(line2 + i) != '\0' ;){
        if(isdigit(*(line1+i)) && isalpha(*(line2+i))){return 0;}

        else if(isdigit(*(line2+i)) && isalpha(*(line1+i))){return 1;}

        else if(*(line1 + i) > *(line2 + i)){return 0;}

        else if(*(line1 + i) == *(line2 + i)){i++;}

        else{return 1;}
    }
}

include stdio & ctype ,,, also the compare function gives more weightage to digits as compares to alphabets, as shown in the function compare

Collectives™ on Stack Overflow

Merge sort of characters in string C

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related