İşlev İşaretçileri kullanarak Introsort (İçe dönük sıralama) - MetaTrader 5 için kütüphane

Gözlemsel Sıralama

Bu, orijinal Introsort kütüphanesinin gözden geçirilmiş bir sürümüdür, şimdiIntrosort() işlevi , özel karşılaştırma işlevine isteğe bağlı bir işlev işaretçisi kabul eder.

Intro veya Introspective sort, hızlı performans sağlayan hibrit bir sıralama algoritmasıdır. Üç aşamaya dayanan karşılaştırma tabanlı bir sıralama algoritmasıdır. Quicksort sort ile birlikte heapsort ve insertion-sort algoritmalarını kullanır.

Quick Sort
Quick sort, dizideki bir pivot elemanı seçerek çalışan, ardından diğer elemanları iki alt diziye bölen ve elemanların daha büyük veya daha küçük olup olmadığını kontrol eden bir böl ve fethet algoritmasıdır. Ortalama olarak quick sort alogirthm O(nlog(n)) zaman alır, en kötü durum karmaşıklığı O(ⁿ²)'dir.

Heap Sort
Heap sort algoirthm ikili heap tabanlı karşılaştırma tabanlı bir sıralama yöntemidir. En kötü durum ve ortalama durum zaman karmaşıklığı O(nlog(n)) ve en iyi durum zaman karmaşıklığı O(n) olan kararsız bir sıralama algoritmasıdır.

Ekleme Sıralama
Ekleme sıralama algoritması, son sıralanmış diziyi her seferinde bir öğe oluşturan basit bir sıralama yöntemidir. En kötü durum ve ortalama durum için zaman karmaşıklığı O(ⁿ²) ve en iyi durum için O(n)'dir.

Introsort algoritması bu üç algoritmanın iyi kısımlarını birleştirir. Hızlı sıralama ile başlar, özyineleme derinliği sıralamaya başlanan öğe sayısına bağlı olarak bir seviyeyi aştığında heapsort'a geçer ve öğe sayısı bazı eşik değerlerinden az olduğunda ekleme sıralamasına geçer.

• Bölüm boyutu maksimum derinlik sınırını aşma olasılığı olacak şekildeyse Introsort Heapsort'a geçer.
• Bölüm boyutu çok küçükse, Quicksort Ekleme Sıralamasına geçer.
• Bölüm boyutu sınırın altındaysa ve çok küçük değilse, basit bir quicksort gerçekleştirir.

Introsort özellikle iyi bir çalışma zamanı davranışına sahiptir. Günümüzde kullanılan en hızlı karşılaştırmalı sıralama algoritmalarından biridir ve C++ STL, Microsoft .NET Framework Sınıf Kütüphanesi, GNU Standart C++ kütüphanesi ve LLVM libc++ kütüphanesi ile sağlanan std::sort algoritmasının olağan uygulamasıdır.

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * less karşılaştırma fonksiyonunu kullanarak girdi dizisini yerinde sıralayın.
 * Kendi karşılaştırma fonksiyonunuzu belirtebilirsiniz. Herhangi bir işlev
 * belirtilmezse, artan sıralama kullanılır.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Özel Less() işlevine bir işaretçi kullanarak sıralama yapın. |
//| Özel bir Less() işlevi iki argüman alır ve mantık içerir |
//| sıralanmış dizideki göreli sıralarına karar vermek için. Buradaki fikir
//| Introsort() fonksiyonunun herhangi bir | için kullanılabilmesi amacıyla esneklik sağlamak için
//| tip (nesneler veya yapılar gibi kullanıcı tanımlı tipler dahil) |
//| ve istenen herhangi bir sıralama düzenini elde etmek için kullanılabilir (artan, |
//| azalan veya yapı alanlarının özel sıralaması). |
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Karşılaştırma fonksiyonu Daha az:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- A'ya göre sırala (asc)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- A'da eşitse, B'ye göre sırala (asc)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- B'de eşitse, C'ye göre sırala (asc)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- tüm anahtarlar eşittir
   return(false);
  }


// Özel Less fonksiyonuna bir işaretçi tipi tanımlayın.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Özel Less fonksiyonunu kullanarak yapı dizilerini sıralayın.
Introsort(structArray, (pLess)MyLessFunc);