Help with quicksort

This is a discussion on Help with quicksort within the C++ Programming forums, part of the General Programming Boards category; I need help implementing quick sort on this but everything else works right. I don't get any errors when compiling ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    22

    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";
    }
    John 3:16 For God so loved the world that He gave His only begotten Son, that whoever believes in Him should not perish but have everlasting life.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    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".
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    48
    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 ?

  4. #4
    Registered User
    Join Date
    Feb 2008
    Posts
    22
    Thanks for the help. I don't completely understand it yet but I will work on it.
    John 3:16 For God so loved the world that He gave His only begotten Son, that whoever believes in Him should not perish but have everlasting life.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by zalezog View Post
    [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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Feb 2008
    Posts
    22
    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.
    John 3:16 For God so loved the world that He gave His only begotten Son, that whoever believes in Him should not perish but have everlasting life.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by c++prog View Post
    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?
    Last edited by iMalc; 11-20-2009 at 11:35 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Feb 2008
    Posts
    22
    Yeah, everything is sorting correctly. I'm just trying to figure everything out.
    John 3:16 For God so loved the world that He gave His only begotten Son, that whoever believes in Him should not perish but have everlasting life.

  9. #9
    Registered User
    Join Date
    Mar 2009
    Posts
    48
    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

    Quote 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

  10. #10
    Registered User
    Join Date
    Feb 2008
    Posts
    22
    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);
    }
    John 3:16 For God so loved the world that He gave His only begotten Son, that whoever believes in Him should not perish but have everlasting life.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Mar 2009
    Posts
    48
    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.
    Last edited by zalezog; 11-24-2009 at 11:21 AM.

  13. #13
    Registered User
    Join Date
    Feb 2008
    Posts
    22
    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.
    John 3:16 For God so loved the world that He gave His only begotten Son, that whoever believes in Him should not perish but have everlasting life.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problems with quicksort!
    By coni in forum C Programming
    Replies: 3
    Last Post: 10-03-2009, 02:29 AM
  2. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 10:26 PM
  3. Question 39: Quicksort vs Linear Search
    By Kleid-0 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 04-17-2005, 11:03 AM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 08:42 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21