Kami terus berkenalan dengan berbagai tumpukan dan menyortir algoritma menggunakan tumpukan ini. Hari ini kita memiliki pohon turnamen yang disebut.
Gagasan utama dari Tournament sort adalah menggunakan heap tambahan yang relatif kecil (dibandingkan dengan array utama), yang bertindak sebagai antrian prioritas. Dalam heap ini, elemen pada level yang lebih rendah dibandingkan, sebagai akibatnya elemen yang lebih kecil (dalam hal ini, kita memiliki pohon MIN-HEAP) naik, dan minimum saat ini dari bagian elemen array yang jatuh ke tumpukan ini mengapung ke root. Minimum ditransfer ke array tambahan "pemenang", sebagai hasilnya elemen yang tersisa dibandingkan / dipindahkan di heap - dan sekarang minimum baru berada di akar pohon. Perhatikan bahwa dengan sistem seperti itu, minimum berikutnya lebih besar nilainya daripada yang sebelumnya - maka susunan baru "pemenang" mudah dirakit, di mana minimum baru hanya ditambahkan ke akhir array tambahan.
EDISON .
, . , .
computer science ;-)
Memindahkan minimum ke array tambahan mengarah ke fakta bahwa lowongan muncul di tumpukan untuk elemen berikutnya dari array utama - sebagai akibatnya semua elemen diproses dalam urutan antrian.
Kehalusan utama adalah bahwa selain "pemenang" ada juga "pecundang". Jika beberapa elemen telah dipindahkan ke array "pemenang", maka jika elemen yang belum diproses kurang dari "pemenang" ini, maka tidak ada gunanya menyaring mereka melalui pohon turnamen pada tahap ini - memasukkan elemen-elemen ini ke dalam array "pemenang" akan terlalu mahal (dalam Anda tidak dapat menghentikannya, tetapi untuk menempatkannya di awal, Anda harus menggeser posisi terendah yang sudah dimasukkan). Elemen seperti itu yang tidak berhasil masuk ke dalam array "pemenang" dikirim ke array "pecundang" - mereka akan melewati pohon turnamen di salah satu iterasi berikutnya, ketika semua tindakan diulang untuk pecundang yang tersisa.
Tidak mudah untuk menemukan implementasi algoritma ini di Internet, tetapi implementasi yang jelas dan baik di Ruby ditemukan di YouTube. Kode Java juga disebutkan di bagian "Tautan", tetapi tidak terlihat terlalu mudah dibaca di sana.
#
require_relative "pqueue"
#
MAX_SIZE = 16
def tournament_sort(array)
# , ""
return optimal_tourney_sort(array) if array.size <= MAX_SIZE
bracketize(array) # , ""
end
#
def bracketize(array)
size = array.size
pq = PriorityQueue.new
#
pq.add(array.shift) until pq.size == MAX_SIZE
winners = [] # ""
losers = [] # ""
#
until array.empty?
# "" ?
if winners.empty?
# ""
winners << pq.peek
#
pq.remove
end
# , ""
if array.first > winners.last
pq.add(array.shift) #
else # ""
losers << array.shift # ""
end
# , ""
winners << pk.peek unless pk.peek.nil?
pq.remove #
end
# , - ?
until pq.heap.empty?
winners << pq.peek # ""
pq.remove #
end
# "" , , ,
# "" -
return winners if losers.empty?
# , ""
# ""
array = losers + winners
array.pop while array.size > size
bracketize(array) #
end
#
def optimal_tourney_sort(array)
sorted_array = [] #
pq = PriorityQueue.new
array.each { |num| pq.add(num) } # -
until pq.heap.empty? # -
sorted_array << pq.heap[0]
pq.remove #
end
sorted_array #
end
#
if $PROGRAM_NAME == __FILE__
#
shuffled_array = Array.new(30) { rand(-100 ... 100) }
#
puts "Random Array: #{shuffled_array}"
#
puts "Sorted Array: #{tournament_sort(shuffled_array)}"
endIni adalah implementasi yang naif, di mana, setelah setiap divisi menjadi "pecundang" dan "pemenang", array ini digabungkan dan kemudian untuk array gabungan semua tindakan diulangi lagi. Jika dalam array gabungan ada elemen "kalah" terlebih dahulu, maka menyaring tumpukan turnamen akan memesannya bersama-sama dengan "pemenang".
Implementasi ini cukup sederhana dan jelas, tetapi Anda tidak akan menyebutnya efektif. "Pemenang" yang diurutkan melewati pohon turnamen lebih dari sekali, yang tampaknya jelas tidak perlu. Saya kira kompleksitas waktu di sini adalah log-kuadratik,
Opsi Penggabungan Banyak
Algoritma ini terasa dipercepat jika elemen-elemen yang dipesan yang melewati saringan tidak melewati balapan turnamen lagi.
Setelah susunan yang tidak berurutan dibagi menjadi “pemenang” dan “pecundang” yang tidak disortir, seluruh proses diulang kembali hanya untuk “pecundang”. Pada setiap iterasi baru, satu set array dengan "pemenang" akan diakumulasikan dan ini akan berlanjut sampai pada beberapa langkah tidak ada "pecundang" yang tersisa. Setelah itu, yang tersisa adalah menggabungkan semua array "pemenang". Karena semua array ini diurutkan, penggabungan ini berlangsung dengan biaya minimal.
Dalam formulir ini, algoritma mungkin sudah menemukan aplikasi yang bermanfaat. Misalnya, jika Anda harus bekerja dengan data besar, maka dalam prosesnya, menggunakan tumpukan turnamen, paket-paket data yang dipesan akan dirilis, yang dengannya Anda sudah dapat melakukan sesuatu sementara semua yang lain sedang diproses.
Setiap elemen n array melewati pohon turnamen hanya sekali, yang biaya
Di akhir musim
Serial tentang tumpukan heap hampir selesai. Masih memberi tahu tentang yang paling efektif dari mereka.
Tautan
Tournament sort
Priority queue
Tournament sort in Java
The Theory Behind the The Theory Behind the z/Architecture Sort Assist Instructions
Using Tournament Trees to Sort
Tournament Sort Demo Ruby
Tournament Sort Visualization
Tournament Sort Data Structure UGC NET DS
Tournament Sort Algorithm — a Heapsort variant
:
Penyortiran hari ini telah ditambahkan ke aplikasi AlgoLab, yang menggunakannya - perbarui file excel dengan makro.
Di komentar ke sel dengan nama pengurutan, Anda dapat menentukan beberapa pengaturan.
Variabel cara adalah pohon turnamen berapa arah (untuk berjaga-jaga, dimungkinkan untuk membuat pohon ini tidak hanya biner, tetapi juga ternary, kuartener, dan pentamerik).
Variabel antrian adalah ukuran antrian asli (jumlah node di tingkat terendah pohon). Karena pohon penuh, jika, misalnya, dengan cara = 2 Anda menentukan antrian = 5, maka ukuran antrian akan ditingkatkan ke kekuatan terdekat dari dua (dalam hal ini, hingga 8). NWayMerge
variabel mengambil nilai 1 atau 0 - dengan bantuan itu ditunjukkan apakah akan menggunakan penggabungan multi-jalur atau tidak.