CODEWITHSUNDEEP
c++performancesortingmerge
siw1171
siw1171

Reputation: 9

Why is my quick-sort slower than merge-sort?

This is my implementation. When I put 100 hundred arrays size 1000000, it sorting for 300 sec. My another algorithm, merge sort do it for 40 sec. I wonder, if there are some things that could slow my algorithm.

template <typename TYP> void quick_sort(TYP *tab, int poczatek, int koniec) {
  int i = poczatek;
  int j = poczatek;
  int srodek = (poczatek + koniec) / 2;
  int piwot = tab[srodek];

  swap(tab[srodek], tab[koniec]);

  for (i = poczatek; i < koniec; i++) {
    if (tab[i] < piwot) {
      swap(tab[i], tab[j]);
      j++;
    }
  }
  swap(tab[koniec], tab[j]);

  if (poczatek < j - 1)
    quick_sort(tab, poczatek, j - 1);

  if (j + 1 < koniec)
    quick_sort(tab, j + 1, koniec);
}

Upvotes: 1

Views: 87

Answers (1)

J&#233;r&#244;me Richard
J&#233;r&#244;me Richard

Reputation: 50288

The quick-sort has an average run-time of O(n log(n)) but a worst-case complexity of O(n^2) if the pivot is poorly chosen. Regarding your input array, the pivot you choose can be really bad. To prevent this, you can implement an Introsort. Moreover, you can use a better method to choose the pivot: the median-of-three rule for example.

Moreover, quick-sort is slow for small arrays. You can significantly improve its performance using an insertion-sort for arrays smaller than 15 for example. The last recursive calls will be faster resulting in an overall faster execution.

Finally, your quick-sort use the Lomuto partition scheme which is probably not the most efficient. You can try to use the Hoare's partition scheme.

Upvotes: 2

Related Questions