Veri Yapıları - Sıralama Algoritmasını Birleştirme

Birleştirme sıralaması, böl ve yönet tekniğine dayalı bir sıralama tekniğidir. En kötü durum zaman karmaşıklığı Ο (n log n) iken, en saygın algoritmalardan biridir.

Birleştirme sıralaması önce diziyi eşit yarıya böler ve ardından bunları sıralı bir şekilde birleştirir.

Birleştirme Sıralaması Nasıl Çalışır?

Birleştirme sırasını anlamak için, sıralanmamış bir diziyi aşağıdaki gibi alıyoruz -

Atomik değerlere ulaşılmadığı sürece, birleştirme sıralamanın önce tüm diziyi yinelemeli olarak eşit yarılara böldüğünü biliyoruz. Burada 8 öğeden oluşan bir dizinin 4 boyutlu iki diziye bölündüğünü görüyoruz.

Bu, orijinaldeki öğelerin görünüm sırasını değiştirmez. Şimdi bu iki diziyi yarıya böldük.

Bu dizileri daha da böleriz ve artık bölünemeyen atomik değer elde ederiz.

Şimdi, onları parçalandıkları gibi birleştiriyoruz. Lütfen bu listelere verilen renk kodlarına dikkat edin.

Önce her listenin elemanını karşılaştırıyoruz ve sonra bunları sıralı bir şekilde başka bir listede birleştiriyoruz. 14 ve 33'ün sıralanmış pozisyonlarda olduğunu görüyoruz. 27 ile 10'u karşılaştırıyoruz ve 2 değerin hedef listesinde ilk önce 10'u, ardından 27'yi koyuyoruz. 19 ve 35'in sırasını değiştirirken 42 ve 44 sırayla yerleştiriliyor.

Birleştirme aşamasının bir sonraki yinelemesinde, iki veri değerinin listelerini karşılaştırıyoruz ve hepsini sıralı bir sıraya yerleştirerek bulunan veri değerleri listesine birleştiriyoruz.

Son birleştirmeden sonra liste şöyle görünmelidir -

Şimdi birleştirme sıralamanın bazı programlama yönlerini öğrenmeliyiz.

Algoritma

Birleştirme sıralaması, daha fazla bölünemeyene kadar listeyi eşit yarıya bölmeye devam eder. Tanıma göre, listedeki yalnızca bir öğe ise sıralanır. Ardından, birleştirme sıralaması, yeni listeyi de sıralı olarak koruyarak daha küçük sıralanan listeleri birleştirir.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Sözde kod

Şimdi, birleştirme sıralama işlevleri için sözde kodları göreceğiz. Algoritmalarımızın iki ana işleve işaret ettiği gibi - bölme ve birleştirme.

Birleştirme sıralaması özyineleme ile çalışır ve uygulamamızı aynı şekilde göreceğiz.

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 programlama dilinde birleştirme sıralama uygulaması hakkında bilgi edinmek için lütfen buraya tıklayın .