Мени

Сортирање стапања у Јави - програм за примену МергеСорт-а

  • Главни
  • Остало
  • Сортирање стапања у Јави - програм за примену МергеСорт-а

merge sort java program implement mergesort

Испробајте Наш Инструмент За Елиминисање Проблема

Овај водич објашњава шта је Сортирање стапања у Јави, МергеСорт алгоритам, Псеудо код, Имплементација сортирања стапања, Примери итеративног и рекурзивног МергеСорт:

Техника сортирања спајањем користи стратегију „Подели и победи“. У овој техници, скуп података који се сортира подељен је на мање јединице да би се сортирао.

=> Прочитајте серију Еаси Јава Траининг.

Споји сортирање у Јави

Шта ћете научити:

Споји сортирање у Јави

На пример, ако се низ треба сортирати помоћу мергесорт, онда је низ подељен око свог средњег елемента у два подниза. Ова два подниза су даље подељена на мање јединице док не добијемо само 1 елемент по јединици.

Једном када се подела изврши, ова техника спаја ове појединачне јединице упоређивањем сваког елемента и сортирањем приликом спајања. На тај начин док се читав низ споји назад добијамо сортирани низ.

У овом упутству ћемо размотрити све детаље ове технике сортирања, укључујући њен алгоритам и псеудо кодове, као и примену технике у Јави.

МергеСорт Алгоритам у Јави

Следи алгоритам за технику.

# 1) Прогласите низ миАрраи дужине Н

#два) Проверите да ли је Н = 1, миАрраи је већ сортиран

# 3) Ако је Н већи од 1,

  • постављено лево = 0, десно = Н-1
  • израчунати средину = (лево + десно) / 2
  • Позовите потпрограм мерге_сорт (миАрраи, лефт, миддле) => ово сортира прву половину низа
  • Позовите потпрограм мерге_сорт (миАрраи, миддле + 1, ригхт) => ово ће сортирати другу половину низа
  • Позовите спајање потпрограма (миАрраи, лево, средње, десно) за спајање низова сортираних у горњим корацима.

# 4) Излаз

Као што се види у корацима алгоритма, низ је у средини подељен на два дела. Затим рекурзивно сортирамо леву половину низа, а затим десну половину. Једном када појединачно сортирамо обе половине, оне се спајају заједно да би се добио сортирани низ.

Споји псеудо код сортирања

Погледајмо псеудо-код Мергесорт технике. Као што је већ речено, јер је ово техника „подели и освоји“, представићемо рутине за поделу скупа података, а затим обједињавање сортираних скупова података.

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

У горњем псеудо-коду имамо две рутине, тј. Мергесорт и мерге. Рутина Мергесорт дели улазни низ на појединачни низ који је довољно једноставан за сортирање. Затим позива рутину спајања.

Рутина спајања спаја појединачне поднизове и враћа резултујући сортирани низ. Након што смо видели алгоритам и псеудо-код за сортирање спајања, илуструјмо сада ову технику на примеру.

МергеСорт Иллустратион

Размотрите следећи низ који ће се сортирати помоћу ове технике.

Спајање илустрације сортирања

Сада ћемо према алгоритму сортирања Мерге поделити овај низ у његовом средњем елементу на два подниза. Затим ћемо наставити подјелу под-низова на мање низове док не добијемо по један елемент у сваком низу.

Једном када свака под-низ садржи само један елемент, ми спајамо елементе. Приликом спајања упоређујемо елементе и осигуравамо да су у реду у обједињеном низу. Дакле, трудимо се да добијемо обједињени низ који је сортиран.

Процес је приказан у наставку:

Поступак сортирања спајања

Као што је приказано на горњој илустрацији, видимо да се низ више пута дели и затим спаја да би се добио сортирани низ. Имајући у виду овај концепт, пређимо на примену Мергесорта у програмском језику Јава.

Спајање сортирања имплементације у Јави

Можемо применити технику у Јави користећи два приступа.

Итеративно сортирање спајања

Ово је приступ одоздо према горе. Под-низови по једног елемента сортирају се и спајају да би формирали низове од два елемента. Ови низови се затим спајају да би формирали низове од четири елемента и тако даље. На овај начин се сортирани низ гради надоле.

Доњи пример Јава приказује итеративну технику сортирања стапања.

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

Излаз:

Оригинални низ: (10, 23, -11, 54, 2, 9, -10, 45)
Сортирани низ: (-11, -10, 2, 9, 10, 23, 45, 54)

Итеративно сортирање спајања - излаз

Рекурзивно сортирање

Ово је приступ од врха према доле. У овом приступу, низ који се сортира разлаже се на мање низове док сваки низ не садржи само један елемент. Тада сортирање постаје једноставно за спровођење.

Следећи Јава код примењује рекурзивни приступ технике сортирања Мерге.

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

Излаз:

Оригинални низ: (10, 23, -11, 54, 2, 9, -10, 45)
Сортирани низ: (- 11, -10, 2, 9, 10, 23, 45, 54)

Рекурзивни МергеСорт - излаз

У следећем одељку пређимо са низова и употребимо технику за сортирање повезаних структура података и листе података.

Сортирање повезане листе помоћу спајања Сортирање у Јави

Техника спајања је најпожељнија за сортирање повезаних листа. Остале технике сортирања имају лош учинак када је у питању повезана листа због углавном секвенцијалног приступа.

Следећи програм сортира повезану листу помоћу ове технике.

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 -> нула

скл питања и одговори за свеже

Излаз - Сортирај повезану листу

Сортирај АрраиЛист помоћу сортирања стапања у Јави

Попут низова и повезаних листа, и ову технику можемо користити за сортирање АрраиЛист-а. Користићемо сличне рутине да рекурзивно поделимо АрраиЛист, а затим спојимо подлисте.

Доле наведени Јава код примењује технику сортирања Мерге за АрраиЛист.

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

Излаз:

Оригинал АрраиЛист:
17 40 36 7 6 23 35 2 38
Сортед АрраиЛист:
2 6 7 17 23 35 36 38 40

Излаз - сортирање листе низова

Често постављана питања

П # 1) Може ли се сортирање обједињавања извршити без рекурзије?

Одговор: Да. Можемо извршити нерекурзивно сортирање спајања под називом „итеративно сортирање спајања“. Ово је приступ одоздо према горе који започиње спајањем под-низова са једним елементом у под-низ од два елемента.

Тада се ови под-низови од 2 елемента обједињују у под-низове од 4 елемента и тако даље користећи итеративне конструкције. Овај процес се наставља док не добијемо сортирани низ.

К # 2) Може ли се сортирање спајањем извршити на месту?

Одговор: Сортирање обједињавања углавном није на месту. Али то можемо постићи користећи паметну имплементацију. На пример, чувањем вредности два елемента на једној позицији. Ово се касније може извући помоћу модула и дељења.

К # 3) Шта је тросмерно сортирање?

Одговор: Техника коју смо видели горе је двосмерна сортирање спајањем при чему поделимо низ да би био сортиран на два дела. Затим сортирамо и спојимо низ.

У 3-смерном сортирању Мерге, уместо да делимо низ на 2 дела, ми га делимо на 3 дела, затим сортирамо и коначно спојимо.

К # 4) Која је временска сложеност Мергесорта?

Одговор: Укупна временска сложеност сортирања Мерге у свим случајевима је О (нлогн).

К # 5) Где се користи сортирање Мерге?

Одговор: Најчешће се користи за сортирање повезане листе у О (нлогн) времену. Такође се користи у дистрибуираним сценаријима у којима нови подаци долазе у систем пре или после сортирања. Ово се такође користи у различитим сценаријима база података.

Закључак

Сортирање обједињавањем је стабилно разврставање и изводи се тако што се скуп података подељује прво узастопно у подскупове, а затим сортира и спаја ове подскупове како би се формирао сортирани скуп података. Скуп података се дели док сваки скуп података није тривијалан и једноставан за сортирање.

Видели смо рекурзивни и итеративни приступ техници сортирања. Такође смо разговарали о сортирању повезане структуре података и АрраиЛист структуре помоћу Мергесорта.

Наставићемо са расправом о више техника сортирања у нашим предстојећим водичима. Будите у току!

=> Посетите овде за ексклузивну серију лекција за Јава тренинг.

Препоручено читање

^