Sorting string lexicographically in c

Question

I want to sort words of a string in lexicographical order.

For Example:

I have a string: I am Apple

Output should be: am Apple I

Problem (output):

enter the string

hello shamsh

the sorted array:

hello

It's not sorting the string and whole string is not being shown in the output, can anyone help me out here. Thanks!

Program code:

#include<stdio.h>
#include<string.h>
void main()
{
    char a[25][25],t[25];
    char s[200];
    char * pch;
    int count = 0;
    int i,j ,n;
    printf("enter the string\n");
    gets(s);
    pch = strtok (s," ,.-");
    for (i = 0;s[i] != '\0';i++)
    {
        if (s[i] == ' ')
            count++;    
    }
    count=count+1;
    i=0;
    while(pch != NULL)
    {
        strcpy(a[i],pch);
        pch = strtok (NULL, " ,.-");
        i++;
    }

    for(i=0;i<count-1;i++)
    {
        for(j=i+1;j<count;j++)
        {
            if(strcmp(a[i],a[j])>0)
            {
                strcpy(t,a[i]);
                strcpy(a[i],a[j]);
                strcpy(a[j],t);
            }
        }
    }
printf("the sorted array:\n");
for(i=0;i<count;i++)
printf("%s\n",a[i]);
}

In your [previous question](http://stackoverflow.com/questions/39355208/sort-the-words-of-a-string-a-lexicographical-order-dictionary-order-in-c?noredirect=1#comment66042921_39355208) you were advised that `gets` is obsolete, and that hard-coded sizes are difficult to maintain, and about safeguards with string lengths. — Weather Vane, Sep 06 '16 at 19:49
Your loop to count words is not right. First, it counts only spaces while you're using other delimiter characters for `strtok`. Second, you do that loop AFTER the first call to `strtok`, which terminates the string after the first word. So you only ever get `count` set to 1. Why not just count words in the `strtok` loop? — Fred Larson, Sep 06 '16 at 19:52
You should not be working with `char s[200];` once you have passed it to `strtok`. From that point, you work with the token pointer `pch`, because `strtok` breaks the original string. — Weather Vane, Sep 06 '16 at 19:53
@FredLarson Thanks a ton, `strtok` breaks the string at the first instance only, so was there wasthe problem. :) — Tabassum Ahmed, Sep 06 '16 at 20:01
@TabassumAhmed `strtok` inserts `nul` terminators all the way along the string it was given, at the next match with the delimitor set. The pointer returned, is to the start of the "token" which it has `nul`-terminated, so you can process it as a string itself. — Weather Vane, Sep 06 '16 at 20:04
Honestly, if your strings are broken up in that line anyway, there is no need for a `char a[25][25]`. Just store the pointers returned from `strtok` into a `char *a[25]` array of pointers. It also makes swapping array elements (which are simple pointers into the line buffer) *trivial*, as no `strcpy` is required. — WhozCraig, Sep 06 '16 at 20:08
NB: See [Why `gets()` is too dangerous to be used — ever!](http://stackoverflow.com/questions/1694036/why-is-the-gets-function-dangerous-why-should-it-not-be-used) — Jonathan Leffler, Sep 06 '16 at 21:29
@TabassumAhmed, I'm afraid that `strtok(3)` breaks the string at all instances, and assuming what is the string contents after it has passed scanning on the original string is undefined behaviour (implementation dependant). Don't assume anything about the string contents after `strtok(3)` has passed over it. — Luis Colorado, Sep 08 '16 at 06:04

score 0 · Answer 1 · answered Sep 06 '16 at 21:05

0

Use qsort() for this sort of thing.

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

#define BUF_SIZE 0x100

int strcmp_wrapper(const void *a, const void *b) {
        return strcmp(*(const char **)a, *(const char **)b);
}

int main () {
        char buffer[BUF_SIZE], *tokens[BUF_SIZE / 2 + 1];
        int i = 0, j = 0;

        printf("Enter a string: ");
        fgets(buffer, BUF_SIZE, stdin);

        tokens[0] = strtok(buffer, " ,.-\n");
        while ((tokens[++i] = strtok(NULL, " ,.-\n")));

        qsort(tokens, i, sizeof(tokens[0]), strcmp_wrapper);

        while (j < i)
                printf("%s\n", tokens[j++]);

        return 0;
}

answered Sep 06 '16 at 21:05

Ray Hamel

1,289
6
16

Why does `strcmp_wrapper()`'s `strcmp()` call use `*(const char**)a` instead of `(const char*)a`? (The second form seems to yield incorrect results, so the first form *is* necessary; I'm just having trouble getting why.) – 6equj5 Feb 13 '22 at 20:07
1

Ah! It's because the `void*` in `strcmp_wrapper()` IS, in fact, a `char**`, not a `char*`. This is because `qsort()` is dealing with `tokens`, an array of strings, and it passes *pointers to those strings* (i.e., `char**`s) to `strcmp_wrapper()`. And, since we want `const char*`s to pass to `strcmp()`, we cast-and-dereference the `void*`s via `*(const char **)`. For another explanation of this, see [this answer](https://stackoverflow.com/a/20061656/9959012). – 6equj5 Feb 13 '22 at 22:14

score 0 · Accepted Answer · answered Sep 06 '16 at 21:20

If you try to print your string after you pch = strtok (s," ,.-"), you'll notice that your string is broken up. That's because strtok() is destructive and breaks up the string into tokens so you need to count the number of white spaces before calling strtok():

printf("enter the string\n");
    gets(s);

    for (i = 0;s[i] != '\0';i++)
    {
        if (s[i] == ' ')
            count++;    
    }
    count=count+1;
    i=0;
    pch = strtok (s," ,.-");

Also like Weather Vane said, don't use gets(), use fgets() instead oand remove the '\n' from end of the string afterwards. Also you can use realloc() to assign more memory to a dynamic array instead of using a static array since you wouldn't know the number of words in a string beforehand.

#include <stdlib.h>
#include<stdio.h>
#include<string.h>
void main()
{
    char** a = NULL;
    char t[25];
    char s[512];
    char * pch;
    int count = 0;
    int i,j ,n;

    printf("enter the string\n");
  if(fgets(s,512, stdin)==NULL)
  {
    printf("failed to read string\n");
    exit(-1);
  }
  /*remove '\n' from end of the string*/
  char *pos;
  if ((pos=strchr(s, '\n')) != NULL)
    *pos = '\0';

  pch = strtok(s, " ,.-");
  while(pch)
  {
    a = realloc(a, sizeof(char*)*++count);
    if(a==NULL)
    { 
      perror("failed to allocate memory\n");
      exit(-1);
    }

    a[count-1] = pch;
    pch = strtok(NULL, " ,.-");
  }
   for(i=0;i<count;i++)
    printf("%d: %s\n", i, a[i]);
    ///...compare array

score 0 · Answer 3 · answered Sep 08 '16 at 06:01

below is a compact working way of doing what you want. It prints the words of each line, sorted and separated by one space, without repeating words being repeated (if you want them repeated for sure you will be able to touch the program to make it work)

$ cat pru799.c

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

#define DELIMITERS  " \t\n,.-()&%$\"\'[]{}+-*/;:@#|!\\<>=?"
#define LINE_SIZE   1024
#define MAX_WORDS   256

int compare(const char **p, const char **q)
{
    return strcmp(*p, *q);
}

int main()
{
    char line[LINE_SIZE];
    char *words[MAX_WORDS];
    int n_words;

    while (fgets(line, sizeof line, stdin)) { /* while not eof */
        char *p;
        int i;

        /* first get the words */
        n_words = 0;
        for (p = strtok(line, DELIMITERS); p; p = strtok(NULL, DELIMITERS)) {
            if (strlen(p) == 0) continue; /* word is zero length */
            if (n_words >= MAX_WORDS) {
                fprintf(stderr, "MAX_WORDS(%d) exceeded\n", MAX_WORDS);
                exit(EXIT_FAILURE);
            }
            words[n_words++] = p;
        } /* for */

        /* now we have all the words in the array of strings words, sort it */
        qsort(words, n_words, sizeof words[0], (int(*)(const void *, const void *))&compare);

        /* now print the words */
        for (i = 0; i < n_words; i++) {
            if (i) { /* all but the first one */
                /* don't repeat words */
                if (!strcmp(words[i], words[i-1])) 
                    continue;
                printf(" "); /* print a space between words */
            }
            printf("%s", words[i]);
        }
        printf("\n");
    } /* while */
} /* main */

Sorting string lexicographically in c

3 Answers3