First quicksort algorithm

Question

The program is separated in main.cpp, quicksort.cpp, partition.cpp and swap.cpp. There is also a header file to each .cpp file. The idea is from this site.

As you can see, I tried to be very modular. I think instead of having swap.cpp I could've simply used std::swap, right?

But the more important thing is, that I'd like to know how I can improve this quicksort algorithm or how to improve my program in general (not only the algorithm itself).

My three .hpp files are looking like this:

#ifndef __qs__name__
#define __qs__name__

#include <vector>

//protype

#endif

partition.cpp:

#include "partition.hpp"
#include "swap.hpp"

int partition(std::vector<int>& v, int ileft, int iright, int ipivot)
{
  int i = ileft, j = iright;

  while (i <= j)
  {
    while (v[i] < ipivot)
      i++;

    while (v[j] > ipivot)
      j--;

    if (i <= j)
    {
      swap(v, i, j); 
      i++; 
      j--;
    }
  } 

  return j;
}

quicksort.cpp:

#include "quicksort.hpp"
#include "partition.hpp"

void quicksort(std::vector<int>& v, int ileft, int iright)
{
  int p, ipivot = v[iright]; // v[(ileft + iright) / 2];

  p = partition(v, ileft, iright, ipivot);

  if(ileft < p) 
    quicksort(v, ileft, p);

  if((p + 1) < iright) 
    quicksort(v, p + 1, iright);
}

swap.cpp:

#include "swap.hpp"

void swap(std::vector<int>& v, int i, int j) 
{
  int temp = v[i];

  v[i] = v[j];
  v[j] = temp;
}

main.cpp:

#include <vector>

#include "partition.hpp"
#include "quicksort.hpp"
#include "swap.hpp"


int main()
{
  std::vector<int> v;
  v.push_back(7);
  v.push_back(10);
  v.push_back(11);
  v.push_back(1); 
  /*v.push_back(-4543);
  v.push_back(88);
  v.push_back(5);
  v.push_back(3);
  v.push_back(31);
  v.push_back(34);
  v.push_back(7);*/


  for (int i = 0; i < v.size(); i++)
    std::cout << v[i] << std::endl;

  quicksort(v, 0, v.size()-1);
  std::cout << "\n";

  for (int i = 0; i < v.size(); i++)
    std::cout << v[i] << std::endl;

  return 0;
}

Zeta · Accepted Answer · 2017-11-16 17:06:17Z

Any identifier with two underscores is reserved for the implementation. Using such an identifier yields undefined behaviour. Change your include guard. Something along QUICKSORT_GAMDSCHIEE_H is perfectly fine.

The user interface of quicksort should only take a std::vector. That way one cannot use size() by accident:

void quicksort(std::vector<int> & v) {
    quicksort_impl(v, 0, v.size() - 1);
}

Make it hard to use your code in a wrong way.

You can return immediately in both partition and quicksort if ileft == iright and spare yourself some other if.

I think instead of having swap.cpp I could've simply used std::swap, right?

Exactly, or at least re-use it:

void swap(std::vector<int> & v, int i, int j) {
    std::swap(v[i], v[j]);
}

Instead of int we should use std::vector<int>::size_type (which will be size_t usually).

There's no reason to limit your quicksort to std::vector<int> it works fine for any std::vector<T> as long as T provides operator<.

To your "faster quicksort algorithm" question: you can find a std::vector where quicksort will take \$\mathcal O(n^2)\$ instead of \$\mathcal O(n \log n)\$. It's average time complexity is \$\mathcal O(n \log n)\$. Mergesort on the other hand is always \$\mathcal \Theta(n \log n)\$ time complexity.

Usually std::sort will be fast enough for all your use cases.

Taking v[(ileft + iright) / 2] as pivot will avoid \$\mathcal O(n^2)\$ for pre-sorted vectors. — Olivier Jacot-Descombes
– Olivier Jacot-Descombes, Commented Nov 16, 2017 at 17:49
Good point. Taking the median from three random values is even better, see stackoverflow.com/a/164183/1139697. Either way, the fastest sort algorithm is the one that won't get called. If std::sort turns out to be too slow one can optimize, pre-filter the vector or change the data structure, depending on the use case. — Zeta
– Zeta, Commented Nov 16, 2017 at 17:55

Cris Luengo · Accepted Answer · 2017-12-17 02:50:16Z

I'll comment on your division into separate files.

First, swap should, IMO, be defined in the header file (using inline). Any trivial function like that will likely be inlined by the compiler if you give it the chance. By defining it in its own translation unit you rob the compiler of that opportunity, and you depend solely on the linker to do something clever there. Inlining a function is more profitable than just skipping a function call, the code can be mixed in with the code around it and yield extra benefit. std::swap is also defined in a header file.

Second, partition is likely not going to be used on its own, without quicksort. Those two functions belong together. There is no advantage to defining them in two separate translation units, nor declaring them in separate header files. Even if you need only partition, including your sort.h that declares it together with a whole lot of other sorting functions is not an issue. In contrast, managing a mildly complex project where each function is declared and defined in its own two files could easily become a nightmare. For a little project like yours it doesn't matter if there are one or four files to compile and link. But the difference between 100 and 400 is significant!

Look at the standard library interface: <algorithm>, <numeric>, <chrono>, etc. Header files define groups of related functions, not a single function.

Stack Exchange Network

First quicksort algorithm

2 Answers 2

You must log in to answer this question.

Hot Network Questions

First quicksort algorithm

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions