Birleştirme Sıralama Algoritmasına Giriş

Birleştirme sıralama, "böl ve yönet" tekniğine dayalı bir sıralama algoritmasıdır. En verimli sıralama algoritmalarından biridir.

Bu makalede, birleştirme sıralama algoritmasının çalışması, birleştirme sıralama algoritması, zaman ve mekan karmaşıklığı ve bunun C++, Python gibi çeşitli programlama dillerinde uygulanması ve JavaScript.

Birleştirme Sıralama Algoritması Nasıl Çalışır?

Birleştirme sıralama, böl ve yönet ilkesine göre çalışır. Birleştirme sıralaması, her bir alt dizi tek bir öğeden oluşana kadar bir diziyi art arda iki eşit alt diziye böler. Son olarak, tüm bu alt diziler, sonuçtaki dizi sıralanacak şekilde birleştirilir.

Bu kavram bir örnek yardımıyla daha verimli bir şekilde açıklanabilir. Şu öğelere sahip sıralanmamış bir dizi düşünün: {16, 12, 15, 13, 19, 17, 11, 18}.

Burada, birleştirme sıralama algoritması diziyi iki yarıya böler, kendisini iki yarıya çağırır ve ardından sıralanmış iki yarıyı birleştirir.

Sıralama Algoritmasını Birleştir

Aşağıda birleştirme sıralamasının algoritması verilmiştir:

MergeSort (dizi[], leftIndex, rightIndex)
eğer leftIndex >= rightIndex
dönüş
Başka
Diziyi ikiye bölen orta dizini bulun: 
ortaIndex = leftIndex + (rightIndex-leftIndex)/2
İlk yarı için mergeSort()'u arayın: 
mergeSort'u çağırın (dizi, leftIndex, MiddleIndex)
İkinci yarı için mergeSort()'u arayın:
mergeSort'u çağırın (dizi, MiddleIndex+1, rightIndex)
2. ve 3. adımda sıralanan iki yarıyı birleştirin:
Çağrı birleştirme (dizi, leftIndex, MiddleIndex, rightIndex)

İlişkili: Özyineleme Nedir ve Nasıl Kullanılır?

Birleştirme Sıralama Algoritmasının Zaman ve Mekan Karmaşıklığı

Birleştirme sıralama algoritması, aşağıdaki yineleme ilişkisi biçiminde ifade edilebilir:

T(n) = 2T(n/2) + O(n)

Bu yineleme bağıntısını master teoremi veya yineleme ağacı yöntemini kullanarak çözdükten sonra çözümü O(n logn) olarak alırsınız. Böylece, birleştirme sıralama algoritmasının zaman karmaşıklığı, O(n oturum açma).

Birleştirme sıralamasının en iyi zaman karmaşıklığı: O(n oturum açma)

Birleştirme sıralamasının ortalama durum zaman karmaşıklığı: O(n oturum açma)

Birleştirme sıralamasının en kötü zaman karmaşıklığı: O(n oturum açma)

İlişkili: Big-O Notasyonu Nedir?

Yardımcı uzay karmaşıklığı birleştirme sıralama algoritmasının O(n) gibi n birleştirme sıralama uygulamasında yardımcı alan gereklidir.

Birleştirme Sıralama Algoritmasının C++ Uygulaması

Birleştirme sıralama algoritmasının C++ uygulaması aşağıdadır:

// C++ uygulaması
// sıralama algoritmasını birleştir
#Dahil etmek 
ad alanı std kullanarak;
// Bu işlev, arr[] öğesinin iki alt dizisini birleştirir
// Sol alt dizi: dizi[leftIndex..middleIndex]
// Sağ alt dizi: dizi[middleIndex+1..rightIndex]
void birleştirme (int dizi[], int leftIndex, int ortaIndex, int rightIndex)
{
int leftSubarraySize = ortaIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - ortaIndex;
// Geçici diziler oluştur
int L[leftSubarraySize], R[rightSubarraySize];
// Verileri L[] ve R[] geçici dizilerine kopyalama
için (int i = 0; i < leftSubarraySize; ben++)
L[i] = dizi[leftIndex + i];
for (int j = 0; j < rightSubarraySize; j++)
R[j] = dizi[middleIndex + 1 + j];
// Geçici dizileri tekrar arr[leftIndex..rightIndex] ile birleştir
// Sol alt dizinin ilk dizini
int ben = 0;
// Sağ alt dizinin ilk dizini
int j = 0;
// Birleştirilmiş alt dizinin ilk dizini
int k = solIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
if (L[i] <= R[j])
{
dizi[k] = L[i];
ben++;
}
Başka
{
dizi[k] = R[j];
j++;
}
k++;
}
// L[] içinde kalan bazı öğeler varsa
// diziye kopyala[]
while (i < leftSubarraySize)
{
dizi[k] = L[i];
ben++;
k++;
}
// R[] içinde kalan bazı öğeler varsa
// diziye kopyala[]
while (j < rightSubarraySize)
{
dizi[k] = R[j];
j++;
k++;
}
}
void mergeSort (int dizi[], int leftIndex, int rightIndex)
{
if (leftIndex >= rightIndex)
{
dönüş;
}
int ortaIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort (dizi, leftIndex, MiddleIndex);
mergeSort (dizi, ortaIndex+1, rightIndex);
birleştirme (dizi, leftIndex, MiddleIndex, rightIndex);
}
// Elemanları yazdırma işlevi
// dizinin
void printArray (int dizi[], int boyutu)
{
için (int i = 0; ben < boyut; ben++)
{
cout << dizi[i] << " ";
}
cout << endl;
}
// Sürücü kodu
int ana()
{
int dizi[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int boyut = sizeof (dizi) / sizeof (dizi[0]);
cout << "Sıralanmamış dizi:" << endl;
printArray (dizi, boyut);
mergeSort (dizi, 0, boyut - 1);
cout << "Sıralı dizi:" << endl;
printArray (dizi, boyut);
0 döndür;
}

Çıktı:

Sıralanmamış dizi:
16 12 15 13 19 17 11 18 
Sıralanmış dizi:
11 12 13 15 16 17 18 19

Birleştirme Sıralama Algoritmasının JavaScript Uygulaması

Aşağıda, birleştirme sıralama algoritmasının JavaScript uygulaması yer almaktadır:

// JavaScript uygulaması
// sıralama algoritmasını birleştir
// Bu işlev, arr[] öğesinin iki alt dizisini birleştirir
// Sol alt dizi: dizi[leftIndex..middleIndex]
// Sağ alt dizi: dizi[middleIndex+1..rightIndex]
işlev birleştirme (dizi, leftIndex, MiddleIndex, rightIndex) {
let leftSubarraySize = ortaIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - ortaIndex;
// Geçici diziler oluştur
var L = new Array (leftSubarraySize);
var R = new Array (rightSubarraySize);
// Verileri L[] ve R[] geçici dizilerine kopyalama
için (i = 0; benL[i] = dizi[leftIndex + i];
}
için (j = 0 olsun; jR[j] = dizi[middleIndex + 1 + j];
}
// Geçici dizileri tekrar arr[leftIndex..rightIndex] ile birleştir
// Sol alt dizinin ilk dizini
var i = 0;
// Sağ alt dizinin ilk dizini
var j = 0;
// Birleştirilmiş alt dizinin ilk dizini
var k = leftIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
if (L[i] <= R[j])
{
dizi[k] = L[i];
ben++;
}
Başka
{
dizi[k] = R[j];
j++;
}
k++;
}
// L[] içinde kalan bazı öğeler varsa
// diziye kopyala[]
while (i < leftSubarraySize)
{
dizi[k] = L[i];
ben++;
k++;
}
// R[] içinde kalan bazı öğeler varsa
// diziye kopyala[]
while (j < rightSubarraySize)
{
dizi[k] = R[j];
j++;
k++;
}
}
function mergeSort (dizi, leftIndex, rightIndex) {
if (leftIndex >= rightIndex) {
dönüş
}
var ortaIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (dizi, leftIndex, MiddleIndex);
mergeSort (dizi, ortaIndex+1, rightIndex);
birleştirme (dizi, leftIndex, MiddleIndex, rightIndex);
}
// Elemanları yazdırma işlevi
// dizinin
function printArray (dizi, boyut) {
için (i = 0; benbelge.write (dizi[i] + " ");
}
belge.yaz("
");
}
// Sürücü kodu:
var dizi = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = dizi.uzunluk;
document.write("Sıralanmamış dizi:
");
printArray (dizi, boyut);
mergeSort (dizi, 0, boyut - 1);
document.write("Sıralanmış dizi:
");
printArray (dizi, boyut);

Çıktı:

Sıralanmamış dizi:
16 12 15 13 19 17 11 18
Sıralanmış dizi:
11 12 13 15 16 17 18 19

İlişkili: Dinamik Programlama: Örnekler, Yaygın Sorunlar ve Çözümler

Birleştirme Sıralama Algoritmasının Python Uygulaması

Aşağıda, birleştirme sıralama algoritmasının Python uygulaması yer almaktadır:

# Python uygulaması
# birleştirme sıralama algoritması
def mergeSort (dizi):
len (dizi) > 1: ise
# Dizinin orta indeksini bulma
ortaIndex = len (dizi)//2
# Dizinin sol yarısı
L = dizi[:ortaIndex]
# Dizinin sağ yarısı
R = dizi[ortaIndex:]
# Dizinin ilk yarısını sıralama
birleştirmeSıralama (L)
# Dizinin ikinci yarısını sıralama
birleştirmeSıralama (R)
# Sol alt dizinin ilk dizini
ben = 0
# Sağ alt dizinin ilk dizini
j = 0
# Birleştirilmiş alt dizinin ilk dizini
k = 0
# Verileri L[] ve R[] geçici dizilerine kopyalayın
iken i < len (L) ve j < len (R):
L[i] < R[j] ise:
dizi[k] = L[i]
ben = ben + 1
Başka:
dizi[k] = R[j]
j = j + 1
k = k + 1
# Kalan bazı öğeler olup olmadığını kontrol etme
iken ben < len (L):
dizi[k] = L[i]
ben = ben + 1
k = k + 1
j < len (R):
dizi[k] = R[j]
j = j + 1
k = k + 1
# Öğeleri yazdırma işlevi
# dizinin
def printArray (dizi, boyut):
aralıktaki i için (boyut):
yazdır (dizi[i], bitiş=" ")
Yazdır()
# Sürücü kodu
dizi = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
boyut = uzunluk (arr)
print("Sıralanmamış dizi:")
printArray (dizi, boyut)
birleştirmeSıralama (dizi)
print("Sıralı dizi:")
printArray (dizi, boyut)

Çıktı:

Sıralanmamış dizi:
16 12 15 13 19 17 11 18
Sıralanmış dizi:
11 12 13 15 16 17 18 19

Diğer Sıralama Algoritmalarını Anlayın

Sıralama, programlamada en çok kullanılan algoritmalardan biridir. Hızlı sıralama, kabarcık sıralama, birleştirme sıralama, ekleme sıralama vb. gibi çeşitli sıralama algoritmalarını kullanarak farklı programlama dillerindeki öğeleri sıralayabilirsiniz.

En basit sıralama algoritması hakkında bilgi edinmek istiyorsanız, kabarcık sıralama en iyi seçimdir.

Kabarcık Sıralama Algoritmasına Giriş

Kabarcık Sıralama algoritması: dizileri sıralamaya mükemmel bir giriş.

Sonrakini Oku

Yazar hakkında