Mergesort An Array of Strings in C

Question

I'm trying to implement a merge sort for an array of strings entered from standard input, and am at a loss at what is wrong. Right now I'm facing a segmentation fault. How should I modify my code?

main() {
    char temp;
    int i = 0;
    char Strings[NUM][LEN];

    printf("Please enter %d strings, one per line:\n", NUM);
    for (i; i < 25; i++) {
        fgets(&Strings[i][0], LEN, stdin);
    }

    i = 0;
    puts("\nHere are the strings in the order you entered:");
    for (i; i < 25; i++) {
        printf("%s\n", Strings[i]);
    }

    mergesort(Strings, NUM);

    i = 0;
    puts("\nHere are the strings in alphabetical order");
    for (i; i < 25; i++) {
        printf("%s\n", Strings[i]);
    }
}

int mergesort(char list[NUM][LEN], int length) { // First part
    mergesort_r(0, length, list);
    return 0;
}

int mergesort_r(int left, int right, char list[NUM][LEN]) { // Overloaded portion
    if (right - left <= 1) {
        return 0;
    }

    int left_start  = left;
    int left_end    = (left + right) / 2;
    int right_start = left_end;
    int right_end   = right;

    mergesort_r( left_start, left_end, list);
    mergesort_r( right_start, right_end, list);

    merge(list, left_start, left_end, right_start, right_end);
}

int merge(char list[NUM][LEN], int left_start, int left_end, int right_start, int right_end) {

    int left_length = left_end - left_start;
    int right_length = right_end - right_start;

    char *left_half[left_length];
    char *right_half[right_length];

    int r = 0;
    int l = 0;
    int i = 0;

    for (i = left_start; i < left_end; i++, l++) {
        strcpy(left_half[l], list[i]);
    }

    for (i = right_start; i < right_end; i++, r++) {
        strcpy(right_half[r], list[i]);
    }

    for (i = left_start, r = 0, l = 0; l < left_length && r < right_length; i++) {
        if (strcmp(left_half[l], right_half[r]) < 0) {
            strcpy(list[i], left_half[l++]);
        } else {
            strcpy(list[i], right_half[r++]);
        }
    }

    for ( ; l < left_length; i++, l++) {
        strcpy(list[i], left_half[l]);
    }
    for ( ; r < right_length; i++, r++) {
        strcpy(list[i], right_half[r]);
    }
    return 0;
}

I'm not sure if it's that I'm passing in my array incorrectly, or maybe it's that I am not even executing swaps properly. I'm at my wits end with this and could use some advice.

Perhaps you should include the output of what you are seeing -- particularly if you run under a debugger so you can get more detailed information about the segfault. That seems nicer than asking people to read your (relatively small, but still) haystack of code looking for a needle of crash. — mah
– mah, Commented Nov 20, 2013 at 20:42
strcpy(left_half[l] Memory destination indicated by the pointer is not ensured — BLUEPIXY
– BLUEPIXY, Commented Nov 20, 2013 at 22:19

BLUEPIXY · Accepted Answer · 2013-11-20 22:37:48Z

3

should be

char left_half[left_length][LEN];
char right_half[right_length][LEN];

answered Nov 20, 2013 at 22:37

BLUEPIXY

40.3k7 gold badges37 silver badges73 bronze badges

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

Comments

Shikhar Srivastava · Accepted Answer · 2015-11-08 14:40:33Z

#include<stdio.h>
#include<stdlib.h>
#include<string.h> //To use the string functions like strcmp and strcpy

#define MAX 10  // This is the default size of every string 

void Merge(char* arr[],int low,int mid,int high) //Merging the Array Function
{
    int nL= mid-low+1;
    int nR= high-mid;

    char** L=malloc(sizeof(char *)*nL);
    char** R=malloc(sizeof(char *)*nR);
    int i;
    for(i=0;i<nL;i++)
    {
        L[i]=malloc(sizeof(arr[low+i]));
        strcpy(L[i],arr[low+i]);
    }
    for(i=0;i<nR;i++)
    {
        R[i]=malloc(sizeof(arr[mid+i+1]));
        strcpy(R[i],arr[mid+i+1]);
    }
    int j=0,k;
    i=0;
    k=low;
    while(i<nL&&j<nR)
    {
        if(strcmp(L[i],R[j])<0)strcpy(arr[k++],L[i++]);
        else strcpy(arr[k++],R[j++]);
    }
    while(i<nL)strcpy(arr[k++],L[i++]);
    while(j<nR)strcpy(arr[k++],R[j++]);

}


void MergeSort(char* arr[],int low,int high) //Main MergeSort function
{
    if(low<high)
    {
        int mid=(low+high)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Merge(arr,low,mid,high);
    }
}


int main()
{
    printf("\nEnter the size of the array desired: ");
    int size;  //This is the String array size
    scanf("%d",&size);

    char** arr= malloc(sizeof(char *)* size); //Creating required string array
    printf("\nEnter the strings of the array: ");

    int i;
    for(i=0;i<size;i++)
    {
        arr[i]=malloc(sizeof(char)*MAX);
        printf("\nEnter String: ");
        scanf("%s",arr[i]);
    }
    MergeSort(arr,0,size-1);
    printf("\nThe Sorted Array is: ");
    for(i=0;i<size;i++)printf("%s ->",arr[i]);
    return 0;

}

This is a Working solution to the same problem. Hope it Helps! Cheers! :)

Shikhar · Accepted Answer · 2020-05-20 17:48:09Z

0

This solution of yours might give a memory error for long inputs or repeated executions. You need to free the allocated memory or not dynamically allocate it in the first place.

The latter is an easier option. What you can do is find the length of the longest string in the array of strings before hand and pass it as an argument to the merge sort and merge function.

Let's say that length is LEN.

Then instead of dynamically allocating memory for the L and R array, just declare it as:

char L[nL][LEN] and char R[nR][LEN].

It might take a slightly larger stack memory but avoids crashing the program.

answered May 20, 2020 at 17:48

Shikhar

1

Collectives™ on Stack Overflow

Mergesort An Array of Strings in C

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related