İçindekiler
- giriiş
- C++'da Birleştirme Sıralaması Nedir?
- Böl ve Fethet Yaklaşımı
- Birleştirme Sıralama Algoritması
- Merge Sort'un C++'da Uygulanması
- Çözüm
1. Giriş
Bilgisayar bilimindeki sıralama algoritmaları, verileri artan veya azalan düzende düzenlemek için kullanılır. Farklı özelliklere sahip birden fazla sıralama algoritması mevcuttur. Merge sort, C++'da dizileri sıralayabilen yöntemlerden biridir.
2. C++'da Birleştirme Sıralaması Nedir?
Birleştirme sıralaması, bir dizinin öğelerini düzenleyebilen böl ve fethet tekniğini kullanır. Ayrıca C++'daki öğelerin listesini de sıralayabilir. Girdiyi ikiye böler, her bir yarıyı bağımsız olarak sıralar ve ardından bunları doğru sırada birleştirir.
3. Böl ve Yönet Yaklaşımı
Sıralama algoritması, giriş dizisini daha küçük alt dizilere bölmeyi, bunları ayrı ayrı çözmeyi ve ardından sıralanmış bir çıktı üretmek için sonuçları birleştirmeyi gerektiren bir böl ve fethet stratejisi uygular. Birleştirme sıralaması durumunda, dizi, her yarıda yalnızca bir öğe kalana kadar yinelemeli olarak iki yarıya bölünür.
4. Birleştirme Sıralama Algoritması
Birleştirme sıralama algoritması iki ana adımdan oluşur: bölme ve birleştirme. Adımlar aşağıdaki gibidir:
4.1 Böl
Birleştirme sıralama algoritması, bir dizideki öğeleri sıralamak için bir böl ve fethet stratejisini izler.
- Algoritmanın ilk adımı dizi öğelerini kontrol edecektir. Bir öğe içeriyorsa, zaten sıralanmış olarak kabul edilir ve algoritma aynı diziyi herhangi bir değişiklik yapmadan döndürür.
- Dizi birden fazla öğe içeriyorsa, algoritma onu iki yarıya bölmeye devam eder: sol yarı ve sağ yarı.
- Birleştirme sıralama algoritması daha sonra dizinin sol ve sağ yarısına yinelemeli olarak uygulanır, bunları etkili bir şekilde daha küçük alt dizilere böler ve ayrı ayrı sıralar.
- Bu özyinelemeli süreç, alt dizilerin her biri yalnızca bir öğe içerene kadar devam eder (adım 1'e göre), bu noktada bunlar nihai, sıralanmış bir çıktı dizisi oluşturmak için birleştirilebilir.
4.2 Birleştirme
Şimdi dizileri birleştirme adımlarını göreceğiz:
- Birleştirme sıralama algoritmasının ilk adımı, boş bir dizi oluşturmayı içerir.
- Algoritma daha sonra giriş dizisinin sol ve sağ yarısının ilk öğelerini karşılaştırmaya devam eder.
- İki öğeden küçük olanı yeni diziye eklenir ve ardından giriş dizisinin ilgili yarısından çıkarılır.
- 2-3 arasındaki adımlar daha sonra yarımlardan biri boşalana kadar tekrarlanır.
- Boş olmayan yarıda kalan tüm öğeler daha sonra yeni diziye eklenir.
- Ortaya çıkan dizi artık tamamen sıralanmıştır ve birleştirme sıralama algoritmasının son çıktısını temsil eder.
5. Merge Sort'un C++'da Uygulanması
C++'da birleştirme sıralamasını uygulamak için iki farklı yöntem izlenir. Her iki yöntemin zaman karmaşıklığı eşdeğerdir, ancak geçici alt dizilerin kullanımları farklıdır.
C++'daki birleştirme sıralaması için ilk yöntem iki geçici alt dizi kullanırken, ikincisi yalnızca bir tane kullanır. İlk yöntemdeki iki geçici alt dizinin toplam boyutunun, ikinci yöntemdeki orijinal dizinin boyutuna eşit olduğunu, dolayısıyla uzay karmaşıklığının sabit kaldığını belirtmekte fayda var.
Yöntem 1 – İki Sıcaklık Alt Dizisi Kullanma
Burada, iki geçici alt dizi kullanan Yöntem 1'i kullanan C++'da birleştirme sıralaması için örnek bir program verilmiştir:
#includead alanı std'sini kullanma ;
geçersiz birleştirmek ( int varış [ ] , int ben , int M , int R )
{
int n1 = M - ben + 1 ;
int n2 = R - M ;
int L [ n1 ] , R [ n2 ] ;
için ( int Ben = 0 ; Ben < n1 ; Ben ++ )
L [ Ben ] = varış [ ben + Ben ] ;
için ( int J = 0 ; J < n2 ; J ++ )
R [ J ] = varış [ M + 1 + J ] ;
int Ben = 0 , J = 0 , k = ben ;
sırasında ( Ben < n1 && J < n2 ) {
eğer ( L [ Ben ] <= R [ J ] ) {
varış [ k ] = L [ Ben ] ;
Ben ++;
}
başka {
varış [ k ] = R [ J ] ;
J ++;
}
k ++;
}
sırasında ( Ben < n1 ) {
varış [ k ] = L [ Ben ] ;
Ben ++;
k ++;
}
sırasında ( J < n2 ) {
varış [ k ] = R [ J ] ;
J ++;
k ++;
}
}
geçersiz birleştirme Sıralaması ( int varış [ ] , int ben , int R )
{
eğer ( ben < R ) {
int M = ben + ( R - ben ) / 2 ;
birleştirme Sıralaması ( varış , ben , M ) ;
birleştirme Sıralaması ( varış , M + 1 , R ) ;
birleştirmek ( varış , ben , M , R ) ;
}
}
int ana ( )
{
int varış [ ] = { 12 , on bir , 13 , 5 , 6 , 7 } ;
int arr_size = boyutu ( varış ) / boyutu ( varış [ 0 ] ) ;
cout << 'Verilen dizi \N ' ;
için ( int Ben = 0 ; Ben < arr_size ; Ben ++ )
cout << varış [ Ben ] << ' ' ;
birleştirme Sıralaması ( varış , 0 , arr_size - 1 ) ;
cout << ' \N sıralanmış dizi \N ' ;
için ( int Ben = 0 ; Ben < arr_size ; Ben ++ )
cout << varış [ Ben ] << ' ' ;
geri dönmek 0 ;
}
Bu programda, birleştirme işlevi, sıralanacak diziyi temsil eden ve birleştirilmesi gereken alt dizinin indekslerini gösteren üç argüman arr, l ve r alır. İşlev önce birleştirilecek iki alt dizinin boyutlarını bulur, ardından bu alt dizilerin öğelerini depolamak için iki geçici alt dizi L ve R oluşturur. Daha sonra L ve R'deki öğeleri karşılaştırır ve bunları adlı orijinal dizide birleştirir. varış artan sırada.
Böl ve fethet tekniği, alt dizide yalnızca bir öğe kalana kadar diziyi yinelemeli olarak iki yarıya bölmek için birleştirmeSort işlevi tarafından kullanılır. Daha sonra iki alt diziyi sıralanmış bir alt dizide birleştirir. İşlev, tüm diziyi sıralamadığı sürece alt dizileri birleştirmeye devam eder.
Ana fonksiyonda 6 elemanlı bir dizi arr tanımlıyoruz ve bunu sıralamak için birleştirmeSort fonksiyonunu çağırıyoruz. Kodun sonunda, sıralanan dizi yazdırılır.
Yöntem 2 - Bir Temp Alt Dizisi Kullanma
Tek bir geçici alt dizi kullanan Yöntem 2'yi kullanan C++'da birleştirme sıralaması için örnek bir program:
#includead alanı std'sini kullanma ;
geçersiz birleştirmek ( int varış [ ] , int ben , int M , int R )
{
int Ben , J , k ;
int n1 = M - ben + 1 ;
int n2 = R - M ;
// Geçici alt diziler oluştur
int L [ n1 ] , R [ n2 ] ;
// Verileri alt dizilere kopyala
için ( Ben = 0 ; Ben < n1 ; Ben ++ )
L [ Ben ] = varış [ ben + Ben ] ;
için ( J = 0 ; J < n2 ; J ++ )
R [ J ] = varış [ M + 1 + J ] ;
// Geçici alt dizileri tekrar orijinal dizide birleştirin
Ben = 0 ;
J = 0 ;
k = ben ;
sırasında ( Ben < n1 && J < n2 ) {
eğer ( L [ Ben ] <= R [ J ] ) {
varış [ k ] = L [ Ben ] ;
Ben ++;
}
başka {
varış [ k ] = R [ J ] ;
J ++;
}
k ++;
}
// L[] öğesinin kalan öğelerini kopyalayın
sırasında ( Ben < n1 ) {
varış [ k ] = L [ Ben ] ;
Ben ++;
k ++;
}
// R[] öğesinin kalan öğelerini kopyalayın
sırasında ( J < n2 ) {
varış [ k ] = R [ J ] ;
J ++;
k ++;
}
}
geçersiz birleştirme Sıralaması ( int varış [ ] , int ben , int R )
{
eğer ( ben < R ) {
int M = ben + ( R - ben ) / 2 ;
// Sol ve sağ yarıları yinelemeli olarak sırala
birleştirme Sıralaması ( varış , ben , M ) ;
birleştirme Sıralaması ( varış , M + 1 , R ) ;
// Sıralanmış iki yarıyı birleştir
birleştirmek ( varış , ben , M , R ) ;
}
}
int ana ( )
{
int varış [ ] = { 12 , onbir , 13 , 5 , 6 , 7 } ;
int arr_size = boyutu ( varış ) / boyutu ( varış [ 0 ] ) ;
cout << 'Verilen dizi \N ' ;
için ( int Ben = 0 ; Ben < arr_size ; Ben ++ )
cout << varış [ Ben ] << ' ' ;
birleştirme Sıralaması ( varış , 0 , arr_size - 1 ) ;
cout << ' \N sıralanmış dizi \N ' ;
için ( int Ben = 0 ; Ben < arr_size ; Ben ++ )
cout << varış [ Ben ] << ' ' ;
geri dönmek 0 ;
}
Bu program öncekine benzer, ancak iki geçici alt dizi L ve R kullanmak yerine, tek bir geçici alt dizi kullanır. Birleştirme işlevi öncekiyle aynı şekilde çalışır, ancak verileri L ve R'ye kopyalamak yerine temp'e kopyalar. Daha sonra geçici dizi öğelerini tekrar birleştirir. varış orijinal dizi hangisidir.
MergeSort işlevi, geçici alt diziyi depolamak için L ve R yerine temp kullanması dışında öncekiyle aynıdır.
Ana fonksiyonda 6 elemanlı bir dizi arr tanımlıyoruz ve bunu sıralamak için birleştirmeSort fonksiyonunu çağırıyoruz. Kod yürütme, sıralanan diziyi ekrana yazdırarak sona erer.
Çözüm
Merge sort, dizi öğelerini sıralayan bir algoritmadır ve böl ve fethet tekniğini kullanır ve öğeler arasında karşılaştırmalar yapar. C++'daki birleştirme sıralaması, O(n log n)'lik bir zaman karmaşıklığına sahiptir ve özellikle büyük dizileri sıralamak için etkilidir. Birleştirilmiş alt dizileri depolamak için ek bellek gerektirse de kararlılığı onu sıralama için popüler bir seçim haline getirir.