Pernah dengar istilah “Divide and Conquer”? Artikel ini secara khusus didasarkan pada pendekatan ini. Gabungkan Sortir adalah algoritme 'bagi dan taklukkan' di mana kita pertama-tama membagi masalah menjadi beberapa subproblem, lalu menggabungkannya untuk mengatasi solusi kita. Berikut ini gambaran lengkap konsep merge sort di J .
melewati referensi di java
Apa itu merge sort di Java?
Merge sort adalah salah satu yang populer algoritma pengurutan tersedia dan mengikuti pendekatan divide and conquer. Masalah dibagi menjadi sub-masalah dan digabungkan bersama untuk mencapai solusi akhir!
Sekarang, apa yang sebenarnya terjadi selama pengerjaan merge sort? Mari kita pahami secara detail.
Bekerja dengan cara merge sort
Ada dua langkah yang diikuti dengan pengurutan gabungan selama proses:
- Membagi: Pada langkah ini, larik masukan dibagi menjadi 2 bagian, pivot adalah titik tengah larik. Langkah ini dilakukan secara rekursif untuk semua setengah larik sampai tidak ada lagi larik setengah untuk membagi lebih lanjut.
- Menaklukkan: Pada langkah ini, kami mengurutkan dan menggabungkan array yang dibagi dari bawah ke atas dan mencapai array yang diurutkan.
Pendekatan ini membantu Anda dengan mudah mengurutkan sub bagian dari masalah terlebih dahulu dan karenanya, mencapai solusinya.
Mari saya tunjukkan representasi bergambar dari jenis gabungan.
Contoh: Diagram
Di sini, Anda melihat bagaimana jenis penggabungan terlihat. Konsep utama dari merge sort adalah waktu yang dibutuhkan untuk mengurutkan lebih sedikit. Sekarang, lanjutkan ke bagian implementasi kami!
Penerapan
paket MyPackage kelas publik MergeSort {void merge (int arr [], int beg, int mid, int end) {int l = mid - beg + 1 int r = end - mid int LeftArray [] = new int [l] int RightArray [] = int [r] baru untuk (int i = 0 iKeluaran:
Array yang diurutkan
satu
4
17
22
2. 3
40
Empat Lima
51
55
90Seperti inilah tampilan kode Java yang menggambarkan jenis gabungan. Pindah ke segmen berikutnya.
Kompleksitas
Kompleksitas dibagi menjadi dua jenis: Kompleksitas waktu dan Kompleksitas ruang. Dalam kasus merge sort, datanya seperti yang ditunjukkan di bawah ini:
Kompleksitas Kasus terbaik
Kasus Rata-rata
Kasus terburuk
Kompleksitas Waktu
O (n log n)
O (n log n)
O (n log n)
Kompleksitas Ruang
-
-
Di)
Dengan ini, saya akan menyimpulkan artikel ini. Semoga konten yang dijelaskan di atas menambah nilai pengetahuan Java Anda. Kami akan terus menjelajahi dunia Jawa bersama. Tetap disini!
Lihat oleh Edureka, perusahaan pembelajaran online tepercaya dengan jaringan lebih dari 250.000 pelajar yang puas dan tersebar di seluruh dunia. Kursus pelatihan dan sertifikasi Java J2EE dan SOA Edureka dirancang untuk siswa dan profesional yang ingin menjadi Pengembang Java. Kursus ini dirancang untuk memberi Anda permulaan dalam pemrograman Java dan melatih Anda untuk konsep Java inti dan lanjutan bersama dengan berbagai kerangka kerja Java seperti Hibernate & Spring.
Ada pertanyaan untuk kami? Harap sebutkan di bagian komentar ini ' Gabungkan sortir di Jawa Blog dan kami akan menghubungi Anda kembali secepat mungkin.
apa kelas anonim di java