D ile hızlı sıralama quick sort u en kolay nasıl yazardınız. Buradaki amacım Python'un olanakları ile D olanaklarını karşılaştırmak:

Örneğin Python için:

   sayilar = [1, 2, 3, 4, 5, 6]
   tekSayilar = [x for x in sayilar if x % 2 == 1]

Scheme gibi işlevsel dillerde bulunan lambda (D'de de sanırım isimsiz işlevler var) olanağını kullanabiliyorsunuz. Evet D ile hızlı sıralama algoritmasını (hazır işlevler kullanmadan) nasıl yazardınız.

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

Alıntı (acehreli):

Evet Python ile doğru sonuç veriyor. Ancak D'de yanlış sonuç veriyor.

Alıntı (acehreli):

Bence de kaldırılsın. Hatta Python'un yazım biçimi çok harikayken D'yi bu konuda çok başarılı bulduğumu söyleyemeyeceğim.

=>!() Bu kadar karakterin yazılması biraz zor oluyor. Ya da artık ben biraz tembelleşmeye başladım.

Alıntı (acehreli):

>         auto parçalar = partition3(elemanlar, elemanlar[$ / 2]);
> ```

>

O zaman yarısı çözülmüş oluyor tabi  ;-)

Ben o kullanıma bakınca ortadan bölüyor diye düşünmüştüm ama örneğin [5, 3, 25, 6, 10, 17, 1, 2, 18, 8] gibi bir dizide böyle bir sonuç çıktı.

[2, 3, 8, 6, 10, 5, 1], [17], [18, 25]

Bu arada güzel bir örnek olmuş oldu.

Alıntı (acehreli):
>
>

    // parçalar[1] pivot'a eşit olanları kapsıyor; zaten doğru yerdeler

Katılır mısınız bilmiyorum ama 'pivot 'için 'mihenk (http://www.tdk.gov.tr/index.php?option=com_gts&arama=gts&guid=TDK.GTS.5050f97bc96365.64015960)' demişler. Ölçü, ölçüt, kriter anlamında.

Bir de mihenk taşı var.Altın veya gümüş üzerine sürüldüğü takdirde, bıraktığı çizgilerden bu madenlerin saflık dereceleri anlaşılıyormuş.

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

   auto küçük = sayılar[1..$].filter!(x => x < sayılar[0])();

Benim düşündüğüm çözüm de bu şekilde. Ancak bunu bir 'int[]''e nasıl çevireceğimi bilmiyorum.

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

Python için süzme işlemi gösterdin. Hızlı sıralamaya biraz aşağıda geçeceğim.

Bu konularda kullanışlı olan iki olanak oluyor: Generator kavramı Python'da iç olanak olduğu halde D'deki aralık (range) kavramı kütüphanelerle gerçekleştirilmek durumunda. Ancak, aralıkların bütünüyle kütüphane olanağı olduğunu söylemek de yanlış olur çünkü foreach döngüsü InputRange aralığı kavramını tanır ve foreach ile rahatça kullanma olanağı sunar. O açıdan bakınca biraz da dilin iç olanağı kabul edilebilir.

Gösterdiğin kod D'de neredeyse aynı (Not: tek sayı karşılaştırmasınd ==1 yapılırsa eksi sayılarda yanlış sonuç verir):

import std.algorithm;
// ...
   immutable sayılar = [1, 2, 3, 4, 5, 6];
   auto tekSayılar = sayılar.filter!(x => x % 2)();

(Not: dmd'nin -property seçeneği kullanılmazsa sondaki boş parantezlere de gerek olmuyor. Bu konunun sonu nereye varacak bilmiyorum. Parantezsiz yazıma izin verilmeyeceğı söyleniyor ama bazı durumlarda çok da kullanışlı olduğu için herhalde hiç kalkmayacak.)

Yukarıdaki kod da Python'da olduğu gibi tembeldir. Yani sayılar sonsuz bir aralık bile olsa filter sonsuza kadar devam etmez, sayıları gerçekten kullanıldıklarında üretir.

Hızlı sıralama en iyi özyinelemeli olarak gerçekleştirilir. Ama isimsiz işlevler ve özyineleme bir araya gelemiyor çünkü bir isimsiz işlevin içinden kendisini çağırma olanağı yok (çünkü ismi yok :)).

Erdem hile yaptım diye bana kızacak ama ben hızlı sıralamayı şöyle gerçekleştirirdim: :)

import std.stdio;
import std.algorithm;

void hızlıSırala(T)(T[] elemanlar)
{
   if (elemanlar.length >= 2) {
       auto parçalar = partition3(elemanlar, elemanlar[$ / 2]);
       hızlıSırala(parçalar[0]);
       // parçalar[1] pivot'a eşit olanları kapsıyor; zaten doğru yerdeler
       hızlıSırala(parçalar[2]);
   }
}

void main()
{
   auto sayılar = [ 10, 40, 0, -3, 7, 8, 11, 100, -5, 1 ];
   hızlıSırala(sayılar);
   writeln(sayılar);
}

Ali

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

Yani 'küçük' filter'ın sonucunu tutan (veya "üreten") tembel bir aralıktır. Onu hevesli bir biçimde diziye dönüştürmek istiyoruz:

import std.array;
// ...
   küçük.array();
   // veya: array(küçük);

Ali

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

Benim bulduğum çözüm de bu şekilde:

import std.stdio;
import std.algorithm;
import std.array;

T[] hızlıSırala(T)(T[] dizi)
{
   if (dizi.length > 2) {
       auto küçük = dizi[1..$].filter!(x => x < dizi[0])();
       auto büyük = dizi[1..$].filter!(x => x >= dizi[0])();
       return (hızlıSırala(array(küçük)) ~ dizi[0] ~ hızlıSırala(array(büyük)));
   }
   return dizi;
}

void main()
{
   auto sayılar = [5, 3, 25, 6, 10, 17, 1, 2, 18, 8];
   writeln(hızlıSırala(sayılar));
}

Ama çalışmasına şaşırdım aslında. Sabah dmd'nin eski bir sürümü ile derlediğimde sonsuz bir döngüye girmişti.

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

Temel bir tartışma konusu olmuş; Ali hocamın cevabı da çok leziz...:)

Çünkü parametre olarak verilen dizinin içeriğini küçükten büyüğe sıralayarak değiştiriyor. Sanırım bunu yaparken dilimlerden de faydalanıyor olmalı; belki de değil?

Öyle ya, bölümlendirme işlevini hayal edersek, dilimlerin boyutları değişeceğinden hız açısından zararı bile olabilir. Çünkü oluşturulan dilimlerden soldaki (ilk yarı), sağdaki (son yarı) dilimden ister istemez eleman alabilir. Yani sağdaki dilimin elemanları mihenkten (pivot) küçük olması durumunda ikili sıralama (binary sort) gereği sola geçmeli. Bu durumda sağdaki dilimin ortasından bir eleman eksilebileceğinden onun da bir dilim olması anlamsız olacaktır.

Özetle, bu değerlendirmenin ışığında dilim kullanılmasa gerek. Ne dersiniz?

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

Alıntı (acehreli):

Ali bey ben de tam onu soracaktım. Burada bahsettiğiniz hız farkı mihenk olarak seçilen değer ile ilgili değil sanırım. Çünkü baştan, sondan, rastgele seçmenin performansı düşüreceğini söylemişler. En uygun yöntem bir baştan bir ortadan bir sondan değer alıp bunların ortalamasını (medyan) bulmakmış.

Benim hatırladığım kadarıyla dilimler bir referans gerçekleşmesi değil miydi. 'array()' işlevini kullanmadan sadece dilimlerle yapsaydık nasıl olurdu.

Aynı durum Rosetta Code'daki D uygulamasında da da vardı sanırım. Ama ben hala D'deki dilimler referans olduğuna göre neden yavaş çalışıyor tam olarak anlamış değilim.

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

Alıntı (acehreli):

Yazdığım gibi aralık demek istememiştim...

Alıntı (acehreli):

Hmm, bu durumda çok işlemci gücü harcıyor olmalı!

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

Salih, gerçekten "dilim" mi demek istedin yoksa aralık mı? Çünkü zaten hem benimki hem de Erdem'inki dilim alıyor.

Erdem'inkinin daha yavaş olacağını beklerim çünkü her array() çağrısı hevesli bir biçimde yeni bir dizi oluşturuyor. Dizilerin uç uca eklenmelerinden bazıları da elemanların yeni yere taşınmasını gerektirebilir.

Benimkinde ise hiç dizi kopyalama yok. Elemanlar aynı dizi içinde değiş tokuş ediliyorlar. O yüzden ona in-place algoritma denir.

Ali

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