Return to Answer

• 1

• 7k
• 3
• 22
• 37

I'm going to assume that you're aware of qsort (C implementation of quicksort) and std::sort (C++ sorting routine). Therefore, you are doing this as a programming exercise. There's a reinventing-the-wheel tag for that if you happen to do something similar in the future.

using namespace std;

Why is using namespace std bad practice? Note that the short version is that it can lead to code conflicts and make it difficult to tell where code originates. For example, someone looking at your code might think that you were using std::swap.

int i=0;
while(i<n){
 cout<<a[i]<<",";
 i++;
}

This might be a good time to use a for loop. The main reason being that the logic matches exactly.

// decrement n so as not to have an extra comma at the end
--n;
for ( int i = 0; i < n; ++i ) {
 std::cout << a[i] << ", ";
}
// print the last entry without a trailing comma
std::cout << a[n] << std::endl;

Now the loop definition is all on one line rather than being scattered across three lines. There are times when you're just as well off to use a while as a for, but this isn't one of them.

Note that we can also get rid of the trailing comma by adjusting the loop boundary.

Also adds some horizontal whitespace to make it easier to see where one token ends and another begins.

Adds an end-of-line (which also flushes output), as that made sense in this code. You can leave that off if you want the code to be a little more general. Then you should do it in your main function. Otherwise you end up with your cursor starting on the same line as the output, which is confusing.

void quicksort(int *arr, int left, int right){

The variable name arr always makes me feel like a pirate. It's not that much more descriptive than a.

cout<<"QS:"<<left<<","<<right<<"\n";

This is debugging code. By the time that you are getting a code review, your debugging code should be out of your function.

std::cout << "QS:" << left << "," << right << std::endl;

When you are using debugging code, consider using a std::endl instead of "\n". This is a little slower because it triggers a flush, but when debugging, you're probably better off with slightly slower code that doesn't have anything in the output buffer. That way, if your program crashes, you can see how far it got.

int min = (left+right)/2;

I find this name confusing. The name min would usually be an abbreviation of minimum, but you aren't picking the minimum. You're actually taking the middle element of the range. A more typical name would be mid, although I would go all the way and say middle.

You can get a better average performance by picking a random pivot though. Picking the middle element can devolve to a complexity of \$O(n^2)\$ in the worst case input. The problem arises when the middle element is always either the smallest or largest element in the range.

 while(arr[i]<pivot)
 i++;

This is unclear. You should always indent the contents of loops relative to the looping command. That way we can easily see that the statement is in the loop.

 while ( arr[i] < pivot )
 i++;

Even better, go all the way and write

 while ( arr[i] < pivot ) {
 i++;
 }

This not only makes it obvious what is and is not in the loop, but it protects against accidentally adding a statement outside the loop that you intended to be inside. As a practical matter, having to debug a mistake once takes more time than adding a thousand curly brace pairs.

int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};

There may be some excuse for calling it arr in the quicksort function where you don't actually know what it represents. Here though, you should call it by something more descriptive, if only test_data.

int test_data[8] = {110, 5, 10,3 ,22, 100, 1, 23};
int test_data_count = sizeof(test_data)/sizeof(test_data[0]);

I'd also go ahead and determine the number of elements ahead of time. You use the same expression twice. Rather than repeating yourself, precalculate it.

quicksort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
print(arr, (sizeof(arr)/sizeof(arr[0])));

Now we have to change this to match our previous changes.

quicksort(test_data, 0, test_data_count-1);
print(test_data, test_data_count);

This has the side effect of making it much easier to see what you are doing. That expression is counting the number of elements in the test_data. We then pass one less than that as the third parameter to quicksort and we pass the exact amount to print.