Sorting sorusuna

[Chewy]

Soru şu aynen :
Suggest how any sorting algorithm can be augmented in a way to make
the best-case count of its key comparisons equal to just n−1 (n is a list’s
size, of course). Do you think it would be a worthwhile addition to any
sorting algorithm?


Şu soruyu bir açın bana yaw :D Nasıl geliştirebilir demiyor mu best case count karşılaştırması için ? Yani mesela ilk önce sorting algoritması bakıcak sıralı gelmiş hiç ellemiycek mi nolcak kafam karıştı :S

[Deacon]

Diyor ki herhangi bir sorting algoritmasinin best case'ini n-1 karsilastirma yapicak sekilde degistiricek bir yol soyleyin. Sonra da ekliyor bunu herhangi bir sorting algoritmalarina eklemek mantikli midir, deger mi ekledigimize?

[Chewy]

e zaten hepsi n-1 comparison yapmıyor mu ? :D

[Deacon]

O dedigin dogru olsaydi O(n) calisan comparison based sort algoritmalarimiz olurdu ki matematiksel olarak lower bound'un nlogn oldugu gosterildi :p

Ilk mesajinda cevabi yazmissin aslinda. Tam anlamamissin galiba sen sorting olayini?

[Chewy]

valla kafam iice karıstı suan :S

[riglous]

Bak şimdi sorting algoritmalarında sen n defa tüm node'ların üzerinden geçiyorsun bir kere. Bunu yaparken bir yandan da gelen node'ları karşılaştırıyorsun ki bu da logn sürüyor, binary tree olursa. Sonuç olarak senin algoritman O(n logn) oluyor.

Sana diyor ki bunu herhangi bir sorting algoritmasına eklemek mantıklı mı? Bence değil, best case'i n yapması worst case'in de öyle olduğu anlamına gelmez. Algoritmanın hızı worst case üzerinden hesaplanır. Haliyle mantıklı değil. Öte yandan eğer algoritma n'den daha uzun bir sürede yapıyorsa işini, O(n n^2) gibi bir şeyse o zaman eklemek belki performans açısından yararlı olabilir.

[Chewy]

teşekkür ettim anladım.