Μενού

Συγχώνευση ταξινόμησης σε Java - Πρόγραμμα υλοποίησης MergeSort

  • Κύριος
  • Αλλα
  • Συγχώνευση ταξινόμησης σε Java - Πρόγραμμα υλοποίησης MergeSort

merge sort java program implement mergesort

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Αυτό το σεμινάριο εξηγεί τι είναι Merge Sort σε Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Παραδείγματα Iterative & Recursive MergeSort:

Η τεχνική συγχώνευσης ταξινόμησης χρησιμοποιεί μια στρατηγική 'Διαίρεση και κατάκτηση'. Σε αυτήν την τεχνική, το σύνολο δεδομένων που πρόκειται να ταξινομηθεί χωρίζεται σε μικρότερες μονάδες για να το ταξινομήσει.

=> Διαβάστε ολόκληρη τη σειρά Easy Java Training.

Συγχώνευση ταξινόμησης σε Java

Τι θα μάθετε:

Συγχώνευση ταξινόμησης σε Java

Για παράδειγμα, Αν ένας πίνακας πρόκειται να ταξινομηθεί χρησιμοποιώντας mergesort, τότε ο πίνακας χωρίζεται γύρω από το μεσαίο στοιχείο του σε δύο υπο-πίνακες. Αυτές οι δύο δευτερεύουσες συστοιχίες χωρίζονται περαιτέρω σε μικρότερες μονάδες έως ότου έχουμε μόνο 1 στοιχείο ανά μονάδα.

Μόλις γίνει η διαίρεση, αυτή η τεχνική συγχωνεύει αυτές τις μεμονωμένες μονάδες συγκρίνοντας κάθε στοιχείο και ταξινομώντας τους κατά τη συγχώνευση. Με αυτόν τον τρόπο μέχρι τη συγχώνευση ολόκληρου του πίνακα, έχουμε έναν ταξινομημένο πίνακα.

Σε αυτό το σεμινάριο, θα συζητήσουμε όλες τις λεπτομέρειες αυτής της τεχνικής ταξινόμησης γενικά, συμπεριλαμβανομένου του αλγορίθμου και των ψευδοκωδικών της, καθώς και την εφαρμογή της τεχνικής στην Java.

Αλγόριθμος MergeSort στην Ιάβα

Ακολουθεί ο αλγόριθμος της τεχνικής.

# 1) Δηλώστε έναν πίνακα myArray μήκους Ν

#δύο) Ελέγξτε αν N = 1, το myArray έχει ήδη ταξινομηθεί

# 3) Εάν το Ν είναι μεγαλύτερο από 1,

  • ορίστε αριστερά = 0, δεξιά = N-1
  • υπολογισμός μέσος = (αριστερά + δεξιά) / 2
  • Κλήση υπορουτίνας merge_sort (myArray, αριστερά, μεσαία) => ταξινομεί το πρώτο μισό του πίνακα
  • Κλήση υπορουτίνας merge_sort (myArray, middle + 1, right) => αυτό θα ταξινομήσει το δεύτερο μισό του πίνακα
  • Κλήση συγχώνευσης υπορουτίνας (myArray, αριστερά, μεσαία, δεξιά) για συγχώνευση συστοιχιών ταξινομημένων στα παραπάνω βήματα.

# 4) Εξοδος

Όπως φαίνεται στα βήματα του αλγορίθμου, ο πίνακας χωρίζεται σε δύο στη μέση. Στη συνέχεια ταξινομούμε αναδρομικά το αριστερό μισό του πίνακα και μετά το δεξί μισό. Μόλις ταξινομήσουμε ξεχωριστά και τα δύο μισά, συγχωνεύονται μαζί για να αποκτήσουν μια ταξινομημένη σειρά.

Συγχώνευση Ταξινόμηση Ψευδοκώδικα

Ας δούμε τον ψευδοκώδικα για την τεχνική Mergesort. Όπως έχει ήδη συζητηθεί, καθώς πρόκειται για μια τεχνική «διαίρεση και κατάκτηση», θα παρουσιάσουμε τις ρουτίνες διαχωρισμού του συνόλου δεδομένων και στη συνέχεια συγχώνευση των ταξινομημένων συνόλων δεδομένων.

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

Στον παραπάνω ψευδοκώδικα, έχουμε δύο ρουτίνες, δηλαδή Mergesort και συγχώνευση. Η ρουτίνα Mergesort χωρίζει τον πίνακα εισαγωγής σε έναν ξεχωριστό πίνακα που είναι αρκετά εύκολο να ταξινομηθεί. Στη συνέχεια καλεί τη ρουτίνα συγχώνευσης.

Η ρουτίνα συγχώνευσης συγχωνεύει τις μεμονωμένες δευτερεύουσες συστοιχίες και επιστρέφει έναν προκύπτοντα ταξινομημένο πίνακα. Έχοντας δει τον αλγόριθμο και τον ψευδοκώδικα για την ταξινόμηση Merge, ας απεικονίσουμε τώρα αυτήν την τεχνική χρησιμοποιώντας ένα παράδειγμα.

Εικονογράφηση MergeSort

Εξετάστε τον ακόλουθο πίνακα που θα ταξινομηθεί χρησιμοποιώντας αυτήν την τεχνική.

Συγχώνευση ταξινόμησης

Τώρα σύμφωνα με τον αλγόριθμο ταξινόμησης συγχώνευσης, θα χωρίσουμε αυτόν τον πίνακα στο μεσαίο στοιχείο του σε δύο υπο-πίνακες. Τότε θα συνεχίσουμε να χωρίζουμε τις υπο-συστοιχίες σε μικρότερους πίνακες έως ότου λάβουμε ένα μόνο στοιχείο σε κάθε πίνακα.

Μόλις κάθε υπο-πίνακας έχει μόνο ένα στοιχείο σε αυτό, συγχωνεύουμε τα στοιχεία. Κατά τη συγχώνευση, συγκρίνουμε τα στοιχεία και διασφαλίζουμε ότι είναι σωστά στον συγχωνευμένο πίνακα. Γι 'αυτό δουλεύουμε για να πάρουμε έναν συγχωνευμένο πίνακα που έχει ταξινομηθεί.

Η διαδικασία φαίνεται παρακάτω:

Διαδικασία συγχώνευσης

Όπως φαίνεται στην παραπάνω εικόνα, βλέπουμε ότι ο πίνακας χωρίζεται επανειλημμένα και στη συνέχεια συγχωνεύεται για να πάρει έναν ταξινομημένο πίνακα. Έχοντας υπόψη αυτήν την ιδέα, ας προχωρήσουμε στην εφαρμογή του Mergesort στη γλώσσα προγραμματισμού Java.

Συγχώνευση υλοποίησης ταξινόμησης σε Java

Μπορούμε να εφαρμόσουμε την τεχνική στην Java χρησιμοποιώντας δύο προσεγγίσεις.

Επαναληπτική ταξινόμηση συγχώνευσης

Αυτή είναι μια προσέγγιση από κάτω προς τα πάνω. Οι υπο-συστοιχίες ενός στοιχείου το καθένα ταξινομούνται και συγχωνεύονται για να σχηματίσουν πίνακες δύο στοιχείων. Αυτοί οι πίνακες συγχωνεύονται στη συνέχεια για να σχηματίσουν πίνακες τεσσάρων στοιχείων και ούτω καθεξής. Με αυτόν τον τρόπο η ταξινομημένη συστοιχία χτίζεται ανεβαίνοντας προς τα πάνω.

Το παρακάτω παράδειγμα Java δείχνει την επαναληπτική τεχνική Merge Sort.

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)); } }

Παραγωγή:

Original Array: (10, 23, -11, 54, 2, 9, -10, 45)
Ταξινομημένη σειρά: (-11, -10, 2, 9, 10, 23, 45, 54)

Επαναληπτική ταξινόμηση συγχώνευσης - Έξοδος

Αναδρομική ταξινόμηση συγχώνευσης

Αυτή είναι μια προσέγγιση από πάνω προς τα κάτω. Σε αυτήν την προσέγγιση, ο πίνακας προς ταξινόμηση χωρίζεται σε μικρότερους πίνακες έως ότου κάθε πίνακας περιέχει μόνο ένα στοιχείο. Στη συνέχεια, η ταξινόμηση γίνεται εύκολη στην εφαρμογή.

Ο ακόλουθος κώδικας Java εφαρμόζει την αναδρομική προσέγγιση της τεχνικής ταξινόμησης συγχώνευσης.

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

Παραγωγή:

Original Array: (10, 23, -11, 54, 2, 9, -10, 45)
Ταξινομημένη συστοιχία: (- 11, -10, 2, 9, 10, 23, 45, 54)

Αναδρομική MergeSort - Έξοδος

Στην επόμενη ενότητα, ας αλλάξουμε από συστοιχίες και χρησιμοποιήστε την τεχνική για να ταξινομήσετε τη δομή δεδομένων της λίστας και της λίστας.

Ταξινόμηση συνδεδεμένης λίστας χρησιμοποιώντας συγχώνευση Ταξινόμηση σε Java

Η τεχνική Mergesort είναι η πιο προτιμώμενη για την ταξινόμηση συνδεδεμένων λιστών. Άλλες τεχνικές ταξινόμησης έχουν κακή απόδοση όταν πρόκειται για τη συνδεδεμένη λίστα λόγω της κατά κύριο λόγο διαδοχικής πρόσβασης.

Το ακόλουθο πρόγραμμα ταξινομεί μια συνδεδεμένη λίστα χρησιμοποιώντας αυτήν την τεχνική.

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); } }

Παραγωγή:

Αρχική συνδεδεμένη λίστα:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> μηδέν
Ταξινομημένη συνδεδεμένη λίστα:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> μηδέν

πώς να ανοίξετε ένα αρχείο .air

Έξοδος - Ταξινόμηση συνδεδεμένης λίστας

Ταξινόμηση ArrayList χρησιμοποιώντας Συγχώνευση Ταξινόμηση σε Java

Όπως οι πίνακες συστοιχιών και οι συνδεδεμένες λίστες, μπορούμε επίσης να χρησιμοποιήσουμε αυτήν την τεχνική για την ταξινόμηση ενός ArrayList. Θα χρησιμοποιήσουμε παρόμοιες ρουτίνες για να διαιρέσουμε το ArrayList αναδρομικά και στη συνέχεια να συγχωνεύσουμε τις λίστες.

Ο παρακάτω κώδικας Java εφαρμόζει την τεχνική ταξινόμησης συγχώνευσης για το ArrayList.

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(); } }

Παραγωγή:

Original ArrayList:
17 40 36 7 6 23 35 2 38
Ταξινόμηση ArrayList:
2 6 7 17 23 35 36 38 40

Έξοδος - Ταξινόμηση ArrayList

Συχνές Ερωτήσεις

Q # 1) Μπορεί η συγχώνευση να γίνει χωρίς αναδρομή;

Απάντηση: Ναί. Μπορούμε να εκτελέσουμε ένα μη αναδρομικό είδος συγχώνευσης που ονομάζεται «επαναλαμβανόμενο είδος συγχώνευσης». Αυτή είναι μια προσέγγιση από κάτω προς τα πάνω που ξεκινά με τη συγχώνευση υπο-συστοιχιών με ένα μόνο στοιχείο σε μια υπο-σειρά δύο στοιχείων.

Στη συνέχεια, αυτές οι δευτερεύουσες συστοιχίες 2 στοιχείων συγχωνεύονται σε δευτερεύουσες συστοιχίες 4 στοιχείων και ούτω καθεξής χρησιμοποιώντας επαναλαμβανόμενες κατασκευές. Αυτή η διαδικασία συνεχίζεται έως ότου έχουμε έναν ταξινομημένο πίνακα.

Q # 2) Μπορεί να γίνει η ταξινόμηση της συγχώνευσης στη θέση της;

Απάντηση: Η ταξινόμηση συγχώνευσης γενικά δεν είναι στη θέση της. Αλλά μπορούμε να το κάνουμε στη θέση του χρησιμοποιώντας κάποια έξυπνη εφαρμογή. Για παράδειγμα, αποθηκεύοντας την τιμή δύο στοιχείων σε μία θέση. Αυτό μπορεί να εξαχθεί στη συνέχεια χρησιμοποιώντας συντελεστή και διαίρεση.

Q # 3) Τι είναι μια ταξινόμηση 3 τρόπων;

Απάντηση: Η τεχνική που έχουμε δει παραπάνω είναι ένα είδος αμφίδρομης συγχώνευσης όπου χωρίζουμε τον πίνακα για ταξινόμηση σε δύο μέρη. Στη συνέχεια ταξινομούμε και συγχωνεύουμε τον πίνακα.

Σε μια ταξινόμηση 3 κατευθύνσεων, αντί να χωρίσουμε τον πίνακα σε 2 μέρη, τον χωρίσαμε σε 3 μέρη, στη συνέχεια ταξινομήσαμε και τελικά τον συγχωνεύσουμε.

Q # 4) Ποια είναι η χρονική πολυπλοκότητα του Mergesort;

Απάντηση: Η συνολική χρονική πολυπλοκότητα του είδους Merge σε όλες τις περιπτώσεις είναι O (nlogn).

Q # 5) Πού χρησιμοποιείται το είδος συγχώνευσης;

Απάντηση: Χρησιμοποιείται ως επί το πλείστον στην ταξινόμηση της συνδεδεμένης λίστας στο χρόνο O (nlogn). Χρησιμοποιείται επίσης σε κατανεμημένα σενάρια όπου νέα δεδομένα έρχονται στο σύστημα πριν ή μετά την ταξινόμηση. Αυτό χρησιμοποιείται επίσης σε διάφορα σενάρια βάσης δεδομένων.

συμπέρασμα

Η ταξινόμηση συγχώνευσης είναι μια σταθερή ταξινόμηση και πραγματοποιείται διαχωρίζοντας πρώτα το σύνολο δεδομένων επανειλημμένα σε υποσύνολα και στη συνέχεια ταξινομώντας και συγχωνεύοντας αυτά τα υποσύνολα για να σχηματίσουν ένα ταξινομημένο σύνολο δεδομένων. Το σύνολο δεδομένων χωρίζεται έως ότου κάθε σύνολο δεδομένων είναι ασήμαντο και εύκολο στην ταξινόμηση.

Έχουμε δει τις επαναληπτικές και επαναληπτικές προσεγγίσεις στην τεχνική διαλογής. Συζητήσαμε επίσης την ταξινόμηση της δομής δεδομένων Linked List και ArrayList χρησιμοποιώντας το Mergesort.

Θα συνεχίσουμε με τη συζήτηση περισσότερων τεχνικών ταξινόμησης στα επερχόμενα σεμινάρια μας. Μείνετε συντονισμένοι!

=> Επισκεφτείτε εδώ για την αποκλειστική σειρά εκπαιδευτικών εκμάθησης Java.

Συνιστώμενη ανάγνωση

^