Sayı Sıralama 2{Çözüldü}

[senior]

A,B,C,D,E diye birbirinden farklı 5 tane sayıyı sıralamak istiyoruz. Sayıların tam değerlerini bilmemekle beraber, üçünü seçip birbirleri ile karşılaştırabiliyoruz(Ör: A,B ve C sayılarını seçip A < B < C sonucunu elde ediyoruz). Bu 5 sayıyı sıralamak için (Ör: A < B < E < D < C ) en şanssız durumda minimum kaç karşılaştırma yaparız?

[alpaslankaynar]

İlk önce A,B ve C sayılarını inceleyelim. A>B>C olsun .
Ardından C,D ve E sayılarını incelediğimizde D>E>C veya E>D>C olmadığı takdirde en küçük 2 sayıyı bulabiliriz. En kötü ihtimali düşündüğümüz için bu 2 olayda yalnız en küçük sayıyı (C'yi) bulmuş oluruz.Bu iki olay için de sonuç aynı olacağından D>E>C olsun.
A>B ve D>E yi biliyoruz. A,D,E yi inceleyelim A>D>E(*) veya D>A>E(**) veya D>E>A(***) olur.
(*) yi ele alırsak D,E ve B  yi inceleyerek sonucu bulmuş oluruz.(Toplam 4 karşılaştırma ile)
(**) yi ele alırsak A,E ve B yi inceleyerek sonucu bulmuş oluruz.(Toplam 4 karşılaştırma ile)
(***) yi ele alırsak direk olarak D>E>A>B>C yi buluruz .(Toplam 3 karşılaştırma ile)Fakat en kötü ihtimali düşündüğümüzden sonuç 4 olur.

[senior]

Tebrikler, aslında cevabınız doğru, 4 karşılaştırma, ama 1.karşılaştırmadan sonra D, E ve C sayıları yerine; D E ve B sayılarını karşılaştırmanız daha isabetli olur. Nitekim D,E,C karşılaştırması 20 olasılığı {1,1,6,6,3,3} parçalarına ayırır ama D,E,B karşılaştırması {3,3,4,4,3,3} parçalarına ayırır. Yani en kötü durumu minimize eden karşılaştırma aslında D,E,B'dir. Ama maalesef bu durumda da 2 karşılaştırma daha gerekiyor.