[MD-sorular] Siralama...

[=?utf-8?q?ihsan=20y=FFfffffccel?=]

Bir paylasim;
  
Verilen n veriyi en hizli sekilde siralamanin yolu nedir? Yani burada ozel bir durum degil de genel bir durum icin gecerli bir siralama teknigi istiyoruz. En verimsiz siralama teknikleri bile eger girilen veriler belli bir duzende ise cok cabuk sonuc verebilir, ama biz boyle bir varsayim yapmiyoruz, genel durumu dusunuyoruz.
   
  Size n veri veriliyor. Siz bu verileri n/2 lik 2 gruba boluyorsunuz. Daha sonra her bir n/2'lik grubu 2'ser parcaya daha boluyorsunuz. Boyle bole bole gidiyorsunuz. En son adimda elinizde 2'lik parcalar kaliyor. 

Bu noktadan itibaren geriye dogru donus basliyor. Elinizdeki ikilileri siraliyorsunuz (yer degistirerek). sonra ikili gruplari ikiser ikiser alip siralayarak kaynastiriyorsunuz. Olusan dortlu gruplari siralayarak kaynastiriyorsunuz... Boyle boyle en son adimda olusan n/2 lik siralanmis iki diziyi siralayarak kaynastiriyorsunuz. 

Ornek: 

3,1,6,9,8,4,7,3,5,3,9,3,0 

adim 1: 
3,1,6,9,8,4 *** 7,3,5,3,9,3,0 

adim 2: 
3,1,6 ** 9,8,4 *** 7,3,5 ** 3,9,3,0 

adim 3: 
3 * 1,6 ** 9,8 * 4 *** 7,3 * 5 ** 3,9 ** 3,0 

Simdi ikilileri siraliyoruz: 

3 * 1,6 ** 8,9 * 4 *** 3,7 * 5 ** 3,9 ** 0,3 

Simdi gerisin geriye gidip, kucuk parcalari siralayarak kaynastiriyoruz: 

1,3,6 ** 4,8,9 *** 3,5,7 ** 0,3,3,9 

1,3,4,6,8,9 *** 0,3,3,3,5,7,9 

0,1,3,3,3,3,4,5,6,7,8,9,9 

Algoritmanin hizli calismasinin sebebi, siralanmis iki kucuk diziyi siralayarak kaynastirma isleminin oldukca hizli bir sekilde yapilabilmesi.
   
  ihsan (...)

       
---------------------------------
Yahoo! kullaniyor musunuz?
Istenmeyen postadan biktiniz mi? Istenmeyen postadan en iyi korunma Yahoo! Posta'da
http://tr.mail.yahoo.com
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20070912/445fe8bd/attachment.htm