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.

bilgisayar wifi windows 10'a bağlanmayacak

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

---

---

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

Birleştirme sıralama, böl ve yönet ilkesine göre çalışır. Merge sort, bir diziyi her bir alt dizi tek bir öğeden oluşana kadar 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(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)

İlgili: Özyineleme Nedir ve Nasıl Kullanırsınız?

---

---

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)

İlgili: Big-O Notasyonu Nedir?

Yardımcı uzay karmaşıklığı birleştirme sıralama algoritmasının Açık) olarak 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++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}

// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
}

Çıktı:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
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 implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size);

Çıktı:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

İlgili: Dinamik Programlama: Örnekler, Genel 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 implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()

# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)


Çıktı:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
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.

Paylaş Paylaş Cıvıldamak E-posta Kabarcık Sıralama Algoritmasına Giriş

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

Sonrakini Oku İlgili konular

• Programlama
• JavaScript
• piton
• Kodlama Eğitimleri

Yazar hakkında Yuvraj Chandra(60 Makale Yayımlandı)

Yuvraj, Hindistan Delhi Üniversitesi'nde Bilgisayar Bilimleri lisans öğrencisidir. Full Stack Web Geliştirme konusunda tutkulu. Yazmadığı zamanlarda farklı teknolojilerin derinliğini keşfediyor.

Yuvraj Chandra'dan Daha Fazla

Haber bültenimize abone ol

Teknik ipuçları, incelemeler, ücretsiz e-kitaplar ve özel fırsatlar için bültenimize katılın!

Abone olmak için buraya tıklayın