Help with quicksort

I need help implementing quick sort on this but everything else works right. I don't get any errors when compiling the program but when I run it and enter the values I get an error that says it has stopped working. Thanks for any help in advance.

Code:

#include <iostream>
#include <iomanip>
using namespace std;

const int MAX_ACCOUNTS = 200;

void readcustomeridacctbalance(int idarray[], int numaccounts, double balancearray[]);
void quicksort(int idarr[], int low, int high);
void displaydata(int idarray[], int numaccounts, double balancearray[], double minpayment[]);

void main()
{
	int number,
		idarray[MAX_ACCOUNTS];
	double balancearray[MAX_ACCOUNTS],
		   minreqpayment[MAX_ACCOUNTS];

	cout << "Enter the number of accounts: ";
	cin >> number;
	while(number>MAX_ACCOUNTS)
	{
		cout << "That is an invalid number of accounts. Please reenter: ";
		cin >> number;
	}

	readcustomeridacctbalance(idarray, number, balancearray);
	int left = idarray[0],
		right = idarray[number];
	quicksort(idarray, left, right);
	displaydata(idarray, number, balancearray, minreqpayment);
}

void readcustomeridacctbalance(int idarray[], int numaccounts, double balancearray[])
{
	for(int i = 0; i < numaccounts; i++)
	{
		cout << "What is your ID number? ";
		cin >> idarray[i];
		cout << "What is your account balance? ";
		cin >> balancearray[i];
	}
}

void quicksort(int idarr[], int low, int high)
{
	int	i = low,
		j = high,
		tmp,
		pivot = idarr[(low+high)/2];
	while (i <= j)	//While there is more than 1 account
	{
            while (idarr[i] < pivot)
				i++;
            while (idarr[j] > pivot)
				j--;
            if (i <= j) 
			{
                  tmp = idarr[i];
                  idarr[i] = idarr[j];
                  idarr[j] = tmp;
                  i++;
                  j--;
            }
      };
      // recursion
	if (low < j)
		quicksort(idarr, low, j);
	if (i < high)
		quicksort(idarr, i, high);
}

void displaydata(int idarray[], int numaccounts, double balancearray[], double minpayment[])
{
	unsigned int totalid=0;
	double totalbalance=0,
		   totalminpayment=0;

	cout << "_______________________________________________________________\n"
		<<setw(11)<<"ID"<<setw(20)<<"Account Balance\n"<<setw(31)
		<<"_______________________________________________________________\n";
	for(int i = 0; i < numaccounts; i++)
	{
		cout <<setw(11)<<idarray[i]
		<<setw(10)<< "$" << balancearray[i]<<"\n";
		totalid+=idarray[i];
		totalbalance+=balancearray[i];
	}
	cout << "_______________________________________________________________\n"
		<< "Total: " << setw(1) << totalid << setw(10) << "$" << totalbalance
		<< setw(27)<< "\n\nAverage Account Balance: $"
		<< totalbalance/numaccounts << "\n";
}

The first thing I noticed is that this would fail a unit test for sorting an empty array, due to this line:

Code:

		pivot = idarr[(low+high)/2];

Yes even sorting an empty array is extremely common!

However, the main problem is that you're calling it with the items you've looked up from the array instead of simply passing 0 and "number".

Code:

int left = idarray[0],
		right = idarray[number]; // << going out of bounds
	quicksort(idarray, left, right);

Passing the value at ith location won't help.
Instead your low and high of

Code:

void quicksort(int idarr[], int low, int high)

expect a valid array index.
The call should have read :

Code:

quicksort(idarray, 0, number - 1);

In your quicksort function, you assume the pivot to be actually located at its right place, won't be true most of the times.The while loop in

Code:

while (i <= j)	//While there is more than 1 account
	{
            while (idarr[i] < pivot)
				i++;
            while (idarr[j] > pivot)
				j--;
            if (i <= j)  {
			
                  tmp = idarr[i];
                  idarr[i] = idarr[j];
                  idarr[j] = tmp;
                  i++;
                  j--;
            }
      };

actually locates your pivot.

At the beginning of your quicksort function , let's say you move your idarr[(low + high) / 2] to the end of the array.
then your while loop determines where to place the pivot

Code:

while (i < j)	//While there is more than 1 account
	{
            while (idarr[i] <= pivot && i < j)
				i++;
            while (idarr[j] >= pivot && i < j)
				j--;
            if (i < j) 
			{
                  tmp = idarr[i];
                  idarr[i] = idarr[j];
                  idarr[j] = tmp;
            }
     }

'i' determines the position of the element which is greater than the pivot.
So it should be placed on the right hand side of the pivot so, you make a swap.

Code:

idarr[high] = idarr[i];
idarr[i] = pivot;

Now you recursively call quicksort to sort the left hand side and then the right hand side of the array

Code:

quicksort(idarr, low ,i - 1 );
quicksort(idarr, i + 1, high);

The final quicksort function looks something like this:

Code:

void quicksort(int idarr[], int low, int high)
{
	int	i = low,
		j = high,
		tmp,
		pivot ;
	    
	// Where is the terminating case ? Array sorted
    if (low >= high)
		return; 
	//Move the pivot to the end of the aray
	pivot = idarr[(low+high)/2];
	idarr[(low+high)/2] = idarr[high];
	idarr[high] = pivot;

      
	while (i < j)	//While there is more than 1 account
	{
            while (idarr[i] <= pivot && i < j)
				i++;
            while (idarr[j] >= pivot && i < j)
				j--;
            if (i < j) 
			{
                  tmp = idarr[i];
                  idarr[i] = idarr[j];
                  idarr[j] = tmp;
            }
     }
    //Returned the pivot to its rightful place
	idarr[high] = idarr[i];
	idarr[i] = pivot;
	// recursion
	
		quicksort(idarr, low ,i - 1 );
	
		quicksort(idarr, i + 1, high);
}

This sorts just the ids, you also need to swap the balance of each customer ?

Thanks for the help. I don't completely understand it yet but I will work on it.

Originally Posted by zalezog

[CODE]
In your quicksort function, you assume the pivot to be actually located at its right place, won't be true most of the times.The while loop in

Code:

while (i <= j)	//While there is more than 1 account
	{
            while (idarr[i] < pivot)
				i++;
            while (idarr[j] > pivot)
				j--;
            if (i <= j)  {
			
                  tmp = idarr[i];
                  idarr[i] = idarr[j];
                  idarr[j] = tmp;
                  i++;
                  j--;
            }
      };

actually locates your pivot.

As odd as it looks, the technique used above does actually correctly perform the partitioning, and does also successfully eliminate the need to do the extra i < j checks in the inner loops! Whilst most partitioning steps swap out the pivot item to the end of the array and swap it back in place afterwards, the above code only makes a copy of the pivot point beforehand and then simply moves the pivot point into one of the partitions. What happens is that if either i or j discovers the pivot point then the pivot point is simply swapped into the other partition's area. Items equivalent to the pivot value may be placed in either partition.
The loops are guaranteed to not run off either end because moving inwards from either end has to find the pivot eventually. Also, once a single swap has been made, i and j wont go past each other by more than one, because the i index will hit an item not geater than the pivot and the j index will hit an item not less than it, when they come across the other partitions items. If no swaps are made for the entire partitioning step then the pivot was in the right place already and both i and j find it and stop.

It does mean that one of the partitions to recurse on contains the pivot value as well, giving it one extra item to process, but you do remove the need to swap the pivot value back into place prior to the recursive calls, and from my experiments this and the removal of the i < j tests from the inner loops, more than offsets any speed loss that would have otherwise occurred. You do also end up comparing the pivot item to a copy of itself however.

I've been tempted to write up something on this technique for some time. It's very different from how we're taught QuickSort, but in my experience it's somewhat superrior.
Thoughts?

Why is the "&& i < j" needed even though the while loop that it is within already checks for that? When I comment it out the sort works incorrectly with 4 values and with 5 it crashes but I don't understand why.

Originally Posted by c++prog

Why is the "&& i < j" needed even though the while loop that it is within already checks for that? When I comment it out the sort works incorrectly with 4 values and with 5 it crashes but I don't understand why.

Consider this code:

Code:

            while (idarr[i] <= pivot /*&& i < j*/)
				i++;

Initial array: 2, 4, 5, 1, 3
With the chosen pivot (5) swapped with the rightmost item: 2, 4, 3, 1, 5
now, we iterate while idarr[i] is less than or equal to pivot. Well, all of them are greater than or equal to the pivot so we go off the end of the array. Where does it stop? Who knows, the next few memory locations might contain zeros, so perhaps it keeps going. Then a little later we perhaps reach a page that isn't allocated and BOOM... Access violation reading some address.

So yes, if you do it the traditional way using code such as what zalezog posted, you need the i<j check in the innermost loops.

Can we assume that with the i<j checks your code now sorts correctly?

Yeah, everything is sorting correctly. I'm just trying to figure everything out.

While not exactly a prompt response, I agree with iMalc, the algorithm worked perfectly, the only problem was that c++ prog wasn't calling the function with correct parameters

Originally Posted by iMalc

but in my experience it's somewhat superrior.
Thoughts?

If the number of swaps are compared between the QuickSort(c++prog) and the version which i gave, the number of swaps in my case always seem to be less even after you set an if condition on comparing the element with itself.

Code:

while (idarr[i] < pivot)
				i++;
            while (idarr[j] > pivot)
				j--;
            if (i <= j)  
                 if (i != j)
                     swap

How would I maintain the association between the balance and the id while sorting id in ascending order using your code zalezog? I was able to do it with the old code after changing the parameters by doing this.

Code:

void quicksort(int idarr[], int low, int high, double balancearr[])
{
      int i = low, j = high;
      int tmp;
      int pivot = idarr[(low + high) / 2];
	  double baltmp;
      /* partition */
      while (i <= j) 
	  {
            while (idarr[i] < pivot)
                  i++;
            while (idarr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = idarr[i];
                  idarr[i] = idarr[j];
                  idarr[j] = tmp;
		  baltmp = balancearr[i];
		  balancearr[i] = balancearr[j];
		  balancearr[j] = baltmp;
                  i++;
                  j--;
            }
      };
      /* recursion */
      if (low < j)
            quicksort(idarr, low, j, balancearr);
      if (i < high)
            quicksort(idarr, i, high, balancearr);
}

The same way you would have had to do it with pretty much any quicksort implementation, which is how you have it now. Looks kinda like a self-answering question to me

By the way, your code still isn't correct for sorting zero items. Can you imagine how annoying it would be if you had to always check that your container wasn't empty before calling std::sort?
My earlier hint was an attempt to get you to add a

Code:

if (low <= high) return;

line near the top of the function, and then having done that, you can remove the two similar if-statements near the end of it.

I also prefer the half-open interval type such as used by the SC++L rather than having to subtract one when calling it. It actually simplifies the code, but I wont go through how to do it now. You can investigate it on your own if you care about it.

Let's say you make a swap function which looks something like this:

Code:

void swap(int idarr[], int index1, int index2, double balance[]) {
     int temp;
	 temp = idarr[index1];
	 idarr[index1] = idarr[index2];
	 idarr[index2] = temp;

     double tmp;
	 tmp = balance[index1];
	 balance[index1] = balance[index2];
	 balance[index2] = tmp;
}

Then you can replace all calls of swap with this method, although now quicksort always will have an exra parameter with it (the balance array), which looks something like this:

Code:

void quicksort(int idarr[], int low, int high, double balance[])
{
	int	i = low,
		j = high,
		
		pivot ;
	    
	// Where is the terminating case ?
    if (low >= high)
		return; 
	//Move the pivot to the end of the aray
	pivot = idarr[(low+high)/2];
	
              //<< does the same thing as pivot does, stores the balance's  pivot
               double balance_pivot = balance[(low+high)/2]; 
	swap(idarr, (low+high)/2, high, balance);
	
	
	//idarr[(low+high)/2] = idarr[high];
	//idarr[high] = pivot;

      
	while (i < j)	//While there is more than 1 account
	{
            while (idarr[i] <= pivot && i < j)
				i++;
            while (idarr[j] >= pivot && i < j)
				j--;
            if (i < j) 
			{
                  swap(idarr, i, j, balance);
            }
     }
    //Returned the pivot to its rightful place
	idarr[high] = idarr[i];
	balance[high] = balance[i];
	idarr[i] = pivot;
	balance[i] = balance_pivot;
	// recursion
	
		quicksort(idarr, low ,i - 1, balance );
	
		quicksort(idarr, i + 1, high,balance);
}

This seems more like tweaking a program, had you been given to write a program which along with balance of a customer asks you to store the account holder's name ,age , address, pincode.. would you make arrays for all of them ?

Classes(more c++ way) or structure would have been perfect here.
Had you made a structure like:

Code:

typedef struct Customer {
     int id;
     double balance;
    . ..
}Customer;

You would have then easily swapped all structure elements at one go and your parameter list for each function would have been certainly shorter.

But after testing your code(with dynamic pivot) and my code with 10 million numbers, your code was faster by around 1.5 seconds, your method seems certainly superior.

I don't know much about classes which is why I didn't use them for this program but later after learning more I might try and implement it into the program. I just modified the quicksort from this website: QUICKSORT (Java, C++) | Algorithms and Data Structures so I don't deserve credit for the code and it seems to me like you still have a better understanding of the algorithm because of how you were able to implement it in a different way despite the fact that the code I used was faster.