C - Custom qsort not working

Question

I am trying to make a qsort type of function that has the same paramenters. I also wrote 3 functions to compare int, float and characters. For some reason it does not work in any case. I don't know whether this is a problem regarded my qsortx function or not, but I checked it several times and it should work perfectly fine. I am not sure what the problem is, or what I am doing wrong. I am currently learning the function pointers and I might not have got everything right related to it. Thanks in advance.

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

void qsortx(void*, int, int, int (*)(const void*, const void*));
int intcmp();
int floatcmp();
int charcmp();

int main()
{
    int i,n;
    char items[]={'c', 'a', 'b'};
    n = 3;
    for (i=0;i<n;++i) {
        printf("%c ", items[i]);
    }
    printf("\n");

    qsortx(items, n, sizeof(char), charcmp);

    for (i=0;i<n;++i) {
        printf("%c ", items[i]);
    }
    printf("\n");
    return 0;
}

void qsortx (void *tp, int length, int pace, int(*fp)(const void* a, const void* b)) {
    int switched,i,j;
    void *p;
    p=(void*)malloc(pace);
    switched = 1;
    while (1) {
        if (switched == 0) {
            return;
        }
        switched = 0;
        for (i=0; i<length-1;++i) {
            for (j=0;j<length-1;++j) {
                printf("%c %c", tp+i, tp+j);
                if (fp(tp+i, tp+j) > 0) {
                    memcpy(p, tp+i, pace);
                    memcpy(tp+i, tp+j, pace);
                    memcpy(tp+j, p, pace);
                    switched++;
                }
            }
        }

    }
}

int intcmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int floatcmp(const void* a, const void* b) {
    return *(float*)a - *(float*)b;
}

int charcmp(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

Answer 1

You have multiple problems related to pointer arithmetic and element sizes. You also have a logic error in your sort (which I guess you know is a unidirectional shaker sort). Here's a version of the qsortx() function that fixes these deficiencies:

void qsortx (void *tp, int length, int pace, int(*fp)(const void* a, const void* b)) {
    if (length > 1) {
        char *bound = ((char *) tp) + (length * pace);
        char *p = malloc(pace);
        char *item1p;

        for (item1p = tp; item1p < (bound - pace); item1p += pace) {
            char *item2p;

            for (item2p = item1p + pace; item2p < bound; item2p += pace) {
                if (fp(item1p, item2p) > 0) {
                    memcpy(p, item1p, pace);
                    memcpy(item1p, item2p, pace);
                    memcpy(item2p, p, pace);
                }
            }
        }

        free(p);
    }
}

Note that:

1. All pointer arithmetic is performed on values of type char *.
2. The element size (pace) must be taken into account as you step through the input array, else you just scramble your data.
3. The innermost loop should start at the element after the one being considered in the next-outer loop.
4. switched = 1 is a better choice than switched ++ because it cannot overflow, and all you care about is zero vs. non-zero. (Update: but switched is no longer relevant.)
5. (Update) It is incorrect to exit early in the event that a pass through the item1p loop results in zero swaps. Just because one element is already in its correct place does not mean that all the subsequent elements are also in their correct places. I updated my code above to remove that behavior.
6. (Update) As chux observed, the temporary space reserved for swapping elements was not freed. I added an appropriate free(p).
7. (Update) I also made sorting conditional on the array length being greater than 1, which avoids undefined behavior associated with bound - pace in the event that the length is zero.

Answer 2

here is the pseudo code and implementation of the quicksort (qsort) algorithm, with some accessory code, as defined in the http://www.codingbot.net/2013/01/quick-sort-algorithm-and-c-code.html web page: Note that this algorithm is slightly different from qsort() in that there is a different parameter list and certain other details. However, the basic algorithm is the same.

function quicksort('array')
    if length('array') ≤ 1
        return 'array'  // an array of zero or one elements is already sorted
        select and remove a pivot value 'pivot' from 'array'
        create empty lists 'less' and 'greater'
        for each 'x' in 'array'
            if 'x' ≤ 'pivot' 
                then append 'x' to 'less'
            else 
                append 'x' to 'greater'
            endif
        end for
        return concatenate(quicksort('less'), 'pivot', quicksort('greater') );

notice that qsort is a partition sort, using recursion.

#include<stdio.h>
#include<conio.h>

void quick_sort(int arr[20],int,int);

int main()
{
   int arr[20],n,i;
   clrscr();
   printf("Enter the number of elements in the Array: ");
   if( 1 != scanf(" %d",&n) ) 
   {
       perror( "scanf for count of elements" );
       exit(1);
   }

   printf("\nEnter %d elements:\n\n",n);

   for(i=0 ; i<n ; i++)
   {
        printf(" Array[%d] = ",i);
        if( 1 != scanf(" %d",&arr[i]) )
        {
            perror( "scanf for element values" );
            exit(2);
        }

   }

   quick_sort(arr,0,n-1);
   printf("\nThe Sorted Array is:\n\n");

   for(i=0 ; i<n ; i++)
   {
        printf(" %4d",arr[i]);
   }
   getch();
}

void quick_sort(int arr[20],int low,int high)
{
    int pivot; // used in partitioning the array
    int j; // loop index
    int temp; // for swapping
    int i; // loop index

    if(low<high)
    {
        pivot = low; 
        i = low;
        j = high;

        while(i<j)
        {
            // find next item not in proper sequence
            while((arr[i] <= arr[pivot]) && (i<high))
            {
                i++;
            }

            // find next item not in proper sequence
            while(arr[j] > arr[pivot])
            {
                j--;
            }

            // following is where a callback function would be invoked
            if(i<j)
            { 
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }

        temp=arr[pivot];
        arr[pivot] = arr[j];
        arr[j]=temp;

        // following is where recursion is used to perform sort on sub partitions
        quick_sort(arr,low,j-1);
        quick_sort(arr,j+1,high);
   }
}

Answer 3

this is a much better algorithm for your purposes. however, it only handles integers, so you would need to add the comparison function as a 4th parameter to quicksort() and modify the code to use your comparison function

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

void swap(int *x,int *y);
int choose_pivot(int i,int j );
void quicksort(int list[],int m,int n);
void display(int list[],const int n);

int main()
{
    const int SIZE = 10;
    int list[SIZE];

    int i = 0;

    /* generates random numbers and fill the list */
    for(i = 0; i < SIZE; i++ )
    {
        list[i] = rand();
    }

    printf("The list before sorting is:\n");
    display(list,SIZE);

    /* sort the list using quicksort algorithm */
    quicksort(list,0,SIZE-1);

    printf("The list after sorting:\n");
    display(list,SIZE);
}


void swap(int *x,int *y)
{
    // for integer swaps, 3 exclusive OR operations would be much faster
    // and not require a temp variable
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}


int choose_pivot(int i,int j )
{
    return((i+j) /2);
}


void quicksort(int list[],int m,int n)
{
    int key,i,j,k;

    if( m < n)
    {
        k = choose_pivot(m,n);
        swap(&list[m],&list[k]);
        key = list[m];
        i = m+1;
        j = n;
        while(i <= j)
        {
            while((i <= n) && (list[i] <= key))
            {
                 i++;
            }

            while((j >= m) && (list[j] > key))
            {
                j--;
            }

            if( i < j)
            {
                swap(&list[i],&list[j]);
            }
        }

        /* swap two elements */
        swap(&list[m],&list[j]);

        /* recursively sort the lesser list */
        quicksort(list,m,j-1);
        quicksort(list,j+1,n);
    }
}


void display(int list[],const int n)
{
    int i;

    for(i=0; i<n; i++)
    {
        printf("%d\t",list[i]);
    }
}