Thread: Help with Quicksort

I've been having a lot of trouble with this lately, and I was hoping someone could give me a clue as to what to do. Mostly because the smallest in the array is displayed last, rather than first.

Code:

#include <stdio.h>
#include "simpio.h"
#define size 10
void GetArray();
void quicksort (int array[size], int arraybegin, int end);
int rotate (int array[size], int arraybegin, int end);
void displayarray (int array [size]);
void swap (int array [size], int first, int second);

main()
{
	printf("What is your array? Enter 10 numbers please.\n");
	GetArray();
}

void GetArray()
{
int array[size];
int i;
for (i=0; i<size; i++)
{
	array[i]=GetInteger();
}
quicksort(array, 0, size-1);
displayarray(array);
}


void quicksort(int array[], int arraybegin, int end)
{
	int count;
	if (arraybegin<end)
	{
		count=rotate(array, arraybegin, end);
		quicksort(array, arraybegin, count-1);
		quicksort(array, count+1, end);
	}
}

int rotate(int array[size], int arraybegin, int end)
{
    int piv, poscount, negcount, j;
	j=0;
	piv=array[arraybegin];
	poscount=arraybegin;
	negcount=end;
	j=size;
	while(poscount<=negcount)
	{
		for(poscount=arraybegin;array[poscount]<=piv&&poscount<=size;poscount++);
		for(negcount=end;array[negcount]>piv;negcount--);
		
	}
	swap(array, poscount, negcount);
	return (negcount);
}

void swap (int array [size], int high, int low)
{
	int change;
	change=array[high];
	array[high]=array[low];
	array[low]=change;	
}


void displayarray(int array [size])
{
	int i;
	printf("The sorted array is:");
	for(i=0;i<size;i++)
	{
		printf("&#37;d, ",array[i]);
	}}

'rotate' is not a good name for that function. 'Partition' would be a better choice.

Do you mean to be saying that the only problem is that you want the data sorted in the reverse order to what it is now?
No wait, from looking at it I can tell that it definitely doesn't sort properly yet. You need to perform a swap inside the while loop. Can't quicksort without that.
It would help if you gave a clearer description of the problem.

Those for-loops are horribly unreadable. I mean sure I can understand them, but... YUCK!

Originally Posted by Fect

The for loops function the same as while loops that do the same thing.

However, even with the swap function inside the main while loop, I input an array like [0,2,1,3,4,5,6,7,8,9] and I get an output of [2,1,3,4,5,6,7,8,9,0].

I know it has to do with the rotate function (partition), but I'm stumped.

I'm fully aware that every type of loop construct can be rewritten using a different loop construct. I understand them, but your code is just senseless obfuscation. At least put some spaces in there.

I know the problem is with your 'rotate' function. It is doing the job of a function normally called 'partition'. However it is impossible for it to be doing what it needs to do when it only ever performs a single swap. There has to be a swap in a loop somewhere because it needs to perform up to n/2 swaps for a call with n items.
That's the 'clue' you've been asking for. Now you need to go back to whatever description of the algorithm you have, and identify what you are missing and how to add it to what you have so far.