I improve the quixort using the median of three. First, I found the median in this way: I put the left, middle and right elements of the sequence into an array of three elements, sorted this array by inserts, and selected the middle element. But this is a very non-optimal algorithm. Now I am looking for a median using the conditions:

/*Процедура Partition, модифицированная методом медианы из трех*/ int MedianPartition(int *a, int p, int r){ int left, mid, right, mediana; left = p; mid = (p + r) / 2; right = r; if(left > mid){ if(left < right){ mediana = left; }else mediana = right; }else if(mid > right){ mediana = right; }else mediana = mid; std::swap(mediana, a[r]); return partition(a, p, r); }

I am confused about the logic of the calculations of the median; it seems to me that it is even more complicated than the quicksort itself. What am I doing wrong? Here is an example of the incorrect operation of this algorithm. https://ideone.com/QuNjjd

Supplement . Wrote this function to calculate the median. https://ideone.com/WLqc5R It can be seen that it works in a strange way, and if you use this method of finding the median in the Partition procedure, the sorting will loop.

Addition 2 . As I just did not torment this function in the last 1.5 hours. Here is the last option, and it doesn't work either. https://ideone.com/7VuMdd And before that there was a terrible jumble of ternary operators.

  • That is, you need to find the "middle" from three elements? In any case, in order to sort the three elements you need to make three comparisons (in some cases two will suffice). It is very likely that you are just trying to invent sorting faster. Quicksort many have tried to improve, but it ceases faster only on certain, specially prepared data. - KoVadim
  • This is part of the idea. I have a very fast implementation of the quicksort on the stack of deferred tasks, in it the random element is taken as the supporting element. I want to add a median of three to the implementation of the quicksort on the stack and see what the speed will be. By the way, here I was sealed: not std :: swap (mediana, a [r]) ;, but std :: swap (a [mediana], a [r]); - typemoon

1 answer 1

You need to find the median of the values a[l] , a[(l + r) / 2] , a[r] (and r is the index of the last element in the sorted segment), but for some reason you are looking for a median among the indices (and It seems to me that it is wrong), and not values.

By the way, the median of 3 IMHO values ​​is calculated

 int med (int a, int b, int c) { if (a > b) { // ba ?c if (c > a) // bac return a; return (b > c) ? b : c; } // ab ? c if (c > b) // abc return b; return (a > c) ? a : c; }

Naturally, in your case, you must pass an array and indices, compare the elements of the array and return the index of the median element.