Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Quicksort

Reply
Thread Tools

Quicksort

 
 
Debaser
Guest
Posts: n/a
 
      05-11-2005
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;
}



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

Thanks in advance.
-Mike-
 
Reply With Quote
 
 
 
 
pete
Guest
Posts: n/a
 
      05-12-2005
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(?).
> 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 */

--
pete
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Gosling's quicksort freezes hiwa Java 4 03-29-2005 08:59 AM
Bentley-Sedgewick ternary QuickSort: C++/C implementation? Alex Vinokur C++ 0 08-30-2004 05:45 AM
Tabelle mit quicksort alphabetisch sortieren Sarah Java 2 10-23-2003 08:18 PM
c++ and quicksort Exekute C++ 6 09-28-2003 09:28 AM
Re: c++ and quicksort David Sachs C++ 1 09-28-2003 02:13 AM



Advertisments