CODEWITHSUNDEEP
calgorithmsortingquicksort
D3migod
D3migod

Reputation: 319

Quicksort doesn't work for the last two numbers

The task was to write quicksort for unknown type of elements in array (using only C code), but my code doesn't work for the last two elements. FOr the following numbers output is '67 45 44 33 5 1 -3 0 -4 -100' I also tried to debug but the only thing I understood is that the last numbers just do not compare. 

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
typedef int typeEl;

void swap(void* a, void* b, size_t sizeOfElem) {
    void* tmp = calloc(1,sizeOfElem);
    memcpy(tmp, a, sizeOfElem);
    memcpy(a, b, sizeOfElem);
    memcpy(b, tmp, sizeOfElem);
}

int compare(const void* a, const void* b)
{

    return (*(typeEl*)a - *(typeEl*)b);
}

void quickSortR(void* a, long N, size_t sizeOfElem, int (*comp)(const void* c, const void* d)) 
{

  long i = 0, j = N;        


  void* p = (void *) ((char *)a + (N>>1)*sizeOfElem);       

  do {
    while ( comp((void *) ((char *)a + i*sizeOfElem), p)>0) i++;
    while ( comp((void *) ((char *)a + j*sizeOfElem), p)<0) j--;

    if (i <= j) {
      swap((void *) ((char *)a + i*sizeOfElem), (void *) ((char *)a + j*sizeOfElem), sizeOfElem);
      i++; j--;
    }
  } while ( i<=j );


  if ( j > 0 ) quickSortR((void *)a, j, sizeOfElem, comp);
  if ( N > i ) quickSortR((void *) ((char *)a + i*sizeOfElem), N-i,sizeOfElem, comp);
}
int main() {
    int n;
   int m[10] = {1,-3,5,-100,45,33,44,67,-4, 0};

   quickSortR((void *)m, 10, sizeof(int),compare);              
    for (n=0; n<10; n++)
        printf ("%d ",m[n]);
   return 0;
}

Anyone can advise? Thx for the help!

Upvotes: 4

Views: 157

Answers (1)

starrify
starrify

Reputation: 14741

There're 3 problems in your code:

  1. The initialization of j = N shall be j = N - 1. Reason: later you use the element at position j to start comparing, and index of an array in C is [0,N-1]

  2. The pivot p shall not be a pointer but a value. This affects the result when the value at position p is swapped but you still regard it as the pivot. Your code seems designed for comparing with pointers, however I could present a quick & ugly(also dangerous!) fix:
    replace your code:

    void* p = (void *) ((char *)a + (N>>1)*sizeOfElem);

    with these:

    void* p = (void *) ((char *)a + (N>>1)*sizeOfElem);
void *px = malloc(sizeOfElem);
memcpy(px, p, sizeOfElem);
p = px;

  3. This line of your code:

    if ( j > 0) quickSortR((void *)a, j, sizeOfElem, comp);

    shall be:

    if ( j > 0) quickSortR((void *)a, j + 1, sizeOfElem, comp);

    since at the second parameter of quickSortR you're passing the length of array.

Fix all these 3 problems and your code shall give correct results.

EDITED:
When I say 3 problems above I mean problems when implementing the algorithm. Other than that there is memory leak within your function compare (simply free(tmp) to solve it). Also the test if ( N > i ) could be if ( N > i + 1 ).
:)

Upvotes: 4

Related Questions