Sorting strings with insertion sort in C - segmentation fault

Question

I'm trying to adapt my number sorting insertion sort code to sort an input file of strings instead e.g:

thickness
combed
revocable
escorted

However I get a segmentation fault(core dumped) when trying to run the below:

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

#define STRING_LEN  80
#define ARRAY_LEN   10000

void insertion_sort(char **a, int n) {
    int i;
    int j;
    char *key;

    for (i = 1; i < n; i++) {
        key = a[i];
        j = i - 1;

        while (strcmp(key, a[j]) == -1 && j >= 0) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key; 
    }
}

void *emalloc(size_t s) {
    void *result = malloc(s);
    if (NULL == result) {
        fprintf(stderr, "Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    return result;
}

int main(void) {
    int j;
    int num_words = 0;
    char word[STRING_LEN];
    char *wordlist[ARRAY_LEN];

    while (num_words < ARRAY_LEN && 1 == scanf("%79s", word)) {
        wordlist[num_words] = emalloc((strlen(word) + 1) * sizeof wordlist[0][0]);
        strcpy(wordlist[num_words], word);
        num_words++;    
    }

    insertion_sort(wordlist, num_words);

    for (j = 0; j < num_words; j++) {
        printf("%s\n", wordlist[j]);
    }

    return EXIT_SUCCESS;
}

I've found by changing the while condition to > 0 instead of >= 0

while (strcmp(key, a[j]) == -1 && j > 0)

It sorts everything but the first string, as this is when j is 0 and the loop isn't entered, and the output is:

thickness
combed
escorted
revocable

I'm new to C and I gather this is related to accessing memory that hasn't been allocated, but I'm struggling to see where.

chqrlie · Accepted Answer · 2016-07-29 01:08:00Z

4

Your loop test is incorrect:

while(strcmp(key,a[j]) == -1 && j>=0){

You should check the index j before using it and you should not rely on strcmp() returning -1 for key less than a[j]. strcmp() is only specified as returning a negative value for this case.

while (j >= 0 && strcmp(key, a[j]) < 0) {

answered Jul 29, 2016 at 1:08

chqrlie

152k12 gold badges145 silver badges231 bronze badges

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

3 Comments

David C. Rankin Over a year ago

You are hitting on all 8-cylinders today!

chqrlie Over a year ago

@DavidC.Rankin: procrastinating on some more important work is such an incredibly effective motivation ;-)

chqrlie Over a year ago

@yhsdygdyusgdysgdsudsd: can you please accept this answer by clicking on the grey checkmark below the answer score?

Collectives™ on Stack Overflow

Sorting strings with insertion sort in C - segmentation fault

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related