SHARE
TWEET

Untitled

a guest Nov 9th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*3_4. Реализуйте стратегию выбора опорного элемента “случайный элемент”.
  2.  * Функцию Partition реализуйте методом прохода двумя итераторами от конца массива к началу.
  3.  * */
  4.  
  5. #include <iostream>
  6. #include <random>
  7. #include <ctime>
  8. template <class T>
  9. void swap(T& a,T& b);
  10. template <class T>
  11. void swap(T& a,T& b)
  12. {
  13.     T temp;
  14.     temp=a;
  15.     a=b;
  16.     b=temp;
  17. }
  18.  
  19. int random(int from, int to);
  20.  
  21. template<class T>
  22. struct is1stBigger
  23. { bool operator() (T rightElement, T leftElement)
  24.     {return rightElement > leftElement;}
  25. };
  26.  
  27. bool intBigger(int a,int b)
  28. {return a>b;}
  29.  
  30. template <class T, class TBigger=is1stBigger<T> >
  31. void *insertionSort(T *arr,int size,const TBigger& is1stBigger = TBigger())
  32. {
  33.     for (int i = 1; i < size; i++)
  34.     {for (int j=i;j>0&&is1stBigger(arr[j-1],arr[j]);j--)
  35.         {swap(arr[j-1],arr[j]);}
  36.     }
  37. }
  38.  
  39. //pivot-медиана трех
  40. template <class T, class TBigger=is1stBigger<T> >
  41. T pivotMedianOf3(T *arr, int left,int right,const TBigger& is1stBigger = TBigger())
  42. {
  43.     T pivot1=arr[right];
  44.     T pivot2=arr[left];
  45.     T pivot3=arr[(right+left)/2];
  46.     T * tempArray=new T [3];
  47.     tempArray={pivot1,pivot2,pivot3};
  48.     T pivot=tempArray[0];
  49.     int t=0;
  50.     for( int i = 0; i < 3 ; i++)
  51.     {
  52.         if (is1stBigger(pivot, tempArray[i]))
  53.         {pivot=tempArray[i];
  54.             t=i;}
  55.     }
  56.     swap(tempArray[0],tempArray[t]);
  57.     if (!is1stBigger(tempArray[1],tempArray[2])||tempArray[1]==tempArray[2])
  58.     {pivot=tempArray[1];}
  59.     else
  60.     {pivot=tempArray[2];}
  61. }
  62. template <class T, class TBigger=is1stBigger<T> >
  63. int LomutoPartitionWithLastPivot (T *arr, int left,int right,const TBigger& is1stBigger = TBigger())
  64. {
  65.     T pivot=arr[right];
  66.     swap(arr[right],arr[left]);
  67.     int right1=right;
  68.     for (int i=right;i>=left;i--)
  69.     {if (is1stBigger(arr[i],pivot))
  70.         {swap(arr[i],arr[right1]);
  71.             right1--;}
  72.     }
  73.     swap(arr[left],arr[right1]);
  74.     return right1;
  75. }
  76. template <class T, class TBigger=is1stBigger<T> >
  77. int LomutoPartitionWithRandomPivot (T *arr, int left, int right, const TBigger& is1stBigger = TBigger())
  78. { int key=random(left,right);
  79.     T pivot=arr[key];
  80.     swap(arr[key],arr[left]);
  81.     int right1=right;
  82.     for (int i=right;i>=left;i--)
  83.     {if (is1stBigger(arr[i],pivot))
  84.         {swap(arr[i],arr[right1]);
  85.             right1--;}
  86.     }
  87.     swap(arr[left],arr[right1]);
  88.     return right1;
  89. }
  90. //оптимизация партишна с медианой трех
  91. template <class T, class TBigger=is1stBigger<T> >
  92. int HoarPartitionWithMedian3Pivot(T *arr, int left, int right, const TBigger& is1stBigger = TBigger())
  93. {
  94.     T pivot=pivotMedianOf3(arr,left,right,is1stBigger);
  95.     int leftIterator=left;
  96.     int rightIterator=right;
  97.     while(true)
  98.     {
  99.         while(!is1stBigger(arr[leftIterator] , pivot))
  100.         {leftIterator++;}
  101.         while (is1stBigger(arr[rightIterator] , pivot))
  102.         {rightIterator--;}
  103.         if (leftIterator >= rightIterator)
  104.         {return rightIterator;}
  105.         swap(arr[leftIterator],arr[rightIterator]);
  106.     }
  107.  
  108. }
  109.  
  110. /* k-порядковая статистика
  111.  * template<class T, class TBigger=is1stBigger<T> >
  112. T keyPosition(T *arr,int k,int sizeOfArray,const TBigger& is1stBigger = TBigger())
  113. {int left=0;
  114.     int right=sizeOfArray-1;
  115.     int currentPivotIndex;
  116.     while (true)
  117.     { currentPivotIndex=partition(arr, left, right, is1stBigger);
  118.         if (currentPivotIndex == k)
  119.         {return arr[currentPivotIndex];}
  120.         if (currentPivotIndex > k)
  121.         {right=currentPivotIndex-1;}
  122.         if (currentPivotIndex < k)
  123.         {left= currentPivotIndex + 1;}
  124.     }
  125. }*/
  126.  
  127. template <class T, class TBigger=is1stBigger<T> >
  128. int HoarPartitionWithRandom(T *arr, int left,int right,const TBigger& is1stBigger = TBigger())
  129. {}
  130. template <class T, class TBigger=is1stBigger<T> >
  131. void optimizedQuickSort(T *arr, int left, int right,const TBigger& is1stBigger = TBigger())
  132. //версия с рандомным пивотом, партишн Ломуто, рекурсивный
  133. //поменять партишн на конечный-будет первая версия
  134. {
  135.     if (left <= right)
  136.     {
  137.         int partition = LomutoPartitionWithLastPivot(arr, left, right, is1stBigger);
  138.         optimizedQuickSort(arr, left, partition-1, is1stBigger);
  139.         optimizedQuickSort(arr, partition+1, right, is1stBigger);
  140.     }
  141. }
  142. //версия с оптимизацией рекурсии
  143. template <class T, class TBigger=is1stBigger<T> >
  144. void optimizedQuickSort2(T *arr, int left, int right, int &recursionCounter,const TBigger& is1stBigger = TBigger())
  145. //версия с пивотом медиана трех, партишном Хоара
  146. {
  147.     if (left<right)
  148.     {
  149.         int partition= HoarPartitionWithMedian3Pivot(arr, left, right, is1stBigger);
  150.         if ((right-partition)<=16)
  151.         {insertionSort(arr,partition-left+1,is1stBigger);}
  152.         else
  153.         { optimizedQuickSort2(arr,left,partition,is1stBigger);}
  154.         if ((right-partition-1)<=16)
  155.         {insertionSort(arr,right-partition,is1stBigger);}
  156.         else
  157.         {optimizedQuickSort2(arr,partition+1,right,is1stBigger);}
  158.     }
  159. }
  160.  
  161. int main()
  162. {
  163. int *randArray = new int[100000];
  164. for (int i = 0; i < 100000; i++)
  165. {randArray[i] = random(1,100000);}
  166. //int timeStart = time(0);
  167. optimizedQuickSort(randArray,0,99999,intBigger);
  168. //int timeEnd = time(0);
  169. //timeEnd = timeEnd-timeStart;
  170. //std::cout<<timeEnd;
  171. delete[] randArray;
  172.  
  173. /*
  174.  *
  175.  
  176. int * array=new int[10];
  177. int * array2 = new int [10] {5,12,56,234,13,4,122,9,8,10};
  178. optimizedQuickSort(array2,0,9,intBigger);
  179. for(int i = 0; i < 10; i++)
  180. {std::cout<<array2[i]<<" ";}
  181. //std::cout<<'\n'<<part;
  182.  */
  183. }
  184.  
  185. int random(int from,int to)
  186. {
  187.     srand(time(0)*10);
  188.     int res;
  189.     res=rand()%(to-from+1)+from;
  190.     return res;
  191. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top