Secara efisien memilih median dan elemen ke kiri dan kanan

Misalkan kita memiliki satu set dari N coders.$S = \{ a_1,a_2,a_3,\ldots , a_N \}$$N$

Setiap memiliki peringkat dan jumlah medali emas , yang telah mereka menangi sejauh ini.$R_i$$E_i$

Perusahaan Perangkat Lunak ingin merekrut tiga coders untuk mengembangkan aplikasi.

Untuk merekrut tiga coders, mereka mengembangkan strategi berikut:

1. Pertama-tama mereka mengatur coders dalam urutan peringkat naik dan urutan medali emas menurun.
2. Dari daftar yang diatur ini, mereka memilih tiga dari coders tengah. Misalnya, jika daftar yang disusun adalah mereka memilih coders.$(a_5,a_2,a_3,a_1,a_4)$$(a_2,a_3,a_1)$

Sekarang kita harus membantu perusahaan dengan menulis program untuk tugas ini.

Memasukkan:

Baris pertama berisi , yaitu jumlah coders.$N$

Kemudian baris kedua berisi peringkat dari coder i .$R_i$$i$

Baris ketiga berisi jumlah medali emas dikantongi oleh th coder.$i$

Keluaran:

Tampilkan hanya satu baris yang berisi jumlah medali emas yang diperoleh oleh tiga coders yang akan dipilih perusahaan.

Ini adalah masalah memilih th elemen terkecil dari daftar diselesaikan dengan kelas algoritma yang disebut Seleksi Algoritma . Terdapat algoritma pemilihan waktu linear deterministik sehingga masalah Anda dapat diselesaikan dalam waktu linier dengan memilih elemen terkecil n / 2 , n / 2 - 1 , n / 2 + 1 dari daftar yang tidak disortir.$k$$n/2,n/2-1,n/2+1$