Сортировка по кастомному условию

Новый комментарий
 

Как реализовать на MQL4++?

 

Мне нужно сортировать массив сигналов по кастомному условию. В С++ за счет указателей на функцию это делается легко.

 

Подскажите, как это простое желание исполнить на MQL4++ без копи-пасты исходников "Быстрой сортировки" для каждого (наперед неизвестного) условия? Снова макрос?

 
Использование такого макроса для рекурсивной реализации алгоритма "Быстрой сортировки" невозможно, к сожалению.
 

используйте массив указателей и сортируйте его. 
#include <Arrays\ArrayObj.mqh> 

Быстрая сортировка там реализована но так как элемент для сравнения выбирается не рандомно, а центральный элемент, то можно нарваться на худший случай из возможных.

 
ALXIMIKS:

используйте массив указателей и сортируйте его. 
#include <Arrays\ArrayObj.mqh> 

Быстрая сортировка там реализована но так как элемент для сравнения выбирается не рандомно, а центральный элемент, то можно нарваться на худший случай из возможных.

Спасибо, но вы не поняли, что такое кастомное условие сортировки.
 

Спасибо, но вы не поняли как их забивать в 

virtual int       Compare(const CObject *node,const int mode=0) const { return(0);      }

 mode - это кастомное условие, точнее номер, который вы ему определите и обработаете.

 
Разобрались что к чему? Там немного ООП, которое вы так любите.

А так как документаций нет, то что бы понять что тот или этот метод в реальности делает, надо вскрывать внутренности и разбирать все самому.
 
ALXIMIKS:
Разобрались что к чему? Там немного ООП, которое вы так любите.

А так как документаций нет, то что бы понять что тот или этот метод в реальности делает, надо вскрывать внутренности и разбирать все самому.

Вскрыл и даже разобрался, спасибо. Это один из первых методов, что пришел мне в голову. И почти сразу был отметен из-за своей ущербности/кривизны.

Попробую представить решение куда правильнее. Пока только на уровне идеи витает. 

 

Сделал симуляцию указателей на функцию. Sort.mqh:

#property strict

class SORT
{
private:
  template <typename T>
  static void Swap( T &Array[], const int i, const int j )
  {
    const T Temp = Array[i];

    Array[i] = Array[j];
    Array[j] = Temp;

    return;
  }

  template<typename T1, typename T2>
  static int Partition( T1 &Array[], const T2 &Compare, const int Start, const int End )
  {
    int Marker = Start;

    for (int i = Start; i <= End; i++)
      if (Compare.Compare(Array[i], Array[End]) <= 0)
      {
        Swap(Array, i, Marker);

        Marker++;
      }

     return(Marker - 1);
  }

  template<typename T1, typename T2>
  static void QuickSort( T1 &Array[], const T2 &Compare, const int Start, const int End )
  {
    if (Start < End)
    {
      const int Pivot = Partition(Array, Compare, Start, End);

      QuickSort(Array, Compare, Start, Pivot - 1);
      QuickSort(Array, Compare, Pivot + 1, End);
    }

    return;
  }

public:
  /* синтаксис почти соответствует MQL-штатной ArraySort:
       void&       array[]                   // массив для сортировки
       void&       Compare                   // условие сортировки (с направлением)
       int         count = WHOLE_ARRAY,      // количество элементов
       int         start = 0,                // начальный индекс
  */
  template<typename T1, typename T2>
  static void Sort( T1 &Array[], const T2 Compare, int Count = WHOLE_ARRAY, const int Start = 0 )
  {
    if (Count == WHOLE_ARRAY)
      Count = ArraySize(Array);

    if (CheckPointer(Compare) != POINTER_INVALID)
      QuickSort(Array, Compare, Start, Start + Count - 1);

    if (CheckPointer(Compare) == POINTER_DYNAMIC)
      delete Compare;

    return;
  }
};

class COMPARE
{
private:
  const int Mode;

protected:
  template <typename T>
  T SetMode( T Value ) const
  {
    if (Mode != MODE_ASCEND)
      Value = -Value;

    return(Value);
  }

public:
  COMPARE( const int iMode = MODE_ASCEND ): Mode(iMode)
  {
  }

  template<typename T>
  T Compare( const T First, const T Second ) const
  {
    return(SetMode(First - Second));
  }
};

Вот так теперь можно делать кастомную сортировку массивов из любых объектов:

#property strict

#include <Sort.mqh>

template <typename T>
void PrintArray( const T &Array[] )
{
  const int Size = ArraySize(Array);
  string Str = "";

  for (int i = 0; i < Size; i++)
    Str = Str + " " + (string)Array[i];

  Print(Str);
}

class CompareByAbs : public COMPARE
{
public:
  template<typename T>
  T Compare( const T First, const T Second ) const
  {
    return(SetMode(
           MathAbs(First) - MathAbs(Second) // условие сортировки
           ));
  }

  CompareByAbs( const int iMode = MODE_ASCEND ) : COMPARE(iMode) // можно не прописывать (для возможности обратной сортировки)
  {
  }
};

void OnStart( void )
{
  int Array[] = {2, -45, 1, -5, 7, 9};

  SORT::Sort(Array, new COMPARE);
  PrintArray(Array); // -45 -5 1 2 7 9


  SORT::Sort(Array, new CompareByAbs(MODE_DESCEND));
  PrintArray(Array); // -45 9 7 -5 2 1

  return;
}
 

1. Там (в стандартной библиотеке) выбирался центральный элемент массива как опорный, у вас еще хуже вариант.
Дает O(n^2) если сортировать отсортированное не в ту сторону. Например (9 8 7 6 5 4 3 2 1    с MODE_ASCEND)

 

2. Используется лишняя рекурсия в  вызове (удар по времени и памяти).

      QuickSort(Array, Compare, Start, Pivot - 1);
      QuickSort(Array, Compare, Pivot + 1, End);

 Оптимальнее зациклить вторую рекурсию

3. Что бы поменять мод сортировки я должен удалить "объект-функтор"  и создать новый

class COMPARE
{
private: const int Mode; 


Может еще что, особо в код не всматривался - просто пробежался.

П.С. А, точно, как же освобождение памяти от new ?

 
lob32371:

Сделал симуляцию указателей на функцию. Sort.mqh:

А почему SetMode? Обычно определяют что-то типа оператора "меньше". С возвращаемым булевским значением, чтобы можно было сравнивать не только простые типы. Не у любого объекта есть перегруженный оператор "-". Ну и на работу с массивом объектов тоже проверить бы.

Вобщем похоже на годно, но требует доработки.

 
ALXIMIKS:

1. Там (в стандартной библиотеке) выбирался центральный элемент массива как опорный, у вас еще хуже вариант.
Дает O(n^2) если сортировать отсортированное не в ту сторону. Например (9 8 7 6 5 4 3 2 1    с MODE_ASCEND)

 

2. Используется лишняя рекурсия в  вызове (удар по времени и памяти).

 Оптимальнее зациклить вторую рекурсию

Да, не оптимизировал алгоритм самой сортировки. Скиньте сюда, оптимальный с вашей точки зрения, MQL-вариант "быстрой сортировки" для целочисленного массива. Нужно было решить обозначенную в теме проблему. Найденный подход доказал свою робастность.

3. Что бы поменять мод сортировки я должен удалить "объект-функтор"  и создать новый


Может еще что, особо в код не всматривался - просто пробежался.

П.С. А, точно, как же освобождение памяти от new ?

По-моему, гораздо проще (дешево и сердито) написать такой универсальный вызов:

SORT::Sort(Array, new COMPARE);
Чем под каждое условие сортировки городить функцию сортировки. "Объект-функтор" удаляется автоматом.
123
Новый комментарий