Valgrind- uninitialized values message

Question

I've been getting some mysterious uninitialized values message from valgrind and it's been quite the mystery as of where the bad value originated from. Don't anyone know where is problem? Thanks a lot There is memmory error, which i have been getting:

==26075== Memcheck, a memory error detector
==26075== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==26075== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==26075== Command: ./main
==26075== 
==26075== Conditional jump or move depends on uninitialised value(s)
==26075==    at 0x4C2A020: strcmp (mc_replace_strmem.c:711)
==26075==    by 0x400CF6: stringcmp (main.c:121)
==26075==    by 0x4E64C69: msort_with_tmp (msort.c:84)
==26075==    by 0x4E6503B: qsort_r (msort.c:298)
==26075==    by 0x400930: main (main.c:42)
==26075== 
==26075== Conditional jump or move depends on uninitialised value(s)
==26075==    at 0x4C2A024: strcmp (mc_replace_strmem.c:711)
==26075==    by 0x400CF6: stringcmp (main.c:121)
==26075==    by 0x4E64C69: msort_with_tmp (msort.c:84)
==26075==    by 0x4E6503B: qsort_r (msort.c:298)
==26075==    by 0x400930: main (main.c:42)
==26075== 
==26075== 
==26075== HEAP SUMMARY:
==26075==     in use at exit: 0 bytes in 0 blocks
==26075==   total heap usage: 4 allocs, 4 frees, 31 bytes allocated
==26075== 
==26075== All heap blocks were freed -- no leaks are possible
==26075== 
==26075== For counts of detected and suppressed errors, rerun with: -v
==26075== Use --track-origins=yes to see where uninitialised values come from
==26075== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 4 from 4)

There is my code:

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

char *input;
int row = 0;


int stringcmp(const void *a, const void *b);

void permute(int n, int fix, char **arr);

int factorial(int n);

void swapSort(char array[], int left, int right);

void quick_sort(char *array, int left, int right);

void free2DArray(char **array, int row);

int main() {
    input = (char *) malloc(8 + 1 * sizeof(char));
    fgets(input, 9, stdin);
    int n = strlen(input);
    if (input[n - 1] == '\n') {
        n--;
        input[n] = '\0';
    }
    int f = factorial(n);
    printf("Length of string: %d\n", n);
    printf("Input string: \"%s\"\n", input);
    quick_sort(input, 0, n);
    printf("Sorted: \"%s\"\n", input);
    printf("Number of permutations: %d\n", f);
    char **arrOfPermutations = (char **) malloc(factorial(n) * sizeof(char *));
    for (int i = 0; i < factorial(n); i++) {
        arrOfPermutations[i] = (char *) malloc((n + 1) * sizeof(char));
    }

    permute(n, n, arrOfPermutations);
    qsort(arrOfPermutations, f, sizeof(char *), stringcmp);
    for (int i = 0; i < f; i++) {
        printf("\"");
        for (int j = 0; j < n; j++) {
            printf("%c", arrOfPermutations[i][j]);
        }
        printf("\"\n");
    }
    free2DArray(arrOfPermutations, f);
    free(input);

    return 0;
}


void free2DArray(char **array, int row) {
    for (row -= 1; row >= 0; row--)
        free(array[row]);
    free(array);
}

void permute(int n, int fix, char **arr) {
    int i, j;
    char temp;
    if (n == 0) {
        for (j = fix - 1, i = 0; j >= 0; j--, i++) {
            arr[row][i] = input[j];
        }
        row++;
    }
    for (i = 0; i < n; i++) {
        temp = input[i];
        for (j = i + 1; j < n; j++) {
            input[j - 1] = input[j];
        }
        input[n - 1] = temp;

        permute(n - 1, fix, arr);

        for (j = n - 1; j > i; j--) {
            input[j] = input[j - 1];
        }
        input[i] = temp;
    }
}

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);

}


void quick_sort(char *array, int left, int right) {
    if (left < right) {
        int boundary = left;
        for (int i = left + 1; i < right; i++) {
            if (array[i] < array[left]) {
                swapSort(array, i, ++boundary);
            }
        }
        swapSort(array, left, boundary);
        quick_sort(array, left, boundary);
        quick_sort(array, boundary + 1, right);
    }

}

void swapSort(char array[], int left, int right) {
    char tmp = array[right];
    array[right] = array[left];

    array[left] = tmp;
}


int stringcmp(const void *a, const void *b) {
    const char **ia = (const char **) a;
    const char **ib = (const char **) b;
    return strcmp(*ia, *ib);
}

Answer 1

Apart from few other smaller problems You are correctly reverse-copying a string however without appending zero-byte at the end.

if (n == 0) {
    for (j = fix - 1, i = 0; j >= 0; j--, i++) { <<-- The problem is in this line
        arr[row][i] = input[j];
    }
    row++;
}

You can't reverse- copy end-of-line marker as it should remain in the end, so you have to add it afterwards:

if (n == 0) {
    for (j = fix - 1, i = 0; j >= 0; j--, i++) { 
        arr[row][i] = input[j];
    }
    arr[row][fix]=0; <<-- the fix
    row++;
}