Menü

Sıralamayı C ++ 'da Örneklerle Birleştirme

  • Ana
  • Diğer
  • Sıralamayı C ++ 'da Örneklerle Birleştirme

merge sort c with examples

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

C ++ Birleştirme Sıralama Tekniği.

Birleştirme sıralama algoritması ' böl ve fethet Problemi alt problemlere böldüğümüz ve bu alt problemleri ayrı ayrı çözdüğümüz ”stratejisi.

Bu alt problemler daha sonra birleşik bir çözüm oluşturmak için birleştirilir veya birleştirilir.

=> Popüler C ++ Eğitim Serisini Buradan Okuyun.

Sıralamayı Birleştir

Ne öğreneceksin:

en iyi ücretsiz virüs temizleme nedir

Genel Bakış

Birleştirme sıralaması aşağıdaki adımlar kullanılarak gerçekleştirilir:

# 1) Sıralanacak liste, listeyi ortadaki elemana bölerek eşit uzunlukta iki diziye bölünür. Listedeki elemanların sayısı 0 veya 1 ise, listenin sıralı olduğu kabul edilir.

#iki) Her alt liste, özyinelemeli olarak birleştirme sıralaması kullanılarak ayrı ayrı sıralanır.

# 3) Sıralanan alt listeler daha sonra, tam sıralı bir liste oluşturmak için birleştirilir veya birleştirilir.

Genel Algoritma

Birleştirme sıralama tekniği için genel sözde kod aşağıda verilmiştir.

N uzunluğunda bir dizi bildirmek
N = 1 ise, Arr zaten sıralanmıştır
N> 1 ise,
Sol = 0, sağ = N-1
Ortayı bul = (sol + sağ) / 2
Merge_sort (Arr, left, middle) => ilk yarıyı özyinelemeli olarak sırala
Merge_sort (Arr, middle + 1, right) => ikinci yarıyı tekrar tekrar sırala
Yukarıdaki adımlarda sıralı dizileri birleştirmek için birleştirmeyi (Ok, sol, orta, sağ) arayın.
çıkış

Yukarıdaki sözde kodda gösterildiği gibi, birleştirme sıralama algoritmasında diziyi ikiye böleriz ve her bir yarıyı özyinelemeli olarak birleştirme sıralaması kullanarak sıralarız. Alt diziler ayrı ayrı sıralandığında, iki alt dizi tam sıralanmış bir dizi oluşturmak için birleştirilir.

Birleştirme Sıralaması İçin Sözde Kod

Aşağıda, birleştirme sıralama tekniği için sözde kod verilmiştir. İlk olarak, diziyi yinelemeli olarak yarıya bölmek için bir prosedür birleştirme sıralaması var. Daha sonra, tam sıralanmış bir dizi elde etmek için sıralanmış daha küçük dizileri birleştirecek bir birleştirme rutinimiz var.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 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

Şimdi birleştirme sıralama tekniğini bir örnekle gösterelim.

İllüstrasyon

birleştirme sıralaması İllüstrasyon

Yukarıdaki çizim, aşağıdaki tablo biçiminde gösterilebilir:

GeçmekSıralanmamış listebölmekSıralanmış liste
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
iki{12,23,2,43}
{51,35,19,4}		{12.23} {2.43}
{51.35} {19.4}		{}
3{12.23} {2.43}
{51.35} {19.4}		{12.23} {2.43}
{35.51} {4.19}		{12.23} {2.43}
{35.51} {4.19}
4{12.23} {2.43}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Yukarıdaki gösterimde gösterildiği gibi, önce dizi 4 uzunluklu iki alt diziye bölünür. Her bir alt dizi ayrıca uzunluk 2'ye sahip iki alt diziye daha bölünür. Her bir alt dizi daha sonra bir alt diziye bölünür. her biri bir element. Tüm bu süreç 'Bölme' sürecidir.

Diziyi her biri tek elemanlı alt dizilere böldükten sonra, şimdi bu dizileri sıralı sırayla birleştirmemiz gerekiyor.

Yukarıdaki çizimde gösterildiği gibi, tek bir elemanın her bir alt dizisini ele alıyoruz ve önce iki elemanın alt dizilerini sıralı sırayla oluşturmak için elemanları birleştiriyoruz. Daha sonra, uzunluk iki olan sıralanmış alt diziler sıralanır ve her biri dört uzunluğunda iki alt dizi oluşturmak için birleştirilir. Daha sonra bu iki alt diziyi tam sıralanmış bir dizi oluşturmak için birleştiririz.

Yinelemeli Birleştirme Sıralaması

Yukarıda gördüğümüz algoritma veya birleştirme sıralaması tekniği özyinelemeyi kullanır. Aynı zamanda ' yinelemeli birleştirme sıralaması ”.

Özyinelemeli fonksiyonların, fonksiyon çağırmanın ara durumunu saklamak için fonksiyon çağrı yığınını kullandığını biliyoruz. Ayrıca, parametreler vb. İçin diğer defter tutma bilgilerini saklar ve işlevi çağırmanın yanı sıra yürütmeyi sürdürmenin aktivasyon kaydını saklama açısından ek yük oluşturur.

Özyinelemeli işlevler yerine yinelemeli işlevler kullanırsak, tüm bu genel giderlerden kurtulabiliriz. Yukarıdaki birleştirme sıralama algoritması, döngüler ve karar verme kullanılarak kolayca yinelemeli adımlara dönüştürülebilir.

Yinelemeli birleştirme sıralaması gibi, yinelemeli birleştirme sıralaması da O (nlogn) karmaşıklığına sahiptir, dolayısıyla performans açısından birbirleriyle eşit performans gösterirler. Genel giderleri basitçe düşürebiliriz.

Bu eğitimde, yinelemeli birleştirme sıralaması üzerinde yoğunlaştık ve daha sonra, C ++ ve Java dillerini kullanarak yinelemeli birleştirme sıralaması uygulayacağız.

Aşağıda, C ++ kullanan birleştirme sıralama tekniğinin bir uygulaması verilmiştir.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Çıktı:

Sıralanacak öğe sayısını girin: 10

Sıralanacak 10 öğe girin: 101 10 2 43 12 54 34 64 89 76

Sıralanmış dizi

2 10 12 34 43 54 64 76 89101

Bu programda iki fonksiyon tanımladık, merge_sort ve Git . Merge_sort işlevinde, diziyi iki eşit diziye böler ve bu alt dizilerin her birinde birleştirme işlevini çağırırız. Birleştirme işlevinde, bu alt diziler üzerinde gerçek sıralamayı yapıyoruz ve sonra bunları tam sıralanmış bir dizi halinde birleştiriyoruz.

Daha sonra, Java dilinde Merge Sort tekniğini uyguluyoruz.

class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i

Çıktı:

Giriş Dizisi

101 10 2 43 12 54 34 64 89 76

Birleştirme sıralaması kullanılarak sıralanan dizi

2 10 12 34 43 54 64 76 89101

Java uygulamasında da C ++ uygulamasında kullandığımız mantığı kullanıyoruz.

Birleştirme sıralaması, listeleri sıralamanın etkili bir yoludur ve çoğunlukla bağlantılı listeleri sıralamak için kullanılır. Böl ve yönet yaklaşımı kullandığından, birleştirme sıralama tekniği daha küçük ve daha büyük diziler için eşit derecede verimli performans gösterir.

Birleştirme Sıralama Algoritmasının Karmaşıklık Analizi

Birleştirme sıralaması kullanarak sıralamayı gerçekleştirmek için önce diziyi iki eşit yarıya böldüğümüzü biliyoruz. Bu, logaritmik bir fonksiyon olan 'log n' ile temsil edilir ve atılan adımların sayısı en fazla log (n + 1) 'dir.

Dizinin orta elemanını bulmak için tek adım, yani O (1) gerekir.

Daha sonra alt dizileri n elemanlı bir dizi halinde birleştirmek için, çalışma süresinin O (n) miktarını alacağız.

Dolayısıyla, birleştirme sıralaması gerçekleştirmek için toplam süre n (log n + 1) olacaktır, bu da bize O (n * logn) 'nin zaman karmaşıklığını verir.

En kötü durum zaman karmaşıklığıO (n * günlük n)
En iyi vaka süresi karmaşıklığıO (n * günlük n)
Ortalama zaman karmaşıklığıO (n * günlük n)
Uzay karmaşıklığıO (n)

Birleştirme sıralaması için zaman karmaşıklığı, diziyi her zaman alt dizilere böldüğü ve ardından doğrusal zaman alarak alt dizileri birleştirdiği için her üç durumda da (en kötü, en iyi ve ortalama) aynıdır.

Birleştirme sıralaması, her zaman sıralanmamış dizilerle eşit miktarda alan alır. Bu nedenle sıralanacak liste bir dizi olduğunda, çok büyük diziler için birleştirme sıralaması kullanılmamalıdır. Bununla birlikte, birleştirme sıralaması, bağlantılı listelerin sıralanması için daha etkili bir şekilde kullanılabilir.

Sonuç

Birleştirme sıralaması, dizi veya listeyi çok sayıda alt diziye bölen ve bunları ayrı ayrı sıralayan ve ardından tam sıralanmış bir dizide birleştiren 'böl ve yönet' stratejisini kullanır.

Birleştirme sıralaması, diğer sıralama yöntemlerinden daha hızlı performans gösterir ve aynı şekilde daha küçük ve daha büyük diziler için verimli bir şekilde çalışır.

Gelecek eğitimimizde Hızlı Sıralama hakkında daha fazlasını keşfedeceğiz!

=> Yeni Başlayanlar İçin C ++ Eğitim Kılavuzuna Buradan Dikkat Edin.

Önerilen Kaynaklar

^