Get best of the week

Urutkan berdasarkan n-piramida


Menyortir tumpukan (itu juga penyortiran piramidal) di Habré telah diingat dengan kata yang baik lebih dari sekali atau dua kali, tetapi ini selalu menjadi informasi yang cukup terkenal. Semua orang tahu tumpukan biner yang biasa, tetapi teori algoritme juga memiliki:

tumpukan-n; banyak tumpukan berdasarkan angka Leonardo; Deramide (hibrida heap dan pohon pencarian biner); turnamen mini-pile; mirror (reverse) heap; tumpukan lemah; Tumpukan Jung; tumpukan binomial; dan Tuhan tahu tumpukan apa yang lain ...

Dan perwakilan paling cerdas dari ilmu komputer di tahun yang berbeda mengusulkan algoritma penyortiran mereka menggunakan struktur piramidal ini. Siapa yang peduli dengan apa yang mereka lakukan - bagi mereka kami memulai serangkaian kecil artikel yang ditujukan untuk menyortir menggunakan struktur ini. Dunia tumpukan beragam - saya harap Anda akan tertarik.
Perangkat Lunak EDISON - pengembangan web
Artikel ini ditulis dengan dukungan EDISON.

Kami terlibat dalam pengembangan aplikasi seluler dan menyediakan layanan pengujian perangkat lunak .

Kami menyukai teori algoritma! ;-)
Ada kelas algoritma seperti itu - pengurutan berdasarkan pilihan. Gagasan umum adalah bahwa bagian array yang tidak berurutan berkurang karena fakta bahwa ia mencari elemen maksimum yang disusun ulang dari itu menjadi area yang diurutkan meningkat.



Menyortir pilihan yang biasa adalah kekerasan. Jika, dalam pencarian maxima, mudah untuk secara linear melalui array, maka kompleksitas waktu dari algoritma semacam itu tidak dapat melebihi O ( n 2 ).

Banyak


Cara paling efisien untuk bekerja dengan ketinggian dalam array adalah mengatur data menjadi struktur pohon khusus, yang dikenal sebagai heap . Ini adalah pohon di mana semua node induk tidak kurang dari node turunan.

Nama lain dari tumpukan - piramida , pohon penyortiran .

Mari kita lihat bagaimana bisa dengan mudah dan hampir bebas untuk menyajikan array dalam bentuk pohon.

Ambil elemen pertama dari array dan pertimbangkan bahwa ini adalah akar dari pohon - simpul level 1. 2 elemen berikutnya adalah node dari level 2, keturunan kanan dan kiri dari elemen root. 4 elemen berikutnya adalah node dari level 3, keturunan kanan / kiri dari elemen kedua / ketiga dari array. 8 elemen berikutnya adalah node dari level 4, keturunan elemen level 3. Dll Dalam gambar ini, node-node dari pohon biner secara jelas terletak secara ketat di bawah elemen-elemen yang sesuai dalam array:



Meskipun demikian, pohon-pohon dalam diagram lebih sering digambarkan dalam pemindaian seperti ini:



Jika Anda melihat sudut ini, maka jelas mengapa menyortir dengan banyak disebut penyortiran piramidal. Meskipun, ini hampir sama seperti jika Anda memanggil gajah catur sebagai perwira, benteng tura, dan ratu ratu.

Indeks untuk turunan dari elemen ke- i ditentukan oleh elementer (jika indeks elemen pertama dari array dianggap sama dengan 0, seperti kebiasaan di sebagian besar bahasa pemrograman):

Keturunan kiri dari 2 × i + 1,
anak kanan: 2 × i + 2

(saya di grafik dan dalam animasi, secara tradisional, indeks array dimulai dengan 1, di mana rumusnya sedikit berbeda: anak kiri: 2 × i dan anak kanan: 2 × i + 1, tapi ini sudah bernuansa aritmatika kecil).

Jika keturunan yang dihasilkan dari formula ini indeks melampaui array, itu berarti bahwa item ke- i tidak memiliki anak. Mungkin juga terjadi bahwa elemen ke- i adalah keturunan kiri (jatuh pada elemen terakhir dari array di mana sejumlah elemen aneh), tetapi tidak ada hak.

Jadi, array apa pun dapat dengan mudah direpresentasikan dalam bentuk pohon, tetapi ini belum menjadi tumpukan, karena, dalam array, beberapa elemen turunan mungkin lebih besar dari elemen induknya.

Agar pohon kita, yang dibuat atas dasar susunan, untuk menjadi tumpukan, perlu diayak dengan benar.

Memilah


Jiwa menyortir banyak sedang menyaring.

Penyaringan untuk suatu elemen adalah jika elemen tersebut lebih kecil dari turunan yang digabungkan dalam rantai yang tidak dapat dipisahkan, maka elemen ini harus dipindahkan serendah mungkin, dan turunan yang lebih besar harus dinaikkan 1 tingkat ke atas.

Gambar menunjukkan jalur pengayakan untuk item. Warna biru menunjukkan elemen yang melakukan penyaringan. Hijau - keturunan yang lebih besar di cabang. Mereka akan dinaikkan satu tingkat ke atas, karena mereka lebih besar dalam ukuran daripada simpul biru yang membuat layar. Elemen itu sendiri dari simpul biru paling atas akan dipindahkan ke tempat keturunan terendah dari rantai hijau.



Penyaringan diperlukan untuk membuat pohon penyortiran dari pohon biasa dan untuk lebih mendukung pohon dalam kondisi (penyortiran) ini.

Dalam gambar ini, elemen-elemen dari array didistribusikan kembali sehingga sudah diletakkan di heap. Meskipun array didekomposisi menjadi pohon penyortiran, itu belum diurutkan (baik naik atau turun), meskipun semua keturunan di pohon lebih kecil dari node induknya. Tetapi kemudian elemen paling maksimal dalam pohon sortasi selalu di root utama, yang sangat penting.



Heap Sort :: Heapsort


Algoritma ini sebenarnya sederhana:

  • Tahap 1. Kami membentuk pohon penyortiran dari seluruh array. Untuk melakukan ini, kita beralih dari kanan ke kiri elemen (dari yang terakhir ke yang pertama) dan jika elemen memiliki keturunan, maka kita menyaringnya.
  • 2. . , . ( ) . , .. . , — . , .




Kode python untuk implementasi semacam piramida klasik:

#    
def HeapSort(data):

    #    
    #   -   
    # (   )       
    for start in range((len(data) - 2) / 2, -1, -1):
        HeapSift(data, start, len(data) - 1) 

    #        
    #        .
    for end in range(len(data) - 1, 0, -1): 
        #       
        #    
        data[end], data[0] = data[0], data[end]
        #        
        #   
        #     
        HeapSift(data, 0, end - 1)
    return data

#   ,      
def HeapSift(data, start, end):

    #   - ,     
    root = start 
    
    #      ,
    #   ,    
    while True:

        child = root * 2 + 1 #  
        #      -  
        if child > end: break 

        #       ,
        #      
        if child + 1 <= end and data[child] < data[child + 1]:
            child += 1

        #     ,   
        #       , 
        #       
        if data[root] < data[child]:
            data[root], data[child] = data[child], data[root]
            root = child
        else:
            break

Kompleksitas Algoritma


Mengapa tumpukan sederhana itu baik - itu tidak perlu disimpan secara terpisah, tidak seperti jenis pohon lainnya (misalnya, pohon pencarian biner berdasarkan array harus dibuat sebelum digunakan). Setiap array sudah menjadi pohon di mana, saat Anda bepergian, Anda dapat segera mengidentifikasi orang tua dan keturunan. Kompleksitas memori tambahan adalah O ( 1 ), semuanya terjadi segera.

Adapun kompleksitas waktu, itu tergantung pada pengayakan. Penyaringan tunggal dilewati dalam O (log n ) . Pertama, kita membuat saringan untuk n elemen untuk membangun tumpukan awal dari array - langkah ini membutuhkan O ( n log n ) . Pada tahap kedua, saat kita mengeluarkan nmaksimum saat ini dari heap, kami membuat satu penyaringan untuk bagian yang tidak disortir yang tersisa, yaitu tahap ini juga merugikan kita O ( n log n ) .

Total kompleksitas waktu: O ( n log n ) + O ( n log n ) = O ( n log n ).
Selain itu, penyortiran piramidal tidak memiliki kasus yang lebih buruk atau lebih baik. Setiap array akan diproses dengan kecepatan yang layak, tetapi tidak akan ada degradasi atau catatan.

Heap sorting rata-rata sedikit lebih lambat daripada sortasi cepat. Tetapi untuk quicksort, Anda dapat mengambil array pembunuh di mana komputer hang, tetapi untuk heapsort - tidak.

Kompleksitas waktu
TerburukRata-rataTerbaik
O(n log n)
O(n2)O(n log n)O(n)


:: Ternary heapsort


Mari kita lihat tumpukan terner. Anda tidak akan mempercayainya dari biner, hanya berbeda bahwa node induk memiliki maksimum tidak dua, tetapi tiga keturunan. Dalam tumpukan ternary untuk elemen elemen ke- i , tiga keturunannya dihitung dengan cara yang sama (jika indeks elemen pertama = 0):

Keturunan kiri 3 × i + 1
Keturunan tengah 3 × i + 2
keturunan kanan 3 × i + 3

(Jika indeks dimulai dengan 1, seperti pada animasi di artikel ini, maka dalam formula ini Anda hanya perlu mengurangi satu).

Proses penyortiran:



Di satu sisi, jumlah level dalam pohon berkurang secara nyata dibandingkan dengan tumpukan biner, yang berarti bahwa rata-rata akan ada lebih sedikit swap selama pengayakan. Di sisi lain, untuk menemukan keturunan minimum, diperlukan lebih banyak perbandingan - karena keturunan sekarang bukan dua, tetapi masing-masing tiga. Secara umum, dalam hal kompleksitas waktu - di suatu tempat kita menemukan, di suatu tempat kita kehilangan, tetapi secara umum hal yang sama. Data dalam tumpukan terner diurutkan sedikit lebih cepat daripada di biner, tetapi percepatan ini sangat kecil. Dalam semua variasi penyortiran piramidal, para pengembang algoritma lebih memilih untuk mengambil opsi biner, karena ternary seharusnya lebih sulit diimplementasikan (walaupun “lebih sulit” untuk menambahkan beberapa atau tiga garis tambahan ke algoritma), dan peningkatan kecepatan minimal.

Urutkan berdasarkan n-heap heaport :: N-narny heapsort


Tentu saja, Anda tidak bisa berhenti di situ dan beradaptasi dengan penyortiran dengan sekelompok keturunan. Mungkin jika Anda terus meningkatkan jumlah keturunan, Anda dapat secara signifikan meningkatkan kecepatan proses?

Untuk elemen ke- i dari indeks array (jika jumlah nol), turunan N -nya dihitung dengan sangat sederhana:

turunan pertama: N × i + 1
turunan kedua: N × i + 2
turunan ketiga: N × i + 3
...
Keturunan ke- N : N × i + N

kode Python untuk mengurutkan berdasarkan tumpukan-N:

#      N 
def NHeapSort(data):

    n = 3 #    

    #    
    #   -   
    # (   )       
    for start in range(len(data), -1, -1):
        NHeapSift(data, n, start, len(data) - 1) 

    #        
    #        .
    for end in range(len(data) - 1, 0, -1): 
        #       
        #    
        data[end], data[0] = data[0], data[end]
        #        
        #   
        #     
        NHeapSift(data, n, 0, end - 1)
    return data
    
#  -     N 
def NHeapSift(data, n, start, end):
    
    #   - ,     
    root = start 

    while True:
        
        #   (    )
        #   
        child = root * n + 1
        if child > end: 
            break 

        max = child
        
        #    
        for k in range(2, n + 1):
            current = root * n + k
            if current > end:
                break
                
            if data[current] > data[max]:
                max = current
        
        #     
        #        
        #  
        if data[root] < data[max]:
            data[root], data[max] = data[max], data[root]
            root = max
        else:
            break

Namun, lebih banyak tidak berarti lebih baik. Jika Anda mengambil situasi ke batas dan mengambil keturunan N untuk array elemen N, kemudian mengurutkan berdasarkan sekelompok menurunkan untuk mengurutkan berdasarkan pilihan yang biasa. Selain itu, ini juga akan menjadi versi yang lebih buruk dari penyortiran berdasarkan pilihan, karena gerakan tidak masuk akal akan dilakukan: penyaringan pertama akan menempatkan maksimum di tempat pertama dalam array, dan kemudian akan mengirim maksimum ke akhir (dalam pemilihan, maksimum dikirim langsung ke akhir).

Jika terner heap minimal menyalip biner, maka quadruple sudah kalah. Menemukan keturunan maksimum di antara beberapa menjadi terlalu mahal.

Trailer Seri Berikutnya


Jadi, kelemahan utama dari binary / ternary / n-heap adalah ketidakmampuan untuk melompat dalam kompleksitasnya lebih tinggi dari O ( n log n ) . Jalan keluar dari jalan buntu adalah menggunakan varietas tumpukan yang lebih canggih dalam menyortir. Dalam seminggu kita akan berkenalan dengan apa yang dipikirkan Edsger Dijkstra tentang ini.


Klik pada animasi untuk pergi ke artikel dengan pengurutan berikut dengan banyak

Referensi


Tumpukan / Piramida

Artikel Seri:



Aplikasi AlgoLab menambahkan penyortiran berdasarkan n-heap. Untuk memilih jumlah keturunan, dalam komentar pada sel semacam ini, Anda perlu menentukan angka untuk n. Kisaran nilai yang mungkin adalah dari 2 hingga 5 (tidak masuk akal lagi, karena untuk n> = 6, animasi dengan tiga tingkat bersarang pada skala normal tidak dijamin sesuai pada layar).

More articles:


All Articles