Quicksort

[Debaser]

Following the pseudocode from a book, I came up with the following
code. It runs fine but does not sort properly. The swapMB function was
added for convenience...perhaps I'm not swapping values properly(?).
Have a look please:

--------------

/* Quick Sort Algorithm Implementation */
/* Last element in (sub)array as pivot */


#include <stdio.h>

int partitionMB(int *A, int p, int r);
void qsortMB(int *A, int p, int r);
void swapMB(int* A, int x, int y);

/* Swaps two elements in an INT array */
void swapMB(int* A, int x, int y)
{
int z;

z = A[x];
A[x] = A[y];
A[y] = z;
}

/* Recursive quicksort */
void qsortMB(int *A, int p, int r)
{
int q;

if (p < r) {
q = partitionMB(A, p, r);
qsortMB(A, p, q-1);
qsortMB(A, q+1, r);
}
}

/* Partions an INT array of size A[p..r] into two sub arrays */
int partitionMB(int *A, int p, int r)
{
int x, /* Pivot */
i, j; /* Array access */

/* Pick pivot as last element in (sub)array */
x = A[r-1];

/* Put i at one before first element */
i = p-1;

/* Move elements <= pivot to current i+1 position*/
for (j = p; j < r-2; j++) {
if (A[j] <= x) {
swapMB(A, ++i, j);
}
}

/* Put pivot after values <= itself */
swapMB(A, ++i, r-1);


return i;
}


/* Sample main() */
int main(void)
{

int A[] = {5,2,3,7,8,4,10,31,1,43};
int x;

qsortMB(A, 0, sizeof(A)/sizeof(int));

for (x = 0; x < sizeof(A)/sizeof(int); x++) {
printf("%d ", A[x]);
}

printf("\n");

return 0;
}

 

[pete]

Following the pseudocode from a book, I came up with the following
code. It runs fine but does not sort properly. The swapMB function was
added for convenience...perhaps I'm not swapping values properly(?).
Have a look please:

--------------

/* Quick Sort Algorithm Implementation */
/* Last element in (sub)array as pivot */

#include <stdio.h>

int partitionMB(int *A, int p, int r);
void qsortMB(int *A, int p, int r);
void swapMB(int* A, int x, int y);

/* Swaps two elements in an INT array */
void swapMB(int* A, int x, int y)
{
int z;

z = A[x];
A[x] = A[y];
A[y] = z;
}

/* Recursive quicksort */
void qsortMB(int *A, int p, int r)
{
int q;

if (p < r) {
q = partitionMB(A, p, r);
qsortMB(A, p, q-1);
qsortMB(A, q+1, r);
}
}

/* Partions an INT array of size A[p..r] into two sub arrays */
int partitionMB(int *A, int p, int r)
{
int x, /* Pivot */
i, j; /* Array access */

/* Pick pivot as last element in (sub)array */
x = A[r-1];

/* Put i at one before first element */
i = p-1;

/* Move elements <= pivot to current i+1 position*/
for (j = p; j < r-2; j++) {
if (A[j] <= x) {
swapMB(A, ++i, j);
}
}

/* Put pivot after values <= itself */
swapMB(A, ++i, r-1);


return i;
}

/* Sample main() */
int main(void)
{

int A[] = {5,2,3,7,8,4,10,31,1,43};
int x;

qsortMB(A, 0, sizeof(A)/sizeof(int));

for (x = 0; x < sizeof(A)/sizeof(int); x++) {
printf("%d ", A[x]);
}

printf("\n");

return 0;
}

/* BEGIN qsortMB.c */

#include <stdio.h>

int partitionMB(int *A, int p, int r);
void qsortMB(int *A, int p, int r);
void swapMB(int* A, int x, int y);

int main(void)
{
int A[] = {5,2,3,7,8,4,10,31,1,43,8,7,3,2,5};
int x;

qsortMB(A, 0, sizeof(A) / sizeof(int) - 1);
for (x = 0; x < sizeof(A) / sizeof(int); x++) {
printf("%d ", A[x]);
}
putchar('\n');
return 0;
}

void swapMB(int* A, int x, int y)
{
int z;

z = A[x];
A[x] = A[y];
A[y] = z;
}

void qsortMB(int *A, int p, int r)
{
int q;

if (p < r) {
q = partitionMB(A, p, r);
qsortMB(A, p, q-1);
qsortMB(A, q+1, r);
}
}

int partitionMB(int *A, int p, int r)
{
int x, j;

x = A[r];
for (j = p; j < r; j++) {
if (A[j] <= x) {
swapMB(A, p++, j);
}
}
swapMB(A, p, r);
return p;
}

/* END qsortMB.c */