Gabungkan Sort dalam C ++: Panduan Lengkap – Codewithaden

Dalam Gabungan algoritma, kami membagi array secara rekursif menjadi dua bagian sampai masing-masing sub-array berisi satu elemen, dan kemudian kami menggabungkan sub-array dengan cara yang menghasilkan a diurutkan Himpunan.

Jenis gabungan c ++

C ++ Gabungan adalah algoritma yang efisien dan berbasis perbandingan untuk mengurutkan array atau daftar bilangan bulat. Gabungkan Sorts terus membagi daftar menjadi bagian yang sama sampai tidak dapat lagi dibagi. Menurut definisi, itu diurutkan jika hanya ada satu elemen dalam daftar. Kemudian, Gabungkan Sort menggabungkan daftar yang diurutkan lebih kecil menjaga daftar baru diurutkan.

Ini adalah sebuah Bagilah dan menaklukkan Algoritma yang diciptakan John von Neumann pada tahun 1945. Sekarang Anda dapat mempertanyakan apa itu metode Divide and Conquer.

Gabungan Dalam C ++ pertama kali membagi array menjadi bagian yang sama dan kemudian menggabungkannya dengan cara yang diurutkan. Anda dapat memeriksa Sortir Gelembung dan Jenis seleksi Contoh di blog ini.

Ini seperti metode Divide and Conquer. Jadi ayo Diskusikan metode Divide and Concur.

Divide dan Concur memiliki tiga tugas berikut.

  1. Membagi Masalah menjadi subproblem yang mirip dengan ukuran asli tetapi lebih kecil.
  2. Menaklukkan Sub-masalah secara rekursif. Jika mereka berukuran lebih kecil, sembuh secara langsung.
  3. Menggabungkan Solusi tersebut menjadi solusi, yang merupakan jawaban untuk masalah asli.

Mari kita pahami gabungan dalam C ++ dan kemudian tulis program yang menunjukkannya.

Bagaimana Algoritma Bagi dan Menaklukkan

Masalah penyortiran: Urutkan urutan elemen ke dalam urutan yang tidak menanggapi.

Membagi Bagilah -Dua elemen yang akan diurutkan menjadi dua setelah n/2 elemen masing -masing

Menaklukkan: Urutkan kedua selanjutnya secara rekursif menggunakan gabungan.

Menggabungkan Gabungkan keduanya diurutkan setelah menghasilkan jawaban yang diurutkan

Pendekatan sortir penggabungan top-down adalah metodologi yang menggunakan mekanisme rekursi. Dimulai dari atas dan berlanjut ke bawah, dengan setiap giliran rekursif menanyakan pertanyaan yang sama seperti “Apa yang harus dilakukan untuk mengurutkan array?” dan memiliki jawaban sebagai, “Pisahkan array menjadi dua, lakukan panggilan rekursif, dan gabungkan hasilnya.”, Sampai seseorang sampai ke dasar pohon array.

Contoh

Oke, sebelum pergi ke kode, pertama -tama pahami model gabungan; Ini akan membantu Anda mengetahui kodenya.

Mari kita pertimbangkan daftar bilangan bulat:

43 63 93 24 15 27 21

Jadi, sesuai algoritma, pertama -tama kita perlu membagi panjang daftar (n) menjadi dua bagian sampai mereka dibagi menjadi satu node.

Jadi disini, n = 7 sekarang n/2 = 3 . Dengan demikian, bagian pertama akan dari 3 bilangan bulat, dan bagian kedua akan berasal 7-3 = 4 bagian.

Perhatikan bahwa: jika ukuran daftarnya rata, kedua belah pihak akan dibagi secara merata. Tetapi untuk kasus ukuran yang lebih kecil yang aneh akan berada di sisi kiri, dan yang lebih signifikan akan berada di sisi kanan.

Jadi, setelahnya Langkah 1, Daftar ini akan dibagi seperti yang berikut.

43 63 93 24 15 27 21

Seperti ini lagi, kita akan membagi masing -masing daftar dengan 2. kiri Daftar samping akan berada di 1+2, dan daftar sisi kanan akan muncul di bagian 2+2. Hal yang sama akan terjadi lagi sampai mereka semua terpisah. Jadi, di sini kita akan melihat daftar akhir setelah metode Divide. Lihat gambar berikut.

Merge

Oke, setelah semua operasi divide dilakukan, kami akan tampil Menaklukkan , Urutkan kedua selanjutnya secara rekursif menggunakan gabungan dan Menggabungkan, itu adalah, Gabungkan keduanya diurutkan setelah menghasilkan operasi jawaban yang diurutkan

Jadi di sini, kita akan melihat apa yang akan menjadi hasil setelah setiap langkah:

C++

Jadi, apa yang terjadi di sini adalah … pertama, membandingkan dua sub-sekuens; Misalnya, 63 dan 93 diperiksa dan ditempatkan dalam urutan naik setelah penggabungan. Demikian pula, 27 dan 21 diperiksa dan kemudian ditempatkan naik setelah penggabungan.

Sekali lagi pada langkah kedua, 43,63,93 diperiksa dan ditempatkan dalam urutan naik setelah bergabung. Dengan cara ini, kami mendapatkan kami Daftar pendek terakhir.

15 21 24 27 43 63 93

Kode semu untuk gabungan

Gabungkan Kode Pseudo adalah sebagai berikut.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure 

C ++ Gabungan Program

Lihat yang berikut mergeSort.cpp mengajukan.

#include
using namespace std;
int Merge(int A[],int p, int q,int r)     
{

	int n1,n2,i,j,k; 
	//size of left array=n1
	//size of right array=n2       
	n1=q-p+1;
	n2=r-q;             
	int L[n1],R[n2];
	//initializing the value of Left part to L[]
	for(i=0;i>n;
	int A[n],i;
	cout<<"Enter array values:\n";
	for(i=0;i>A[i];
	//Calling the MergeSort()
	//First we are passing the array
	//the start index that is 0
	//and the size of the array n
	
	MergeSort(A,0,n-1);
	cout<<"The Sorted List is\n";
	for(i=0;i

Output adalah sebagai berikut.

Example

Kompleksitas waktu untuk gabungan

Durasi dari gabungan:

  1. Divide: Computing the Middle mengambil θ (1)
  2. CONQUER: Memecahkan 2 sub-masalah mengambil 2 /2)
  3. Campurkan: Penggabungan elemen mengambil θ (
  4. Kompleksitas waktu total adalah sebagai berikut.
T(n) = Θ(1)  
if n = 1T(n) = 2T(n/2) + Θ(n) 
if n > 1            
T(n)= 2 T(n/2) + n           
= 2 ((n/2)log(n/2) + (n/2)) + n                
= n (log(n/2)) + 2n              
= n log n – n + 2n               
= n log n + n
= O(n log n ) 

Kekambuhan di atas dapat diselesaikan dengan menggunakan pohon kekambuhan atau metode master. Namun, itu jatuh dalam kasus II dari metode master, dan solusi pengulangan adalah O (n log n).

Kompleksitas waktu dari jenis gabungan adalah O (n log n) dalam ketiga kasus (terburuk, rata -rata, dan terbaik) karena jenis gabungan membagi array menjadi dua bagian dan membutuhkan waktu linier untuk menggabungkan dua bagian.

Dengan kompleksitas waktu terburuk adalah (n log n), itu adalah salah satu algoritma yang paling dihormati.

Aplikasi jenis gabungan

  1. Gabungan Urutan Membantu Mengurutkan Daftar Tertaut dalam Waktu O (NLOGN).
  2. Ini digunakan dalam masalah jumlah inversi.
  3. Kita dapat menggunakannya dalam penyortiran eksternal.

Itu untuk tutorial ini.

Posting yang disarankan

C ++ Heap Sort

Sort Penyisipan C ++

Jenis seleksi c ++

C ++ Bubble Sort

C ++ sortir cepat

Artikel ini berasal dari website Winpoin, dan kemudian diterjemahkan ke bahasa indonesia, baca artikel asli disini

Leave a Reply

Your email address will not be published. Required fields are marked *