Create function which sorts 2 given sorted strings

Question

Given two sorted strings, I need to merge these strings to one string, and make it sorted. sort by the ASCII value. for example: acdty, berz => abcdertyz

My code:

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

char* PairSortedArrays(char a[], char b[]) {
    char* c = (char*)malloc((sizeof(a) + sizeof(b)) * sizeof(char));
    int i, aPos = 0, bPos = 0;

    for (i = 0; i < sizeof(*c); i++) {
        if ((int)(a[aPos]) <= (int)(b[bPos])) {
            c[i] = a[aPos];
            aPos++;
        }
        else {
            c[i] = b[bPos];
            bPos++;
        }
    }
    return c;
}

int main()
{
    printf("%s", PairSortedArrays("acdty", "berz"));
    return 0;
}

The first problem is with sizeof(a). if I code: printf("%d", sizeof(a)); it prints 8, while I expect it to print 5.

`char a[]` as function parameter is adjusted to `char *a` so `sizeof(a)` gives "size of pointer" as opposed to "size of array". — machine_1, Dec 29 '19 at 21:10
`char* c = (char*)malloc(strlen(a) + strlen(b));` You'll need to add 1 for the null character. And don't cast the return value of `malloc` in C — lost_in_the_source, Dec 29 '19 at 21:22
Does this answer your question? [How to find the 'sizeof' (a pointer pointing to an array)?](https://stackoverflow.com/questions/492384/how-to-find-the-sizeof-a-pointer-pointing-to-an-array) — dandan78, Dec 29 '19 at 21:38
@dandan78 I used strlen.. but still.. there is a problem as described — Tal Rofe, Dec 29 '19 at 21:42
Please don't edit the code in your question to eliminate problems. This makes it very difficult for people who come along later and read the question and comments to understand what's actually going on. I've rolled back to the last version of the question which contained `sizeof`. Thanks. — Bob Jarvis - Слава Україні, Dec 29 '19 at 21:59
Tal Rofe, given "sort by the ASCII value", what should happen when the values are outside the ASCII 0-127 range? — chux - Reinstate Monica, Dec 29 '19 at 22:51

score 1 · Answer 1 · answered Dec 29 '19 at 21:15

1

When working with strings in C, you will want to be using strlen() to see how long they are, not sizeof (which merely tells you what the size of a pointer is).

Also note that sizeof(char) is 1 by definition, so there's no need to say "* sizeof(char)" in your malloc

answered Dec 29 '19 at 21:15

David Gelhar

27,873
3
67
84

`sizeof` tells you the size of object or type, depending on its operand. – machine_1 Dec 29 '19 at 21:18

score 1 · Answer 2 · answered Dec 29 '19 at 21:19

1

sizeof(a) will return the size of a pointer in this case which will be 8 bytes if you compile for 64 architecture. you have to either pass the size of each string or loop the string characters until you reach the '\0' if the string is null-terminated.

answered Dec 29 '19 at 21:19

WaleedYaser

605
5
9

1

A _string_ is null-terminated _by definition_. – Lxer Lx Dec 29 '19 at 21:44

Lxer Lx · Accepted Answer · 2019-12-29T22:51:23.267

The expression i < sizeof(*c) controling the for loop is the main culprit. The corrected version of your program could be: (I edited the code a bit)

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

char* PairSortedArrays(const char a[], const char b[])
{
    size_t i;
    const size_t total_len = strlen(a)+strlen(b);
    char *c = malloc(total_len + 1);
    size_t aPos = 0, bPos = 0;

    for (i = 0; i < total_len; i++) {
        if (a[aPos] == '\0') {
            strcpy(c + i, b + bPos);
            break;
        }
        if (b[bPos] == '\0') {
            strcpy(c + i, a + aPos);
            break;
        }
        c[i] = a[aPos] < b[bPos] ? a[aPos++] : b[bPos++];
    }

    return c;
}

int main()
{
    printf("%s\n", PairSortedArrays("acdty", "berz"));
    printf("%s\n", PairSortedArrays("az", "ks"));
    return 0;
}

The return value of malloc must be checked against NULL in a real program. Also there is a memory leak (easy to fix).

Doesn't work with `PairSortedArrays("az", "ks")`. It returns `aks` instead of `aksz` — Tal Rofe, Dec 29 '19 at 22:15
@chux-ReinstateMonica Copied from the original code. Fixed now. I wouldn't myself use indexes; I would use just pointers `a` and `b`, but I didn't want to edit the original code much. — Lxer Lx, Dec 29 '19 at 22:52

Bob Jarvis - Слава Україні · Answer 4 · 2019-12-29T22:00:20.377

0

You should consider using qsort:

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

int compare_chars(const void *p1, const void *p2)
  {
  return *(const char *)p1 - *(const char *)p2;
  }

char *PairSortedArrays(char *a, char *b)
  {
  char *c = malloc(strlen(a)+strlen(b)+1);

  strcpy(c, a);
  strcat(c, b);

  qsort(c, strlen(c), sizeof(char), compare_chars);

  return c;
  }

int main()
  {
  printf("%s", PairSortedArrays("acdty", "berz"));
  return 0;
  }

edited Dec 29 '19 at 22:00

answered Dec 29 '19 at 21:54

Bob Jarvis - Слава Україні

48,992
9
77
110

True, but that increases the run-time complexity from O(n) to O(n log n). – Lxer Lx Dec 29 '19 at 23:06
As Grandma Roseannadanna once said, "It's always something!" :-) – Bob Jarvis - Слава Україні Dec 30 '19 at 00:40

Create function which sorts 2 given sorted strings

4 Answers4