Quicksort Unsorted

[DarthBane]

I understand the majority of quick sort so far(Kinda simple now that i got it) but the only problem I seem to be having is in my last line of code.
Now I know this may not be the cleanest code you have seen this is for a program with no reason. Just for quicksort.

It's sorting the array of numbers:
50 10 20 70 1 40 30 100 90 80 60

and sorts it to be:
1 20 10 30 40 60 70 80 90 50 100

now I commented the last part of the quicksort function and it goes to be:
1 10 20 30 40 50 70 100 90 80 60

first part in order right? therefore the last line of code quicksort(j+1, right, a);
must be the error OR is executing incorrectly.

any help would be AWSOME and much appreciated. I've worn myself out on this one program ha-ha.

#include<iostream>
#include<string>
#include<iomanip>
#include<fstream>
using namespace std;
const int dummy=30;

void printem(double arr[],int nums, ofstream &outf)
{
	int i, j=4;
	for (i=0; i<nums; i++)
	{
		outf<<arr[i]<<" ";
		if(i==j)
		{
			j=j+5;
			outf<<endl;
		}
	}
}
void readem(double arr[], int &nums)
{
	int i=0;
	ifstream inf;
	inf.open ("Q.data");
	while(!inf.eof())
	{
		inf>>arr[i];
		i++;
	}
	nums=i;
}
void swapem(double &a, double &b)
{
	double temp;
	temp=a;
	a=b;
	b=temp;
}


void quicksort(int left, int right, double a[])
{
	int j=left;
	int k=right;

	double pivot=a[left];
	if(left<right)
	{


		do
		{
			do
			{
				j++;
			}
			while(a[j]<=pivot && j<k);
			do
			{
				k--;
			}
			while(a[k]>=pivot && k>0);
			if(j<=k)swapem(a[j], a[k]);
		}
		while(j<k);
		swapem(a[left], a[k]);
		cout<<j<<endl;


		quicksort(left, k, a);
		quicksort(j+1, right, a);

	}
}



void main()
{
	ofstream outf;
	outf.open("Q.out");

	double arr[dummy+1];
	int i, nums;
	readem(arr, nums);
	outf<<"--------------Data unsorted-----------"<<endl;
	printem(arr, nums, outf);

 int left=0, right=nums;
 quicksort(left, right, arr);

 outf<<"---------------data Sorted-----------------"<<endl;
 printem(arr, nums, outf);




	system("pause");
}

[helios]

I believe the problem is in the do whiles.

Suppose that on line 48, pivot=14 and a[k]=13. Line 60 decrements k unconditionally, so a[k] (using the value of k at line 54) will never get swapped.
You need to check the conditions before entering the loops, so use regular while loops.

[jumper007]

I suggest you use the sort() function from the algorithm library.

Example:

// sort algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
  vector<int>::iterator it;

  // using default comparison (operator <):
  sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

Output:

myvector contains: 12 26 32 33 45 53 71 80

Best of wishes,
~ Raul ~

[DarthBane]

Thanks for the replies. I'm trying to keep it as these (I'd love to use the sort function.... SO much easier) But I'm making this program for another program ha-ha.

I tried using the regular while loops but just sits there... endless loop(I cut and pasted above the do's as to replace them)

[helios]

You didn't by any chance make this transformation, did you?

do
{
	j++;
}
while(a[j]<=pivot && j<k);

becomes

while(a[j]<=pivot && j<k);
{
	j++;
}

[DarthBane]

helios:
Yeah I did.

Others:

I found the problem. I have a friend who's programming a like code and we found the problem so simple haha...


in main I called left and right but didn't think right would be nums-1. His did...

also within the quicksort I called "k--". this was a mistake on how I did the while loop. it can not be while(a[k]>=pivot && k>0);
it must be:while(a[k]>pivot && k>0);

why?
endless loop. no matter what it i will continue to increment. this is a problem and causes problems.

here's the code with the fixed solution:

#include<iostream>
#include<string>
#include<iomanip>
#include<fstream>
using namespace std;
const int dummy=30;

void printem(double arr[],int nums, ofstream &outf)
{
	int i, j=4;
	for (i=0; i<nums; i++)
	{
		outf<<arr[i]<<" ";
		if(i==j)
		{
			j=j+5;
			outf<<endl;
		}
	}
}
void readem(double arr[], int &nums)
{
	int i=0;
	ifstream inf;
	inf.open ("Q.data");
	while(!inf.eof())
	{
		inf>>arr[i];
		i++;
	}
	nums=i;
}
void swapem(double &a, double &b)
{
	double temp;
	temp=a;
	a=b;
	b=temp;
}


void quicksort(int left, int right, double a[])
{
	if(left<right)
	{
	int j=left;
	int k=right+1;

		do
		{
			do
			{
				j++;
			}
			while(a[j]<=a[left]);
			do
			{
				k--;
			}
			while(a[k]>a[left]);
			if(j<k)swapem(a[j], a[k]);
		}
		while(j<=k);
		swapem(a[left], a[k]);


		quicksort(left, k-1, a);
		quicksort(k+1, right, a);

	}
}



void main()
{
	ofstream outf;
	outf.open("Q.out");

	double arr[dummy+1];
	int i, nums;
	readem(arr, nums);
	outf<<"--------------Data unsorted-----------"<<endl;
	printem(arr, nums, outf);

 int left=0, right=nums-1;
 quicksort(left, right, arr);

 outf<<"---------------data Sorted-----------------"<<endl;
 printem(arr, nums, outf);




	system("pause");
}

thanks everyone for the help. And I will probably be using the easier way of sorting next time ;)

THANKS!!!!!