Quicksort FAQ

Traditionally in C++, we can make an array like this:

					
	int myArray[5];
					

However, making an array like this requires a constant size, meaning you can't use a variable to make an array of variable length. However, it is still possible to make an array with variable size using dynamic allocation. The following code will dynamically allocate an array of integers:

					
	int* myArray = new int[size];
					

Make sure that you delete your array after you use it, as follows:

				
	delete[] myArray;				
				

The first step in the book's algorithm for partition is to sort the first, middle, and last items. While this will work, we recommend making this a separate function and calling it separately when sorting the array. The test files we provide expect that you will not use the median of three algorithm in your partition function

Memory leaks often frustrate students, but they're actually easy to find if you use this simple procedure. Many leak checkers are comparable to putting a paper towel under a leaking fish tank; they don't really tell you where the leak occurred (or if they try to it's not very helpful) but that there is one. Try following this procedure to find where the memory leak is occurring:

1. Look at the test case you're running. Shave off a couple of lines and run the program. Did the memory leak go away?
2. Keep removing lines from your test file until the memory leak goes away. Whichever was the last one removed is the case that was causing the leak.
3. Form a hypothesis about why that case was causing a leak. For example, if the case that causes the leak for you is when you insertTail on an empty list, your hypotheses may be that you missed checking for that condition in your insertTail function.
4. Create your own test case for that hypothesis. Try to recreate the error in as few lines as possible. This is important because it allows you simplify the case down so it's easier to comprehend as you walk through your code. If you can't recreate the memory leak maybe try a different hypothesis.
5. Walk that test case through your code. In an IDE you can use breakpoints, otherwise you can always use cout statements. You should have a good idea of what each variable's value should be at each step. It may be helpful (as in definitely helpful) to draw a picture of what's going on.

Here are some common mistakes that can cause memory leaks:

• Do you have a destructor? Remember that you don't call clear on a vector when you're done with it. It does that for you in the destructor.
• Do you initialize all of your data members? Use your constructor!!
• Do you delete everything that you allocate? Look at the types that you allocate. Are you sure that you have a delete for every object that you allocate?