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.

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.

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.