Using Quick Sort for sorting arrays of characters

Question

I would like to sort an array of characters. However every time I run the program it crashes when it reaches the QuickSort function. What may be wrong that causes such effect? I am using the array of pointers in order to sort the array.

#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;
}

Because I learn how to implement algorithms and using a pre-build function will not make the teacher give me a good mark. — MaranX
– MaranX, Commented Nov 17, 2013 at 20:47

Community · Accepted Answer · 2017-04-13 12:40:32Z

Replace

QuickSort(A, 0, 12);

with

QuickSort(A, 0, 11);

Compile and run it, then think about it. I suppose you shall be smart enough to figure it out yourself why 12 is incorrect while 11 is okay.

By the way I think this question really shall go to https://codereview.stackexchange.com/

EDITED: sorry I didn't noticed this problem at first:

In Partition this three lines are weird:

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

There is no problem (means no crash, while there is actually memory leakage since the allocated x doesn't get freed and also A was mistakenly freed) with it in this case since the array of A is also allocated by malloc.
Also as you use temp as a variable holding a value of char* while swapping, there is no need to allocated the memory. See the edited code:

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;
    }
}

AVIK DUTTA · Accepted Answer · 2014-11-03 07:05:37Z

0

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;
}

answered Nov 3, 2014 at 7:05

AVIK DUTTA

7387 silver badges23 bronze badges

Collectives™ on Stack Overflow

Using Quick Sort for sorting arrays of characters

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related