Yine Ali hoca sayesinde süper bir algoritmaya sahip olduk. Yani neredeyse ipteki cambaz gibi algoritmayı her türlü hatim edebiliriz...:)

Ama!

Son döngüsündeki karşılaştırmasını (aslında çıkarma!) tekrar TypeInfo üzerinden yapmam gerekti. Çünkü bu sefer real sayılarda sıkıntı çıktı...:(

Çalışan kod şu:

void main() {
 auto dizi = [5, 3.14, 3, 25, 6, 17, 1, 2, 18, 8];
 dizi.writeln;
 qsort(dizi);
 dizi.writeln;
}

void qsort(T)(ref T[] a) {
 struct Stack(T) {
   T*[] l, r;
   size_t konum;

   void push(T)(T* left, T* right) {
       l ~= left;
       r ~= right;
       konum++;
   }

   void pop(T)(ref T* left, ref T* right) {
       konum--;
       left = l[konum];
       right = r[konum];
   }

   bool empty() const {
       return konum == 0;
   }
 }
 void swap(T* p1, T* p2) {
   T temp = *cast(T*)p1;
            *cast(T*)p1 = *cast(T*)p2;
            *cast(T*)p2 = temp;
 }
 size_t Qsort_Threshold = 7;
 Stack!T sp;

 T* lbound = a.ptr;
 T* rbound = a.ptr + a.length;
 T* li, ri;

 while(true) {
   if(rbound - lbound > Qsort_Threshold) {
     swap(lbound + ((rbound - lbound) >> 1), lbound);

     li = lbound + 1;
     ri = rbound - 1;

     if((*li - *ri) > 0) swap(li, ri);
     if((*lbound - *ri) > 0) swap(lbound, ri);
     if((*li - *lbound) > 0) swap(li, lbound);

     while(true) {
       do li += 1; while ((*li - *lbound) < 0);
       do ri -= 1; while ((*ri - *lbound) > 0);
       if(li > ri) break;
       swap(li, ri);
     }

     swap(lbound, ri);

     if(ri - lbound > rbound - li) {
       sp.push(lbound, ri);
       lbound = li;
     } else {
       sp.push(li, rbound);
       rbound = ri;
     }
   } else {
     for(ri = lbound, li = lbound + 1; li < rbound; ri = li, li++) {
       // auto t = *ri - *(ri + 1);/*
       TypeInfo ti = typeid(T.init);//*/
       for(;  ti.compare (ri, ri+1) > 0; ri--) {
         swap(ri, ri + 1);
         if(ri == lbound) break;
         //t = *ri - *(ri + 1);
       }
     }
     if(!sp.empty) sp.pop(lbound, rbound);
     else break;
   }
 }
}

Aslında karşılaştırma işlevi kesirli sayılarda değişiyormuş. Belki o yüzden bu konuda sıkıntı yaşamış olmalıyım. Yani tam sayılarda basit bir şekilde çıkarma işlemi yapılırken. Bakınız real değişken türünde şöyle bir algoritma kullanımış:

Alıntı:

>     static int _compare(real d1, real d2)
>     {
>         if (d1 !<>= d2) // if either are NaN
>         {
>             if (d1 !<>= d1)
>             {
>                 if (d2 !<>= d2)
>                     return 0;
>                 return -1;
>             }
>             return 1;
>         }
>         return (d1 == d2) ? 0 : ((d1 < d2) ? -1 : 1);
>     }
> ```

>

-- 
[ Bu gönderi, <http://ddili.org/forum>'dan dönüştürülmüştür. ]

Peki hocam, bu algoritmada eşik (threshold) nedir? Son yazdığımda ismi Qsort_Threshold ve dizi uzunluğu ile orantılı artması gerekiyor yoksa sonsız döngüye giriyor...:(

Belki orijinal koda bakarsan daha iyi anlaşılır. Ben bunun yerine dizi uzunluğunu kullandım 1-2 binlik dizilerde sıkıntı yapmadı ama onbinlere çıkınca yine sonsuz döngüye girdi. Demek ki hala algoritma üzerinde cambazlık yapamıyorum...:(

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Temel hata gösterge aritmetiğine elem_size'ı karıştırmandan kaynaklanıyor. Onlar byte* kullandıkları için bir sonraki elemana geçmek için elem_size eklemek zorundaydılar.

Sen şablona dönüştürdüğün ve T* kullandığın için gösterge aritmetiği elemanların uzunluğunu hesaba katar.

Programın doğru sonuç üretmesi için hemen yapman gereken şu:

 size_t elem_size = 1; //T.sizeof;

Ama elem_size'ı tümden kaldır.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

He he. :) O konu da kitapta var. Şurada "Kesirli sayı karşılaştırmaları" başlığında:

http://ddili.org/ders/d/kesirli_sayilar.html

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Her algoritmanın iyi ve kötü olduğu tarafları vardır. Örneğin, eleman adedi belirli bir sayının altındaysa quick sort'un "mihenk bul, gösterge hesabı yap, özyinele, vs." düzeneği, getirdiği kazançtan daha yavaştır.

Buradaki algoritma eleman adedi 7 veya daha az eleman olduğunda insertion sort algoritmasına geçiyor. Sıralama algoritmalarının bir karşılaştırması şurada var:

http://en.wikipedia.org/wiki/Sorting_algorithm

Bunun benzeri bir durum arama algoritmalarında da görülür: Belirli bir sayının altında sırayla arama bile ikili aramadan daha hızlıdır.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]