Selam şöyle bir kod var

import std.stdio, std.algorithm;

void permutationSort(T)(T[] items) pure nothrow {
   while (items.nextPermutation) {}
}

void main() {
   auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
   data.permutationSort;
   data.writeln;

}

Bu kod Visual D ile derlenip çalıştırıldığında ya da bağımsız çalıştırıldığında dahi çok uzun sürede çalışıyor yani program başladıktan 4-5 saniye sonra sıralamayı yazdırıyor acaba neden?

Çalışma zamanını nasıl öğrenebilirim? Kaç saniyede istediğimi vermiş diye yani.

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

Sanırım -1 işleri karıştırıyor!

Üstelik T == byte[] olduğu zaman bile süre aynı. Yani diyeceğim o ki veri türünün içerebileceği tüm olasılıkları hesaplıyor ama byte ile 127 ile sınırlamama rağmen değişen bir şey olmadı. Tabi -1 değerini kaldırırsanız normalleşiyor.

Sebebini ben bilmiyorum :p

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

Dlang forumlarından Chris cevapladı hocam

One of the main reasons is because the number of permutations an array has is n!. Thus the expected runtime is O(n!). That's a slow, slow algorithm in general. In particular, your array with length 11 has 39,916,800 permutations (although it, obviously, doesn't have to go through all of those to get the sorted sequence in this case).

You might be able to come up with a faster way to permute, but it's mostly pointless because it will always be very slow. Use std.algorithm.sort if you want to sort quickly, as that uses an algorithm that is O(n log n)

Compare:
11! = 39,916,800
11 log_2 11 = ~38

So the best you could really expect to do is be around a million times slower than a regular sort.

Kısacası daha hızlı olabilir ama en hızlı hali bile yavaş olacak bu algoritma genelde de yavaş çalışıyor demiş. 11! = 39,916,800

demiş yani bu hız normal demiş.

Windows için kodladığım timer'da programın çalışma süresine baktım da

//başlangıç 1:10:52,69
//sonuç [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
//bitiş 1:11:04,14

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

Hocam bu O(log N), Big O Notation mu oluyor. Dün bir arkadaşımla bunu konuşuyorduk o da bunu tavsiye etti bana.

Aslında o direkt Big O Notation olarak belirtmedi

Asymptotic Notation duydun mu dedi aklima bu geldi.

Öneriniz olan algoritmalar var mı?

Ben aşağıdakileri çözdüm. Ama sadece sıralama algoritmaları istemiyorum mesela çok farklı algoritmalar da istiyorum örneğin genetic algoritmalar, yapay zeka algoritmalari gibi programlamada çok iyi olduğumdan istemiyorum kendimi geliştirmek için :)

Bogo Sort
Bubble Sort
Coctail Sort
Counting Sort
Gnome Sort
Heap Sort
Merge Sort
Pancake Sort
Permutation Sort
Quick Sort
Radix Sort
Shell Sort
Sleep Sort
Stooge Sort
Strand Sort
Josephus Problem
Fast Fourier Transform

Bunlar çözüp bitirdiklerim

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

Algorithmic complexity denen kavramın bir örneğini yaşıyorsun. O(log N) karmaşıklıkta sıralama algoritmaları varken daha yavaşına gitmeye gerek yok. :)

Ali

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

Demek eleman sayısı 11 olunca farkedilir derecede artıyor, iyimiş :)

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

Bir sürü algoritma araştırdım bulduklarımı çözdüm hala arıyorum :d

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

Bogo sort'un bir şaka olduğu açık, değil mi?

void main() {
   auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
   while (!isSorted(data))
       randomShuffle(data);
   data.writeln;
}

Diziyi rasgele karıştır, belki sıralanmış olur. Olmazsa tekrarlar. :)

Haber gruplarında bir de miracle sort çıktı:

void main() {
   import core.thread;
   immutable period = 1.seconds;
   auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];

   while (!isSorted(data)) {
       Thread.sleep(period);
   }

   data.writeln();
}

Onda da hiçbir şey yapmadan sıralanmış mı diye bakıyorsun. Belki bir mucize olur ve sıralanır. :p

Ali

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

Alıntı (agora):

Evet, büyük O harfiyle ifade idelen ve bir algoritmanın karmaşıklığı ile ilgili bilgi veren gösterime Big O notation deniyor.

N, işlenecek eleman sayısını ifade eder. O(N^2) olduğunda eleman sayısının karesine bağlı bir zaman tutacak demektir. Örneğin, O(N^2) olan bir algoritma tek eleman için t zaman alıyorsa, 1000 eleman için t'nin 1000x1000=1_000_000 katı kadar zaman alır demektir.

O(lg N) ise N'nin logaritmasına bağlı bir zaman alır demek. lg 1000 kabaca 10 olduğundan, 1000 elemanın işlenmesi tek elemanın işlenmesinin yalnızca 10 katı zaman alır. Bir milyon nerede, 10 nerede. :)

Eleman sayısı olarak 1000 yerine daha büyük sayılar seçince fark daha da açık hale gelir.

Ali

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

Evet hocam Bogo Sort şaka yani aslında buna saçma sıralama demişler :)

void bogoSort(T)(T[] data) {
   while (!isSorted(data))
       randomShuffle(data);
}

void main() {
   auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8];
   bogoSort(array);
   writeln(array);
}

//Saçma Sıralama

Ayrica hocam Miracle Bogo Sort icin birisi grafik tarzi bir sey yapmis SWF ile :)

http://wonderfl.net/c/gT9W/read

Bu ne kadar doğru bilmiyorum ama input'a 4 yerine 6 yazdım 10 dakikadır uğraşıyo düzelmeye :)

Belki ilgilenen olabilir diye söyleyeyim benim en çok ilgimi çeken Miracle Numbers diye bir algoritma oldu :)

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