C++

Forum

 
to make a qsort() like function with quicksort example, sorting not ordered

ota2 (2)
Hi. i have trying to make qsort() like function from quicksort codes in http://www.algolist.net/Algorithms/Sorting/Quicksort
. From code of that site it works.

I want to use a compare function as parameter for use on strings and using void pointer on array to run also on structs. I give an array of elements between 0 and arrayLength(let's say 20) which randomly generated to this function. Comparing same elements with results of function qsort() but not taking same results with that(std::qsort()).

myqsort.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <iostream>
#include <cstdlib>

// original
void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */
  while (i <= j) {
    while (arr[i] < pivot)
      i++;
    while (arr[j] > pivot)
      j--;
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  };

  /* recursion */
  if (left < j)
    quickSort(arr, left, j);
  if (i < right)
    quickSort(arr, i, right);
}


int qsortCompare(const void *param1, const void *param2) {
  int number1 = *(int *) param1;
  int number2 = *(int *) param2;
  return number1 - number2;
}

// Forward Declaration
static void myqsortpart(void *array, size_t size, int left, int right,
    int (*compar)(const void *param1, const void *param2));

void myqsort(void *array, size_t nMembers, size_t size,
    int (*compar)(const void *param1, const void *param2))
{
  int left = 0;
  int right = nMembers - 1;
  myqsortpart(array, size, left, right, compar);
}

static void myqsortpart(void *array, size_t size, int left, int right,
    int (*compar)(const void *param1, const void *param2))
{
  int i = left, j = right;
  int pivot = (right + left) / 2;
  void *pivotptr = (void *) ((char *) array + pivot * size);

  /* partition */
  while (i <= j)
  {
    while ((*compar)((void *) ((char *) array + i * size), pivotptr) < 0)
      i++;
    while ((*compar)((void *) ((char *) array + j * size), pivotptr) > 0)
      j--;
    if (i <= j)
    {
      // swap operation
      char *ptr1 = NULL, *ptr2 = NULL;
      ptr1 = (char *) array + i * size;
      ptr2 = (char *) array + j * size;
      size_t size2;
      size2 = size;
      do
      {
        char tmp = *ptr1;
        *ptr1 = *ptr2;
        *ptr2 = tmp;
        ptr2++;
        ptr1++;
        --size2;
      }
      while (size2 > 0);
      i++;
      j--;
    }
  }

  if (left < j)
    myqsortpart(array, size, left, j, compar);
  if (i < right)
    myqsortpart(array, size, i, right, compar);
}
void printArray(int *array, int nElems)
{
  for (int i = 0; i < nElems; i++)
    std::cout << array[i] << ' ';
  std::cout << std::endl;
}
int main(void)
{
  int array[] = { 18, 20, 7, 3, 9, 14, 4, 18, 11, 5, 16, 15, 14, 18, 18, 7, 20, 10, 4, 18 };
  int arraySize = sizeof(array) / sizeof(array[0]);
  int *arrayMyqsort = new int[arraySize];
  int *arrayQsort = new int[arraySize];
  int *arrayQuicksort = new int[arraySize];
  for (int i = 0; i < arraySize; i++)
  {
    arrayMyqsort[i] = array[i];
    arrayQsort[i] = array[i];
    arrayQuicksort[i] = array[i];
  }
  std::qsort(arrayQsort, arraySize, sizeof(array[0]), qsortCompare);
  quickSort(arrayQuicksort, 0, arraySize - 1);
  myqsort(arrayMyqsort, arraySize, sizeof(array[0]), qsortCompare);
  std::cout << "array : " << std::endl;
  printArray(array, arraySize);
  std::cout << "qsort() : " << std::endl;
  printArray(arrayQsort, arraySize);
  std::cout << "quicksort() : " << std::endl;
  printArray(arrayQuicksort, arraySize);
  std::cout << "myqsort() : " << std::endl;
  printArray(arrayMyqsort, arraySize);
  delete[] arrayMyqsort;
  delete[] arrayQsort;
  delete[] arrayQuicksort;
}


array :
18 20 7 3 9 14 4 18 11 5 16 15 14 18 18 7 20 10 4 18
qsort() :
3 4 4 5 7 7 9 10 11 14 14 15 16 18 18 18 18 18 20 20
quicksort() :
3 4 4 5 7 7 9 10 11 14 14 15 16 18 18 18 18 18 20 20
myqsort() :
3 4 4 5 7 9 11 14 18 7 10 14 15 16 18 18 18 18 20 20


for another example: 2, 20, 18, 11, 18, 9, 20, 14, 1, 7, 17, 19, 2, 6, 13, 5, 16, 8, 5, 14

I'm using g++, eclipse IDE with
CXXFLAGS = "-c -fmessage-length=0 -rdynamic -g -O3"
LINKER="-rdynamic"

I also tried Optimization -O0 -O2. All the same
With some numbers it works nicely. These should always get same results, because myqsort() and quickSort() using same algorithm except one that myqsort() using pointer arithmetic.
Last edited on
salem c (3685)
Add a few cout statements to get an overview of where it might be going wrong.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
#include <iostream>
#include <cstdlib>

// original
void quickSort(int arr[], int left, int right) {
  std::cout << ">quicksort(arr,"<<left<<","<<right<<");\n";
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */
  while (i <= j) {
    while (arr[i] < pivot)
      i++;
    while (arr[j] > pivot)
      j--;
    std::cout << "+quicksort(i="<<i<<",j="<<j<<"\n";
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  };

  /* recursion */
  if (left < j)
    quickSort(arr, left, j);
  if (i < right)
    quickSort(arr, i, right);
  std::cout << "<quicksort(arr,"<<left<<","<<right<<");\n";
}

int qsortCompare(const void *param1, const void *param2) {
  int number1 = *(int *) param1;
  int number2 = *(int *) param2;
  return number1 - number2;
}

// Forward Declaration
static void myqsortpart(void *array, size_t size, int left, int right,
    int (*compar)(const void *param1, const void *param2));

void myqsort(void *array, size_t nMembers, size_t size,
    int (*compar)(const void *param1, const void *param2))
{
  int left = 0;
  int right = nMembers - 1;
  myqsortpart(array, size, left, right, compar);
}

static void myqsortpart(void *array, size_t size, int left, int right,
    int (*compar)(const void *param1, const void *param2))
{
  std::cout << ">myqsortpart(arr,"<<left<<","<<right<<");\n";
  int i = left, j = right;
  int pivot = (right + left) / 2;
  void *pivotptr = (void *) ((char *) array + pivot * size);

  /* partition */
  while (i <= j)
  {
    while ((*compar)((void *) ((char *) array + i * size), pivotptr) < 0)
      i++;
    while ((*compar)((void *) ((char *) array + j * size), pivotptr) > 0)
      j--;
    std::cout << "+myqsortpart(i="<<i<<",j="<<j<<"\n";
    if (i <= j)
    {
      // swap operation
      char *ptr1 = NULL, *ptr2 = NULL;
      ptr1 = (char *) array + i * size;
      ptr2 = (char *) array + j * size;
      size_t size2;
      size2 = size;
      do
      {
        char tmp = *ptr1;
        *ptr1 = *ptr2;
        *ptr2 = tmp;
        ptr2++;
        ptr1++;
        --size2;
      }
      while (size2 > 0);
      i++;
      j--;
    }
  }

  if (left < j)
    myqsortpart(array, size, left, j, compar);
  if (i < right)
    myqsortpart(array, size, i, right, compar);
  std::cout << ">myqsortpart(arr,"<<left<<","<<right<<");\n";
}
void printArray(int *array, int nElems)
{
  for (int i = 0; i < nElems; i++)
    std::cout << array[i] << ' ';
  std::cout << std::endl;
}
int main(void)
{
  int array[] = { 18, 20, 7, 3, 9, 14, 4, 18, 11, 5, 16, 15, 14, 18, 18, 7, 20, 10, 4, 18 };
  int arraySize = sizeof(array) / sizeof(array[0]);
  int *arrayMyqsort = new int[arraySize];
  int *arrayQsort = new int[arraySize];
  int *arrayQuicksort = new int[arraySize];
  for (int i = 0; i < arraySize; i++)
  {
    arrayMyqsort[i] = array[i];
    arrayQsort[i] = array[i];
    arrayQuicksort[i] = array[i];
  }
  std::qsort(arrayQsort, arraySize, sizeof(array[0]), qsortCompare);
  quickSort(arrayQuicksort, 0, arraySize - 1);
  myqsort(arrayMyqsort, arraySize, sizeof(array[0]), qsortCompare);
  std::cout << "array : " << std::endl;
  printArray(array, arraySize);
  std::cout << "qsort() : " << std::endl;
  printArray(arrayQsort, arraySize);
  std::cout << "quicksort() : " << std::endl;
  printArray(arrayQuicksort, arraySize);
  std::cout << "myqsort() : " << std::endl;
  printArray(arrayMyqsort, arraySize);
  delete[] arrayMyqsort;
  delete[] arrayQsort;
  delete[] arrayQuicksort;
}



Up to the first recursive step, there is already a difference.

>quicksort(arr,0,19);
+quicksort(i=0,j=18
+quicksort(i=1,j=9
+quicksort(i=2,j=6
+quicksort(i=4,j=3
>quicksort(arr,0,3);
vs
>myqsortpart(arr,0,19);
+myqsortpart(i=0,j=18
+myqsortpart(i=1,j=9
+myqsortpart(i=9,j=8
>myqsortpart(arr,0,8);


Use a debugger to spot fine level flow differences.

It would be useful to put both functions into separate projects, so you could single-step both functions side-by-side one line at a time.

A debug 'int *debug = (int*)array;' in your myqsortpart function would greatly assist in debugging, while you know you're debugging ints.
ota2 (2)
It should be void *array, because of function should run also on structs for another uses.
salem c (3685)
> It should be void *array, because of function should run also on structs for another uses.
I know that.

But while you're debugging arrays of int, having an int pointer will make your life a lot easier when it comes to debugging.

Which do you prefer?
std::cout << debug[pivot] << std::endl;

or
std::cout << *(((int*)array)+pivot) << std::endl;

When you've made the algorithm work for ints, you just remove it.

Topic archived. No new replies allowed.