sorting by length with stability in c

Question

I am working on a coding problem where I have to sort an array of words(pointers to strings) by the length of the word. I have an idea of the code that uses some index manipulation, but would like some help with checking the logic to see if I have this right. Here's the code I have so far.

void len_sort(char** words, int num_words)
{
    int index=0;
    int isSorted=0;
    int string1_len;
    int string2_len;
    while(isSorted==0)
    {
        for(index=0;index<num_words;index++)
        {
            printf("%s\n", words[index]);
            string1_len=strlen(words[index]);
            if((index+1)==num_words)
                string2_len=strlen(words[index]);
            else
                string2_len=strlen(words[index+1]);

            if(string1_len<string2_len)
            {
                swap(words[index], words[index+1]);
            }
        }

        isSorted=1;

        for(index=0;index<num_words;index++)
        {
            string1_len=strlen(words[index]);
            if(index+1==num_words)
                string2_len=strlen(words[index]);
            else
                 string2_len=strlen(words[index+1]);
            if(string1_len>string2_len)
            {
                isSorted=0;
            }
        }

    }


}
void swap(char* word1, char* word2)
{

    char* temp;
    word1=word2;
    word2=temp;

}

I don't need to sort alphabetically, and I need to maintain the order of the words as they are in the array. for example: if I have something like

car
x
horse
a

my output should look like:

x
a
car
horse

keeping the fact that x is before a in the array true. Is there a better way to work with this sort for more efficiency??

Do you need to reorder the actual memory, or can you work with pointers? — Alexandre Cassagne, Nov 23 '15 at 02:15
This code won't be correct because `swap()` does virtually nothing. — MikeCAT, Nov 23 '15 at 02:16
Oh should I pass in the array and swap the values of the array by referencing to them while I'm doing the swapping? — JustaRedShirt, Nov 23 '15 at 02:22
I'm not picky about time compexity atm. Maybe later I'll try to redesign for O(N) . I can work with pointers, the array that is holding the words is a pointer array (char**) or, an array of pointers that point to strings?I think that's how I'm supposed to say that — JustaRedShirt, Nov 23 '15 at 02:24
For the swap function, you should make use of strcpy or memcpy to transfer the first word into a temporary buffer then transfer the second word into the first word then make the new second word the contents of the temporary buffer. You can define such buffer as a `char[]` type and you may want to pass in the maximum word length into the swap function so the correct amount of memory can be allocated. — Mike -- No longer here, Nov 23 '15 at 02:27
Try to separate _how_ to sort (ascending, stable) from _what_ (`char const*` by length of string pointed to). `better […] sort for more efficiency` depends on input: try to characterise that, find out which sort implementations your run time environment offers, and give "simple" a try. You can invest more effort _if_ and _when_ the sort turns out to be a performance bottleneck. — greybeard, Nov 23 '15 at 07:21

score 1 · Answer 1 · answered Nov 23 '15 at 03:13

The swap function is not doing anything meaningful. If you want to swap two pointer, It should be like this:

void swap(char **word1, char **word2)
{
    char *temp;

    temp = *word1;
    *word1 = *word2;
    *word2 = temp;

}

Now, to sort with stability, We can only swap if the previous one is lengthy then the next. After every swap, The array will be one step more sorted. And we start from the beginning

void len_sort(char** words, int num_words)
{
    int i = 0; //start from the beginning.
    while(i < num_words-1) //till the last pair.
    {
        if(strlen(words[i]) > strlen(words[i+1])){//if a mismatch occur
            swap(&words[i], &words[i+1]);//fix it
            i = -1;//and start from the beginning 
        }
        i++;//so far sorted, try next pair
    }
}

Test:

int main()
{
    char d[][30] = {"car", "x", "horse", "a"};
    char *s[4];
    int i;

    //our function sort through pointer
    for(i=0; i<4; i++)
        s[i] = d[i];

    len_sort(s, 4);
    for(i=0; i<4; i++)
        printf("%s ", s[i]);
    puts("");

    return 0;
}

OUTPUT:

x a car horse

ibrohimislam · Answer 2 · 2015-11-23T03:10:09.603

I have a suggestion. Why don't you just create a pair of integer, first one for your length, and second one for your index of string. And then sort them.

Here is my code:

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

typedef struct {
  int first;
  int second;
} pair;

int cmp(pair a, pair b){
  return (a.first > b.first) || ((a.first == b.first) && (a.second > b.second));
}

// you can use your favorite sort algorithm
// Since in some condition, quick_sort runs in O(n^2)
void quick_sort (pair *a, int n) {
    int i, j;
    pair p, t;
    if (n < 2)
        return;
    p = a[n / 2];
    for (i = 0, j = n - 1;; i++, j--) {
        while (cmp(a[i],p))
            i++;
        while (cmp(p,a[j]))
            j--;
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    quick_sort(a, i);
    quick_sort(a + i, n - i);
}

char** len_sort(char** words, int num_words){
  pair my_pairs[num_words];

  // iterate in O(n)
  for (int i = 0; i < num_words; ++i) {
    my_pairs[i].first = strlen(words[i]);
    my_pairs[i].second = i;
  }

  // sort in O(nlogn)
  quick_sort(my_pairs, num_words);

  // iterate through sorted and create ne wlist of words in O(n)
  char** new_word_list = (char**) malloc(num_words*sizeof(char*));
  for (int i = 0; i < num_words; ++i)
    new_word_list[i] = words[my_pairs[i].second];

  return new_word_list;
}

IIRC, quicksort is _not_ stable, as in: http://stackoverflow.com/questions/1517793/stability-in-sorting-algorithms You could do it with a mergesort. Or, I am just being thrown off by your calling it "quick_sort"? — Craig Estey, Nov 23 '15 at 03:03
Yes, you can use any kind of sort algorithm, I just want to emphasize the logic to solve them. Just replace it with merge sort, or any kind of sort. — ibrohimislam, Nov 23 '15 at 03:07

score 0 · Answer 3 · answered Nov 23 '15 at 03:00

0

You can use sort by combined synthetic key, for example:

uint32_t key = (strlen(s) << 16) | line_no;

answered Nov 23 '15 at 03:00

olegarch

3,670
1
20
19

sorting by length with stability in c

3 Answers3