# Quicksort

Discussion in 'C Programming' started by Debaser, May 11, 2005.

1. ### DebaserGuest

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(?).

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

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

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

-Mike-

Debaser, May 11, 2005

2. ### peteGuest

Debaser wrote:
>
> 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(?).
>
> --------------
>
> /* 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 */

--
pete

pete, May 12, 2005