Bu eğitimde, birleştirme sıralaması hakkında bilgi edineceksiniz. Ayrıca, C, C ++, Java ve Python birleştirme sıralaması için çalışma örnekleri bulacaksınız.
Birleştirme Sıralama, Böl ve Fethet Algoritması ilkesine dayanan en popüler sıralama algoritmalarından biridir.
Burada bir problem, birden fazla alt probleme bölünmüştür. Her alt problem ayrı ayrı çözülür. Son olarak, nihai çözümü oluşturmak için alt problemler birleştirilir.
Sıralama örneği Birleştirme
Böl ve Fethet Stratejisi
Böl ve Yönet tekniğini kullanarak bir problemi alt problemlere böleriz. Her alt problemin çözümü hazır olduğunda, ana problemi çözmek için alt problemlerin sonuçlarını 'birleştiririz'.
Bir A dizisini sıralamak zorunda olduğumuzu varsayalım. Bir alt problem, bu dizinin p dizininden başlayıp A (p… r) olarak belirtilen r dizininde biten bir alt bölümünü sıralamak olabilir.
Bölme
Eğer q, p ve r arasındaki yarı nokta ise, o zaman A (p… r) alt dizisini A (p… q) ve A (q + 1, r) olmak üzere iki diziye bölebiliriz.
Fethetme
Fethetme adımında, hem A (p… q) hem de A (q + 1, r) alt dizilerini sınıflandırmaya çalışıyoruz. Henüz temel duruma ulaşmadıysak, bu iki alt diziyi yeniden böler ve onları sıralamaya çalışırız.
Birleştir
Fethetme adımı temel adıma ulaştığında ve A (p… r) dizisi için iki sıralı alt dizi A (p… q) ve A (q + 1, r) elde ettiğimizde, sonuçları sıralı bir dizi A oluşturarak birleştiririz ( p… r) iki sıralı alt dizi A (p… q) ve A (q + 1, r).
MergeSort Algoritması
MergeSort işlevi, diziyi, 1 boyutunda bir alt dizide MergeSort gerçekleştirmeye çalıştığımız bir aşamaya ulaşana kadar art arda iki yarıya böler, yani p == r.
Bundan sonra, birleştirme işlevi devreye girer ve sıralanmış dizileri, tüm dizi birleştirilene kadar daha büyük diziler halinde birleştirir.
MergeSort (A, p, r): eğer p> r return q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r )
Bir dizinin tamamını sıralamak için aramamız gerekir MergeSort(A, 0, length(A)-1).
Aşağıdaki resimde gösterildiği gibi, birleştirme sıralama algoritması, 1 öğeli dizinin temel durumuna ulaşana kadar diziyi yinelemeli olarak yarıya böler. Bundan sonra, birleştirme işlevi sıralı alt dizileri alır ve tüm diziyi aşamalı olarak sıralamak için birleştirir.
Sıralamayı iş başında birleştir
Birleştirme Birleştirme Sıralama Adım
Her özyinelemeli algoritma, bir temel duruma ve sonuçları temel durumlardan birleştirme yeteneğine bağlıdır. Birleştirme sıralaması farklı değildir. Birleştirme sıralama algoritmasının en önemli kısmı, tahmin etmişsinizdir, birleştirme adımıdır.
Birleştirme adımı, büyük bir sıralı liste (dizi) oluşturmak için iki sıralı listeyi (dizileri) birleştirmenin basit probleminin çözümüdür.
Algoritma, iki dizinin her biri için bir tane ve son sıralanmış dizinin geçerli dizinini korumak için bir tane olmak üzere üç işaretçi tutar.
Dizilerden herhangi birinin sonuna ulaştık mı? Hayır: Her iki dizinin geçerli öğelerini karşılaştırın Daha küçük öğeyi sıralı diziye kopyala Daha küçük öğe içeren öğenin işaretçisini taşı Evet: Boş olmayan dizinin kalan tüm öğelerini kopyala
Birleştirme adımı
Birleştirme Algoritması Kodunu Yazma
Yukarıda tarif ettiğimiz birleştirme adımı ile birleştirme sıralaması için kullandığımız arasındaki göze çarpan bir fark, birleştirme işlevini yalnızca ardışık alt dizilerde gerçekleştirmemizdir.
Bu nedenle, yalnızca diziye, ilk konuma, ilk alt dizinin son dizinine (ikinci alt dizinin ilk dizinini hesaplayabiliriz) ve ikinci alt dizinin son dizinine ihtiyacımız var.
Görevimiz, sıralı bir dizi A (p… r) oluşturmak için iki alt dizi A (p… q) ve A (q + 1… r) birleştirmektir. Yani fonksiyonun girdileri A, p, q ve r'dir.
Birleştirme işlevi şu şekilde çalışır:
- Alt dizilerin
L ← A(p… q)ve M ← A (q + 1… r) kopyalarını oluşturun . - Üç işaretçi i, j ve k oluşturun
- i 1'den başlayarak mevcut L indeksini korur
- j 1'den başlayarak mevcut M indeksini korur
- k, p'den başlayarak A (p… q) 'nun geçerli indeksini korur.
- L veya M'nin sonuna ulaşana kadar, L ve M'den daha büyük olanı seçin ve onları A'da doğru konuma yerleştirin (p… q)
- L veya M'de elemanlar tükendiğinde, kalan elemanları al ve A (p… q)
Kodda bu şöyle görünür:
// Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Adım Adım Açıklanan Birleştirme () Fonksiyonu
Bu işlevde çok şey oluyor, bu yüzden bunun nasıl çalışacağını görmek için bir örnek alalım.
Her zamanki gibi, bir resim bin kelime konuşuyor.
Dizinin iki ardışık alt dizisini birleştirme
A dizisi (0… 5) iki sıralı alt dizi A (0… 3) ve A (4… 5) içerir. Birleştirme fonksiyonunun iki diziyi nasıl birleştireceğini görelim.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
Adım 1: Sıralanacak alt dizilerin yinelenen kopyalarını oluşturun
// Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9) 
Birleştirme için alt dizilerin kopyalarını oluşturun
Adım 2: Alt dizilerin ve ana dizinin geçerli dizinini koruyun
int i, j, k; i = 0; j = 0; k = p; 
Alt dizi ve ana dizi kopyalarının endekslerini koruyun
Adım 3: L veya M'nin sonuna ulaşana kadar, L ve M öğeleri arasından daha büyük olanı seçin ve bunları A'da doğru konuma yerleştirin (p… r)
while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) 
Birinin sonuna ulaşana kadar sıralanmış alt dizilerin tek tek öğelerinin karşılaştırılması
Adım 4: L veya M'de elemanlar tükendiğinde, kalan elemanları toplayın ve A (p… r) koyun.
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
Kalan elemanları ilk diziden ana alt diziye kopyala
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
İkinci dizinin kalan elemanlarını ana alt diziye kopyala
M'nin boyutu L'den büyük olsaydı bu adım gerekli olurdu.
Birleştirme işlevinin sonunda, alt dizi A (p… r) sıralanır.
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array)
// Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
// Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
// Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )
Sıralama Karmaşıklığını Birleştirme
Zaman Karmaşıklığı
En İyi Durum Karmaşıklığı: O (n * log n)
En Kötü Durum Karmaşıklığı: O (n * log n)
Ortalama Durum Karmaşıklığı: O (n * log n)
Uzay Karmaşıklığı
Birleştirme sıralamanın uzay karmaşıklığı O (n) 'dir.
Sıralama Uygulamalarını Birleştir
- Ters çevirme sayımı sorunu
- Dış sıralama
- E-ticaret uygulamaları
