Kompleksitas Waktu Heapsort

Tumpukan disebut sebagai 'terurut sebagian' dan bukan 'diurutkan sebagian'. Kata “sortir” berarti pengurutan lengkap (complete sorting). Tumpukan tidak dipesan sebagian secara sewenang-wenang. Tumpukan sebagian dipesan mengikuti kriteria (pola), seperti yang ditunjukkan di bawah ini.

Jadi, heapsort terdiri dari dua tahap: membangun heap dan mengekstrak elemen yang dipesan dari atas heap. Pada tahap kedua, setelah setiap ekstraksi, heap dibangun kembali. Setiap pembangunan kembali lebih cepat dari proses pembangunan awal karena pembangunan kembali dilakukan dari pembangunan sebelumnya, di mana satu elemen telah dihilangkan. Dan dengan itu, heapsort mengurutkan daftar yang benar-benar tidak disortir.

Tujuan dari artikel ini adalah untuk menjelaskan secara singkat heapsort dan kemudian menghasilkan kompleksitas waktunya (lihat arti dari kompleksitas waktu di bawah). Menjelang akhir, pengkodean dilakukan dalam C++.

Tumpukan Minimum

Heap dapat berupa heap minimum atau heap maksimum. Max-heap adalah salah satu di mana elemen pertama adalah elemen tertinggi, dan seluruh pohon atau daftar yang sesuai diurutkan sebagian dalam urutan menurun. Min-heap adalah salah satu di mana elemen pertama adalah elemen terkecil, dan seluruh daftar sebagian diurutkan dalam urutan menaik. Dalam artikel ini, hanya tumpukan minimum yang dipertimbangkan. Catatan: dalam topik heap, sebuah elemen juga disebut node.

Heap adalah pohon biner lengkap. Pohon biner dapat dinyatakan sebagai array (daftar); membaca dari atas ke bawah dan kiri ke kanan. Properti heap untuk min-heap adalah bahwa simpul induk kurang dari atau sama dengan masing-masing dari dua anaknya. Contoh daftar tidak berurutan adalah:

Baris pertama dari tabel ini adalah elemen dari array. Di baris kedua adalah indeks berbasis nol. Daftar elemen ini dapat dinyatakan sebagai pohon. Elemen null telah ditambahkan untuk membuat pohon biner penuh. Sebenarnya, elemen nol bukan bagian dari daftar (pohon). Daftar ini tidak memiliki urutan, jadi ini belum menjadi tumpukan. Itu akan menjadi heap ketika memiliki pemesanan sebagian, menurut properti heap.

Hubungan Antara Node dan Indeks

Ingat, heap adalah pohon biner lengkap sebelum memiliki konfigurasi heap (properti heap). Daftar sebelumnya belum menjadi heap, karena elemen tidak mematuhi properti heap. Itu menjadi heap setelah menata ulang elemen menjadi urutan parsial sesuai dengan properti min-heap. Urutan parsial dapat dilihat sebagai pengurutan parsial (meskipun kata 'sort' berarti pengurutan lengkap).

Apakah pohon biner adalah tumpukan atau tidak, setiap orang tua memiliki dua anak, kecuali simpul daun (terakhir). Ada hubungan matematis antara indeks antara setiap orang tua dan anak-anaknya. Sebagai berikut: Jika induk berada pada indeks i, maka anak kiri berada pada indeks:

dan anak yang tepat ada di indeks:

Ini untuk pengindeksan berbasis nol. Jadi, orang tua pada indeks 0 memiliki anak kirinya pada indeks 2×0+1=1 dan anak kanannya pada 2×0+2=2. Orang tua pada indeks 1 memiliki anak kirinya pada indeks 2×1+1=3 dan anak kanan pada indeks 2×1+2=4; dan seterusnya.

Dengan properti min-heap, induk di i kurang dari atau sama dengan anak kiri di 2i+1 dan kurang dari atau sama dengan anak kanan di 2i+2.

Tumpukan

Heapifying berarti membangun tumpukan. Ini berarti mengatur ulang elemen daftar (atau pohon yang sesuai) sehingga memenuhi properti heap. Di akhir proses heapifying, list atau tree adalah heap.

Jika daftar yang tidak disortir sebelumnya ditumpuk, itu akan menjadi:

Catatan: ada 12 elemen dan bukan 15 dalam daftar. Di baris kedua adalah indeks. Dalam proses membangun tumpukan, elemen harus diperiksa, dan beberapa ditukar.

Perhatikan bahwa elemen terkecil dan pertama adalah 3. Elemen lainnya mengikuti secara menaik tetapi bergelombang. Jika anak kiri dan kanan pada posisi 2i+1 dan 2i+2 masing-masing lebih besar dari atau sama dengan induknya di i, maka ini adalah min-heap. Ini bukan pemesanan atau penyortiran penuh. Ini adalah pemesanan sebagian, menurut properti heap. Dari sinilah tahap selanjutnya untuk heap sort dimulai.

Kompleksitas Waktu Heapify

Kompleksitas waktu adalah waktu berjalan relatif dari beberapa kode. Ini dapat dilihat sebagai jumlah operasi utama yang harus diselesaikan oleh kode tersebut. Ada berbagai algoritma untuk membangun tumpukan. Yang paling efisien dan tercepat terus membagi daftar menjadi dua, memeriksa elemen dari bawah, dan kemudian melakukan beberapa pertukaran elemen. Biarkan N menjadi jumlah elemen praktis dalam daftar. Dengan algoritma ini, jumlah maksimum operasi utama (swapping) adalah N. Kompleksitas waktu untuk heapifying diberikan sebelumnya sebagai:

Dimana n adalah N dan merupakan jumlah maksimum operasi utama yang mungkin. Notasi ini disebut notasi Big-O. Ini dimulai dengan O dalam huruf besar, diikuti oleh tanda kurung. Di dalam tanda kurung adalah ekspresi untuk jumlah operasi tertinggi yang mungkin.

Ingat: penjumlahan bisa menjadi perkalian jika hal yang sama ditambahkan terus menerus.

Ilustrasi Heapsort

Daftar unsorted sebelumnya akan digunakan untuk mengilustrasikan heapsort. Daftar yang diberikan adalah:

Min-heap yang dihasilkan dari daftar adalah:

Tahap pertama dalam heapsort adalah menghasilkan heap yang telah dihasilkan. Ini adalah daftar yang dipesan sebagian. Ini bukan daftar yang diurutkan (sepenuhnya diurutkan).

Tahap kedua terdiri dari menghapus elemen terkecil, yaitu elemen pertama, dari tumpukan, menumpuk kembali tumpukan yang tersisa, dan menghapus elemen terkecil dalam hasil. Elemen terkecil selalu menjadi elemen pertama dalam heap yang ditumpuk ulang. Unsur-unsur tersebut tidak dihilangkan dan dibuang. Mereka dapat dikirim ke array yang berbeda dalam urutan di mana mereka dihapus.

Pada akhirnya, array baru akan memiliki semua elemen yang diurutkan (sepenuhnya), dalam urutan menaik; dan tidak lagi hanya sebagian dipesan.

Pada tahap kedua, hal pertama yang harus dilakukan adalah menghapus 3 dan menempatkannya di array baru. Hasilnya adalah:

dan

Elemen yang tersisa harus ditumpuk sebelum elemen pertama diekstraksi. Tumpukan elemen yang tersisa dapat menjadi:

Mengekstrak 5 dan menambahkan ke daftar baru (array) memberikan hasil:

dan

Heapifying set yang tersisa akan memberikan:

Mengekstrak 6 dan menambahkan ke daftar baru (array) memberikan hasil:

dan

Heapifying set yang tersisa akan memberikan:

Mengekstrak 7 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa memberikan:

Mengekstrak 9 dan menambahkan ke daftar baru, memberikan hasil:

dan

Heapifying set yang tersisa memberikan:

Mengekstrak 11 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa akan memberikan:

Mengekstrak 14 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa akan memberikan:

Mengekstrak 15 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa akan memberikan:

Mengekstrak 17 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa akan memberikan:

Mengekstrak 19 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa memberikan:

Mengekstrak 22 dan menambahkannya ke daftar baru memberikan hasil:

dan

Heapifying set yang tersisa memberikan:

Mengekstrak 24 dan menambahkannya ke daftar baru memberikan hasil:

dan

Array tumpukan sekarang kosong. Semua elemen yang ada di awal sekarang berada di array (daftar) baru dan diurutkan.

Algoritma Heapsort

Meskipun pembaca mungkin telah membaca di buku teks bahwa heapsort terdiri dari dua tahap, heapsort masih dapat dilihat sebagai terdiri dari satu tahap, yang secara iteratif menyusut dari array yang diberikan. Dengan itu, algoritma untuk mengurutkan dengan heapsort adalah sebagai berikut:

• Heapify daftar yang tidak disortir.
• Ekstrak elemen pertama dari heap dan letakkan sebagai elemen pertama dari daftar baru.
• Heapify daftar yang tersisa.
• Ekstrak elemen pertama dari tumpukan baru dan letakkan sebagai elemen berikutnya dari daftar baru.
• Ulangi langkah sebelumnya secara berurutan hingga daftar tumpukan kosong. Pada akhirnya, daftar baru diurutkan.

Kompleksitas Waktu Heapsort Tepat

Pendekatan satu tahap digunakan untuk menentukan kompleksitas waktu untuk heapsort. Asumsikan bahwa ada 8 elemen yang tidak disortir untuk diurutkan.

Jumlah operasi maksimum yang mungkin adalah:

Rata-rata dari jumlah operasi ini adalah:

Perhatikan bahwa empat tumpukan terakhir pada ilustrasi sebelumnya tidak berubah, ketika elemen pertama dihilangkan. Beberapa tumpukan sebelumnya juga tidak berubah saat elemen pertama dihapus. Dengan itu, jumlah rata-rata operasi utama (swapping) yang lebih baik adalah 3 dan bukan 4,5. Jadi, jumlah rata-rata total operasi utama yang lebih baik adalah:

sejak log _dua 8 = 3.

Secara umum, kompleksitas waktu kasus rata-rata untuk heapsort adalah:

Di mana titik berarti perkalian dan n adalah N, jumlah total elemen dalam daftar (salah satu daftar).

Perhatikan bahwa operasi mengekstraksi elemen pertama telah diabaikan. Pada topik Kompleksitas Waktu, operasi yang memakan waktu relatif singkat diabaikan.

Pengkodean dalam C++

Di perpustakaan algoritma C++, ada fungsi make_heap() . Sintaksnya adalah:

Dibutuhkan iterator yang menunjuk ke elemen pertama dari sebuah vektor sebagai argumen pertama dan kemudian iterator yang menunjuk tepat di luar akhir vektor sebagai argumen terakhirnya. Untuk daftar yang tidak disortir sebelumnya, sintaks akan digunakan sebagai berikut untuk mendapatkan heap minimum:

Kode ini mengubah konten vektor menjadi konfigurasi heap minimum. Dalam vektor C++ berikut, dua vektor akan digunakan sebagai pengganti dua array.

Untuk menyalin dan mengembalikan elemen pertama dari sebuah vektor, gunakan sintaks vektor:

Untuk menghapus elemen pertama dari sebuah vektor dan membuangnya, gunakan sintaks vektor:

Untuk menambahkan elemen di belakang vektor (elemen berikutnya), gunakan sintaks vektor:

Awal program adalah:

Algoritma dan perpustakaan vektor disertakan. Selanjutnya dalam program adalah fungsi heapsort(), yaitu:

Ini adalah fungsi rekursif. Ini menggunakan fungsi make_heap() dari pustaka algoritma C++. Segmen kode kedua dalam definisi fungsi mengekstrak elemen pertama dari vektor lama setelah pembuatan heap dan menambahkan sebagai elemen berikutnya untuk vektor baru. Perhatikan bahwa dalam definisi fungsi, parameter vektor adalah referensi, sedangkan fungsi dipanggil dengan pengidentifikasi (nama).

Fungsi utama C++ yang cocok untuk ini adalah:

Outputnya adalah:

diurutkan (lengkap).

Kesimpulan

Artikel tersebut membahas secara rinci sifat dan fungsi Heap Sort yang biasa dikenal dengan Heapsort, sebagai algoritma pengurutan. Kompleksitas Waktu Heapify, ilustrasi Heapsort, dan Heapsort sebagai algoritme dibahas dan didukung oleh contoh. Kompleksitas waktu rata-rata untuk program heapsort yang ditulis dengan baik adalah O(nlog(n))