Is this reimplemented quicksort correct?

Question

#include<iostream>
using namespace std;
int partition(int arr[],int first,int last,int pivot)
{
 int tmparr[100];
 int left=first,right=last;
 for(int i=first;i<=last;i++)
 {
 if(arr[i]<pivot)
 tmparr[left++]=arr[i];
 else if(arr[i]>pivot)
 tmparr[right--]=arr[i];
 }
 //for the case when pivot is duplicated
 for(int i=left;i<=right;i++)
 tmparr[i]=pivot;
 for(int i=first;i<=last;i++)
 arr[i]=tmparr[i];
 return left;
}
void quicksort(int arr[],int first,int last)
{
 if(first<last)
 {
 int pivotindex = partition(arr,first,last,arr[first]);
 quicksort(arr,first,pivotindex-1);
 quicksort(arr,pivotindex+1,last);
 }
}
int main()
{
 int arr[6]={6,6,9,5,3,7};
 int n=6;
 quicksort(arr,0,n-1);
 for(int i=0;i<n;i++)
 cout<<arr[i];
}

• How do I avoid the copying to tmparr?

• How does the current method of copying to tmparr and back affect my time efficiency as opposed to an in-place swap?

• Am I missing anything in this code? It looks much simpler than implementations I could find online.

• AJMansfield: "I am aware of issues around it being limited to 5 elements instead of dynamic, and some variables not named properly" then you should fix that first.
• Akash: @AJMansfield Fixed most of the names, essentially need feedback on the algo implementation

Answer 1

How do I avoid the copying to tmparr?

Use in-place swaps.

How does the current method of copying to tmparr and back affect my time efficiency as opposed to an in-place swap?

The effort of moving data is approximately the same. I don't see any performance gain or impact, other than that your approach is less cache-friendly.

Am I missing anything in this code? It looks much simpler than implementations I could find online.

Mostly the fact that you can't deal with large datasets, and that stack consumption is significantly larger. Properly implemented (that is, not limited to 100 elements), your algorithm would require \$O(n)\$ space vs \$O(log n)\$ for a real quicksort.

PS: As usual, I can't help noticing that two last loops in partition represent important algorithms (namely, fill and copy), and shall be factored out into functions of their own.

• Akash: Will the larger stack consumption be resolved if I used malloc(last-first) and a corresponding free() instead of the statically allocated tmparr?
• vnp: Unfortunately, no. Extra memory is extra memory, no matter where it comes from.

Answer 2

I know you haven't mentioned anything about this, but I think it should still be addressed.

You should not be passing around C arrays in C++. The entire array is not passed; it merely decays to a pointer to the array.

Instead, use a storage container such as an std::vector. These will not decay to pointers, and using such containers is more idiomatic C++. If you have C++, you can use an std::array instead.

Declare and push back the elements:

std::vector<int> values;
values.push_back(6);
values.push_back(6);
// ...

If you have C++11, initialize an std::array instead:

std::array<int, 6> values = { 6, 6, 9, 5, 3, 7 };

Pass either one to a function:

void func(std::vector<int>& values) {}

void func(std::array<int, 6>& values) {}

You will also no longer need n; storage containers know their sizes. You can access this value with values.size(), which is of the return type std::size_type. This is also safer because the returned value will be updated as the container changes size.

If you don't have C++11, display the container with (const) iterators:

std::vector<int>::const_iterator iter;
// OR
std::array<int, 6>::const_iterator iter;
for (iter = values.cbegin(); iter != values.cend(); iter++)
{
 std::cout << *iter;
}

If you do have C++11, use a range-based for-loop:

for (auto& iter : values)
{
 std::cout << iter;
}

You can use auto here to give you the correct container type automatically.

• Akash: Thanks, but the fact that an array is passed as a pointer is what I am using in my partition and sort functions. Passing it by value would not have allowed me to sort the values without having a return. Still, the vector functions are new to me. Thanks
• Jamal: @Akash: You could still pass them by reference, and I've just added it to this answer.