Использование быстрой сортировки для сортировки массивов символов

Question

Я хотел бы отсортировать массив символов. Однако каждый раз, когда я запускаю программу, он падает, когда он достигает функции QuickSort. Что может быть неправильным, что вызывает такой эффект? Я использую массив указателей, чтобы отсортировать массив.

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

void print(char** A, int n){ 
    int i = 0; 
    for (i = 0; i < n; i++){ 
     printf("%s\n", A[i]); 
    } 
} 

int Partition(char** A, int p, int r){ 
    char *temp = (char*)malloc(sizeof(char)*30); 
    char *x = (char*)malloc(sizeof(char)*30); 
    x = A[r]; 
    int i = p - 1; 
    int j = 0; 
    for(j = p; j<=r; j++){ 
     if(strcmp(A[j],x) <=0){ 
      i=i+1; 
      temp = A[i]; 
      A[i] = A[j]; 
      A[j] = temp; 
      } 
     } 
    if(i<r){ 
     return i; 
    }else{ 
     return i-1; 
    } 

    free(temp); 
    free(x); 

} 

void QuickSort(char** A, int p, int r){ 
    if(p<r){ 
     int q = Partition(A, p, r); 
     QuickSort(A, p, q); 
     QuickSort(A, q+1, r); 
    } 
} 


int main(){ 
    int i = 0; 

    char **A = (char**) malloc(12*sizeof(char*)); 

    for(i = 0; i < 12; i++){ 
     A[i] = (char*) malloc(sizeof(char)*30); 
    } 

    strcpy(A[0], "imarr"); 
    strcpy(A[1], "ikak"); 
    strcpy(A[2], "agh"); 
    strcpy(A[3], "ogss"); 
    strcpy(A[4], "alllll"); 
    strcpy(A[5], "ackm"); 
    strcpy(A[6], "plccc"); 
    strcpy(A[7], "strrr"); 
    strcpy(A[8], "raat"); 
    strcpy(A[9], "omhhh"); 
    strcpy(A[10], "rrors"); 
    strcpy(A[11], "basds"); 

    QuickSort(A, 0, 12); 

    print(A, 12); 

    free(A); 

    return 0; 
} 

Answer 1

Заменить

QuickSort(A, 0, 12); 

с

QuickSort(A, 0, 11); 

откомпилировать и запустить его, а затем думать об этом. Полагаю, вы будете достаточно умны, чтобы понять, почему 12 неверно, а 11 - в порядке.

Кстати, я думаю, что этот вопрос действительно должен идти к https://codereview.stackexchange.com/

EDITED: жаль, что я не заметил эту проблему на первый:

В Partition это три линии странно:

char *x = (char*)malloc(sizeof(char)*30); 
x = A[r]; 
...... 
free(x); 

Нет проблем (значит нет сбоев, в то время как на самом деле происходит утечка памяти, так как выделенное x не освобождается, а также A был ошибочно освобожден) с этим в этом случае, так как массив A также выделяется malloc.
Также, как вы используете temp как переменную, содержащую значение char* при обмене, нет необходимости выделять память. См отредактированный код:

int Partition(char** A, int p, int r){ 
    char *temp; 
    char *x = A[r]; 
    int i = p - 1; 
    int j = 0; 
    for(j = p; j<=r; j++){ 
     if(strcmp(A[j],x) <=0){ 
      i=i+1; 
      temp = A[i]; 
      A[i] = A[j]; 
      A[j] = temp; 
      } 
     } 
    if(i<r){ 
     return i; 
    }else{ 
     return i-1; 
    } 
} 

Answer 2

http://algs4.cs.princeton.edu/23quicksort/

void quick_sort (int *a, int n) { 
    if (n < 2) 
     return; 
    int p = a[n/2]; 
    int *l = a; 
    int *r = a + n - 1; 
    while (l <= r) { 
     if (*l < p) { 
      l++; 
     } 
     else if (*r > p) { 
      r--; 
     } 
     else { 
      int t = *l; 
      *l = *r; 
      *r = t; 
      l++; 
      r--; 
     } 
    } 
    quick_sort(a, r - a + 1); 
    quick_sort(l, a + n - l); 
} 

int main() { 
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; 
    int n = sizeof a/sizeof a[0]; 
    quick_sort(a, n); 
    return 0; 
}