Menü

Sıralamayı Java'da Birleştir - MergeSort Uygulama Programı

  • Ana
  • Diğer
  • Sıralamayı Java'da Birleştir - MergeSort Uygulama Programı

merge sort java program implement mergesort

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

Bu Eğitimde Java'da Birleştirme Sıralaması, MergeSort Algoritması, Sözde Kod, Birleştirme Sıralama Uygulaması, Yinelemeli ve Yinelemeli Birleştirme Sıralaması Örnekleri açıklanmaktadır:

Birleştirme sıralama tekniği 'Böl ve Yönet' stratejisi kullanır. Bu teknikte, sıralanacak veri seti sıralamak için daha küçük birimlere bölünür.

=> Kolay Java Eğitim Serisini Okuyun.

Sıralamayı Java

Ne öğreneceksin:

Sıralamayı Java'da Birleştir

Örneğin, bir dizi birleştirme sıralaması kullanılarak sıralanacaksa, dizi ortadaki elemanı etrafında iki alt diziye bölünür. Bu iki alt dizi, birim başına yalnızca 1 öğeye sahip olana kadar daha küçük birimlere bölünür.

Bölme yapıldıktan sonra, bu teknik, her bir öğeyi karşılaştırarak ve birleştirme sırasında bunları sıralayarak bu ayrı birimleri birleştirir. Bu şekilde, tüm dizi geri birleştirildiğinde, sıralı bir dizi elde ederiz.

Bu eğitimde, bu sıralama tekniğinin genel olarak algoritması ve sözde kodları dahil olmak üzere tüm ayrıntılarını ve tekniğin Java'da uygulanmasını tartışacağız.

Java'da MergeSort Algoritması

Aşağıdaki teknik için algoritmadır.

# 1) Bir dizi myArray of length N bildirir

#iki) N = 1 olup olmadığını kontrol edin, myArray zaten sıralanmıştır

# 3) N 1'den büyükse,

  • sol = 0, sağ = N-1 olarak ayarlayın
  • orta hesaplama = (sol + sağ) / 2
  • Çağrı alt rutini merge_sort (myArray, left, middle) => bu, dizinin ilk yarısını sıralar
  • Çağrı alt rutini merge_sort (myArray, middle + 1, right) => bu, dizinin ikinci yarısını sıralayacaktır
  • Yukarıdaki adımlarda sıralanan dizileri birleştirmek için alt rutin birleştirmeyi (myArray, sol, orta, sağ) çağırın.

# 4) çıkış

Algoritma adımlarında görüldüğü gibi dizi ortada ikiye bölünmüştür. Ardından dizinin sol yarısını ve ardından sağ yarısını özyinelemeli olarak sıralarız. Her iki yarıyı da ayrı ayrı sıraladığımızda, sıralı bir dizi elde etmek için birleştirilirler.

Sıralama Sözde Kodunu Birleştir

Mergesort tekniği için sözde kodu görelim. Daha önce tartışıldığı gibi, bu bir 'böl ve yönet' tekniği olduğundan, veri kümesini bölmek ve ardından sıralanan veri kümelerini birleştirmek için rutinleri sunacağız.

procedure mergesort( var intarray as array ) if ( n == 1 ) return intarray var lArray as array = intarray(0) ... intarray (n/2) var rArray as array = intarray (n/2+1) ... intarray (n) lArray = mergesort(lArray ) rArray = mergesort(rArray ) return merge(lArray, rArray ) end procedure procedure merge( var l_array as array, var r_array as array ) var result as array while (l_array and r_array have elements ) if (l_array (0) > r_array (0) ) add r_array (0) to the end of result remove r_array (0) from r_array else add l_array (0) to the end of result remove l_array (0) from l_array end if end while while (l_array has elements ) add l_array (0) to the end of result remove l_array (0) from l_array end while while (r_array has elements ) add r_array (0) to the end of result remove r_array (0) from r_array end while return result end procedure

Yukarıdaki sözde kodda, iki rutinimiz var, yani Mergesort ve birleştirme. Rutin Mergesort, girdi dizisini sıralaması kolay olan tek bir diziye böler. Ardından birleştirme rutini çağırır.

Birleştirme yordamı, tek tek alt dizileri birleştirir ve sonuçta sıralanmış bir dizi döndürür. Birleştirme sıralaması için algoritmayı ve sözde kodu gördükten sonra, şimdi bu tekniği bir örnek kullanarak gösterelim.

MergeSort İllüstrasyon

Bu teknik kullanılarak sıralanacak aşağıdaki diziyi düşünün.

Sıralama resmini birleştir

Şimdi Birleştirme sıralama algoritmasına göre, bu diziyi orta öğesinde iki alt diziye böleceğiz. Ardından, her dizide tek bir öğe elde edene kadar alt dizileri daha küçük dizilere ayırmaya devam edeceğiz.

Her bir alt dizi içinde yalnızca bir öğe olduğunda, öğeleri birleştiririz. Birleştirme sırasında öğeleri karşılaştırır ve birleştirilmiş dizide sıralı olmalarını sağlarız. Bu yüzden sıralanan birleştirilmiş bir dizi elde etmek için yolumuza devam ediyoruz.

İşlem aşağıda gösterilmiştir:

Sıralama sürecini birleştir

Yukarıdaki çizimde gösterildiği gibi, dizinin tekrar tekrar bölündüğünü ve daha sonra sıralı bir dizi elde etmek için birleştirildiğini görüyoruz. Bu kavramı akılda tutarak, Java programlama dilinde Mergesort uygulamasına geçelim.

Java'da Sıralama Uygulamasını Birleştirme

Tekniği Java'da iki yaklaşım kullanarak uygulayabiliriz.

Yinelemeli Birleştirme Sıralaması

Bu aşağıdan yukarıya bir yaklaşımdır. Bir elemanın alt dizilerinin her biri sıralanır ve iki elemanlı diziler oluşturmak için birleştirilir. Bu diziler daha sonra dört elemanlı diziler oluşturmak için birleştirilir ve bu böyle devam eder. Bu şekilde sıralanmış dizi yukarı doğru giderek oluşturulur.

Aşağıdaki Java örneği, yinelemeli Birleştirme Sıralama tekniğini gösterir.

import java.util.Arrays; class Main { // merge arrays : intArray(start...mid) and intArray(mid+1...end) public static void merge(int() intArray, int() temp, int start, int mid, int end) { int k = start, i = start, j = mid + 1; // traverse through elements of left and right arrays while (i <= mid && j <= end) { if (intArray(i) < intArray(j)) { temp(k++) = intArray(i++); } else { temp(k++) = intArray(j++); } } // Copy remaining elements while (i <= mid) { temp(k++) = intArray(i++); } // copy temp array back to the original array to reflect sorted order for (i = start; i <= end; i++) { intArray(i) = temp(i); } } // sorting intArray(low...high) using iterative approach public static void mergeSort(int() intArray) { int low = 0; int high = intArray.length - 1; // sort array intArray() using temporary array temp int() temp = Arrays.copyOf(intArray, intArray.length); // divide the array into blocks of size m // m = (1, 2, 4, 8, 16...) for (int m = 1; m <= high - low; m = 2*m) { for (int i = low; i < high; i += 2*m) { int start = i; int mid = i + m - 1; int end = Integer.min(i + 2 * m - 1, high); //call merge routine to merge the arrays merge(intArray, temp, start, mid, end); } } } public static void main(String() args) { //define array to be sorted int() intArray = { 10,23,-11,54,2,9,-10,45 }; //print the original array System.out.println('Original Array : ' + Arrays.toString(intArray)); //call mergeSort routine mergeSort(intArray); //print the sorted array System.out.println('Sorted Array : ' + Arrays.toString(intArray)); } }

Çıktı:

Orijinal Dizi: (10, 23, -11, 54, 2, 9, -10, 45)
Sıralanmış Dizi: (-11, -10, 2, 9, 10, 23, 45, 54)

Yinelemeli Birleştirme Sıralaması - Çıktı

Yinelemeli Birleştirme Sıralaması

Bu yukarıdan aşağıya bir yaklaşımdır. Bu yaklaşımda, sıralanacak dizi, her dizi yalnızca bir öğe içerene kadar daha küçük dizilere bölünür. Ardından sıralamanın uygulanması kolaylaşır.

Aşağıdaki Java kodu, Birleştirme sıralama tekniğinin özyinelemeli yaklaşımını uygular.

import java.util.Arrays; public class Main { public static void merge_Sort(int() numArray) { //return if array is empty if(numArray == null) { return; } if(numArray.length > 1) { int mid = numArray.length / 2; //find mid of the array // left half of the array int() left = new int(mid); for(int i = 0; i

Çıktı:

Orijinal Dizi: (10, 23, -11, 54, 2, 9, -10, 45)
Sıralanmış dizi: (- 11, -10, 2, 9, 10, 23, 45, 54)

Yinelemeli MergeSort - Çıktı

Sonraki bölümde, dizilerden geçelim ve bağlantılı liste ve dizi listesi veri yapılarını sıralamak için tekniği kullanalım.

Java'da Birleştirme Sıralamasını Kullanarak Bağlantılı Listeyi Sıralama

Birleştirme tekniği, bağlantılı listeleri sıralamak için en çok tercih edilen yöntemdir. Diğer sıralama teknikleri, çoğunlukla sıralı erişimi nedeniyle bağlantılı liste söz konusu olduğunda kötü performans gösterir.

Aşağıdaki program, bu tekniği kullanarak bağlantılı bir listeyi sıralar.

import java.util.*; // A singly linked list node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } }; class Main { //two sorted linked list are merged together to form one sorted linked list public static Node Sorted_MergeSort(Node node1, Node node2) { //return other list if one is null if (node1 == null) return node2; else if (node2 == null) return node1; Node result; // Pick either node1 or node2, and recur if (node1.data <= node2.data) { result = node1; result.next = Sorted_MergeSort(node1.next, node2); } else { result = node2; result.next = Sorted_MergeSort(node1, node2.next); } return result; } //splits the given linked list into two halves public static Node() FrontBackSplit(Node source) { // empty list if (source == null || source.next == null) { return new Node(){ source, null } ; } Node slow_ptr = source; Node fast_ptr = source.next; // Advance 'fast' two nodes, and advance 'slow' one node while (fast_ptr != null) { fast_ptr = fast_ptr.next; if (fast_ptr != null) { slow_ptr = slow_ptr.next; fast_ptr = fast_ptr.next; } } // split the list at slow_ptr just before mid Node() l_list = new Node(){ source, slow_ptr.next }; slow_ptr.next = null; return l_list; } // use Merge sort technique to sort the linked list public static Node Merge_Sort(Node head) { // list is empty or has single node if (head == null || head.next == null) { return head; } // Split head into 'left' and 'right' sublists Node() l_list = FrontBackSplit(head); Node left = l_list(0); Node right = l_list(1); // Recursively sort the sublists left = Merge_Sort(left); right = Merge_Sort(right); // merge the sorted sublists return Sorted_MergeSort(left, right); } // function to print nodes of given linked list public static void printNode(Node head) { Node node_ptr = head; while (node_ptr != null) { System.out.print(node_ptr.data + ' -> '); node_ptr = node_ptr.next; } System.out.println('null'); } public static void main(String() args) { // input linked list int() l_list = { 4,1,6,2,7,3,8 }; Node head = null; for (int key: l_list) { head = new Node(key, head); } //print the original list System.out.println('Original Linked List: '); printNode(head); // sort the list head = Merge_Sort(head); // print the sorted list System.out.println(' Sorted Linked List:'); printNode(head); } }

Çıktı:

Orijinal Bağlantılı Liste:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> boş
Sıralanmış Bağlantılı Liste:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> boş

java ile jar dosyası nasıl açılır

Çıktı - Bağlantılı listeyi sırala

Java'da Birleştirme Sıralamasını Kullanarak Dizi Listesini Sıralama

Diziler ve Bağlantılı listeler gibi, bu tekniği bir ArrayList'i sıralamak için de kullanabiliriz. ArrayList'i yinelemeli olarak bölmek ve ardından alt listeleri birleştirmek için benzer rutinler kullanacağız.

Aşağıdaki Java kodu, ArrayList için Merge sort tekniğini uygular.

import java.util.ArrayList; class Main { //splits arrayList into sub lists. public static void merge_Sort(ArrayList numList){ int mid; ArrayList left = new ArrayList<>(); ArrayList right = new ArrayList<>(); if (numList.size() > 1) { mid = numList.size() / 2; // left sublist for (int i = 0; i numList, ArrayList left, ArrayList right){ //temporary arraylist to build the merged list ArrayList temp = new ArrayList<>(); //initial indices for lists int numbersIndex = 0; int leftIndex = 0; int rightIndex = 0; //traverse left and righ lists for merging while (leftIndex = left.size()) { temp = right; tempIndex = rightIndex; } else { temp = left; tempIndex = leftIndex; } for (int i = tempIndex; i numList = new ArrayList<>(); int temp; //populate the ArrayList with random numbers for (int i = 1; i <= 9; i++) numList.add( (int)(Math.random() * 50 + 1) ); //print original ArrayList of random numbers System.out.println('Original ArrayList:'); for(int val: numList) System.out.print(val + ' '); //call merge_Sort routine merge_Sort(numList); //print the sorted ArrayList System.out.println(' Sorted ArrayList:'); for(int ele: numList) System.out.print(ele + ' '); System.out.println(); } }

Çıktı:

Orijinal Dizi Listesi:
17 40 36 7 6 23 35 2 38
Sıralanmış Dizi Listesi:
2 6 7 17 23 35 36 38 40

Çıktı - Dizi Listesini Sırala

Sıkça Sorulan Sorular

S # 1) Birleştirme sıralaması Özyineleme olmadan yapılabilir mi?

Cevap: Evet. 'Yinelemeli Birleştirme sıralaması' adı verilen, yinelemeli olmayan bir Birleştirme sıralaması gerçekleştirebiliriz. Bu, tek bir elemanla alt dizileri iki elemandan oluşan bir alt dizide birleştirerek başlayan aşağıdan yukarıya bir yaklaşımdır.

Daha sonra bu 2 elemanlı alt diziler 4 elemanlı alt diziler halinde birleştirilir ve yinelemeli yapılar kullanılarak bu şekilde devam edilir. Bu işlem sıralı bir diziye sahip olana kadar devam eder.

S # 2) Birleştirme sıralaması yerinde yapılabilir mi?

Cevap: Birleştirme sıralaması genellikle yerinde değildir. Ancak bazı akıllı uygulamalar kullanarak bunu yerinde yapabiliriz. Örneğin, iki öğenin değerini bir konumda depolayarak. Bu, modül ve bölme kullanılarak daha sonra çıkarılabilir.

S # 3) 3 yollu Birleştirme sıralaması nedir?

Cevap: Yukarıda gördüğümüz teknik, diziyi iki parçaya ayırdığımız 2 yönlü bir Birleştirme sıralamasıdır. Sonra diziyi sıralar ve birleştiririz.

3 yollu Birleştirme sıralamasında, diziyi 2 parçaya bölmek yerine 3 parçaya böler, sonra sıralar ve son olarak birleştiririz.

S # 4) Mergesort'un zaman karmaşıklığı nedir?

Cevap: Her durumda Birleştirme sıralamanın genel zaman karmaşıklığı O (nlogn) 'dur.

S # 5) Birleştirme sıralaması nerede kullanılır?

Cevap: Çoğunlukla bağlantılı listenin O (nlogn) zamanında sıralanmasında kullanılır. Ayrıca, sisteme sıralama öncesi veya sonrası yeni verilerin geldiği dağıtılmış senaryolarda da kullanılır. Bu aynı zamanda çeşitli veritabanı senaryolarında da kullanılır.

Sonuç

Birleştirme sıralaması kararlı bir sıralamadır ve önce veri kümesini tekrar tekrar alt kümelere bölerek ve ardından sıralı bir veri kümesi oluşturmak için bu alt kümeleri sıralayıp birleştirerek gerçekleştirilir. Veri kümesi, her veri kümesi önemsiz ve sıralanması kolay olana kadar bölünür.

Sıralama tekniğine yönelik yinelemeli ve yinelemeli yaklaşımları gördük. Mergesort kullanarak Bağlantılı Liste ve ArrayList veri yapısının sıralanmasını da tartıştık.

Gelecek eğitimlerimizde daha fazla sıralama tekniği tartışmasına devam edeceğiz. Bizi izlemeye devam edin!

=> Özel Java Eğitimi Öğretici Dizisi İçin Burayı Ziyaret Edin.

Önerilen Kaynaklar

^