Medyan Ortamında Algoritma algoritması açıklaması

Question

quicksort tip bölümleme algoritmaları, diziyi düzgün bir şekilde bölerek oldukça iyi bir pivot oluşturmak için çok popülerdir. Bu mantık olarak Wikipedia verilir:

belirli dönme daha az ve daha büyük çevresinde N/10 elemanlarının (1/2 * (n/5'tir medyan listesinde elemanlarının yarısından daha hem)) her bir yarı için. Bu elemanların her biri 5 medyanıdır, bu da onu 2 diğer elementten daha az ve bloğun dışında 2 diğer elemandan daha fazla yapar. Bu nedenle, pivot bloğun dışındaki 3 (n/10) öğeden daha azdır ve bloğun dışındaki diğer 3 (n/10) öğeden daha büyüktür. Böylece seçilen medyan,% 30 /% 70 ile% 70/30 arasında bir yere elementleri ayırır, bu da algoritmanın en kötü durum lineer davranışını sağlar. Birisi benim için biraz berrak bir şekilde açıklayabilir mi?

Mantığı anlamakta zorlanıyorum. aşağıdaki numara setinin

Answer 1

Think:

5 2 6 3 1 

Bu sayıların medyan 3 olduğunu. Şimdi n numaralı bir numaranız varsa, n > 3 ise, yukarıdaki sayıların en az yarısından daha büyüktür. n < 3 ise, yukarıdaki sayıların en az yarısından daha küçüktür.

İşte bu fikir. Yani, her 5 sayı için, medyanlarını alırsınız. Artık n/5 numaranız var. Bu apaçık. Şimdi bu sayıların ortancasını alırsanız (m olarak adlandırın), bunların yarısından daha büyük ve diğer yarısından daha küçüktür (medyan tanımına göre!) .0. Başka bir deyişle, m, n/10 numaralarından (kendilerinin küçük 5 element grubunun medyanı) daha büyük ve diğer n/10 sayılarından (yine küçük 5 element grubunun medyanları) daha büyüktür. Örnekte

yukarıda, biz medyan k ise ve m > k varsa, o zaman m da ( k daha kendilerini daha küçüktü) büyük 2'den diğer sayılar olduğunu gördük. Bu, m'un ortamından daha büyük olan 5 eleman grubunun her biri için m'un diğer iki sayıdan daha büyük olduğu anlamına gelir. Bu,'dan küçük olan n/10 küçük 5 eleman grubunun her birinde en az 3 sayı (2 sayı + medyanın kendisi) yapar. Bu nedenle, m en az 3n/10 sayıdan daha büyüktür.

m öğelerinin sayısı için benzer mantık daha büyüktür. - of - median

Answer 2

açıklanması n dışına k'inci en büyük tamsayı bulmak için algoritma medyan da burada bulunabilir: http://cs.indstate.edu/~spitla/presentation.pdf