Meniu

Merge Sortează în C ++ cu exemple

merge sort c with examples

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

C ++ Merge Sort Technique.

Algoritmul de sortare Merge folosește „ diviza și cuceri ”Strategie în care împărțim problema în subprobleme și rezolvăm aceste subprobleme în mod individual.

Aceste subprobleme sunt apoi combinate sau combinate pentru a forma o soluție unificată.

=> Citiți aici seria populară de formare C ++.

Merge Sort

Ce veți învăța:

unde să transmiteți anime gratuit

Prezentare generală

Sortarea Merge se realizează urmând pașii următori:

# 1) Lista de sortat este împărțită în două tablouri de lungime egală prin împărțirea listei pe elementul de mijloc. Dacă numărul de elemente din listă este fie 0, fie 1, atunci lista este considerată sortată.

#Două) Fiecare sublistă este sortată individual utilizând sortarea merge recursiv.

# 3) Sublistele sortate sunt apoi combinate sau combinate pentru a forma o listă completă sortată.

Algoritm general

Pseudo-codul general pentru tehnica de sortare a îmbinării este dat mai jos.

Declarați o matrice Arr de lungime N
Dacă N = 1, Arr este deja sortat
Dacă N> 1,
Stânga = 0, dreapta = N-1
Găsiți mijlocul (stânga + dreapta) / 2
Apelați merge_sort (Arr, stânga, mijloc) => sortați prima jumătate recursiv
Apelați merge_sort (Arr, mijloc + 1, dreapta) => sortați recursiv a doua jumătate
Apelați îmbinare (Arr, stânga, mijloc, dreapta) pentru a îmbina matricile sortate în pașii de mai sus.
Ieșire

Așa cum se arată în pseudo-codul de mai sus, în algoritmul de sortare a îmbinării împărțim matricea în jumătate și sortăm fiecare jumătate folosind sortarea de îmbinare recursiv. Odată ce sub-tablourile sunt sortate individual, cele două sub-tablouri sunt îmbinate împreună pentru a forma un tablou sortat complet.

Pseudo cod pentru sortare Merge

Urmează pseudocodul pentru tehnica de sortare a îmbinării. În primul rând, avem o procedură de fuzionare pentru a împărți matricea în jumătăți recursiv. Apoi avem o rutină de îmbinare care va îmbina matricile mai mici sortate pentru a obține o matrice sortată completă.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 end if end while while ( a has elements ) add a(0) to the end of c remove a(0) from a end while while ( b has elements ) add b(0) to the end of c remove b(0) from b end while return c end procedure

Să ilustrăm acum tehnica de sortare a îmbinării cu un exemplu.

Ilustrare

fuzionează sortare Ilustrație

Ilustrația de mai sus poate fi afișată într-o formă tabelară de mai jos:

TreceListă nesortatădivideListă sortată
unu{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
Două{12,23,2,43}
{51,35,19,4}		{12,23} {2,43}
{51.35} {19.4}		{}
3{12,23} {2,43}
{51.35} {19.4}		{12,23} {2,43}
{35.51} {4.19}		{12,23} {2,43}
{35.51} {4.19}
4{12,23} {2,43}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Așa cum se arată în reprezentarea de mai sus, mai întâi matricea este împărțită în două sub-matrice de lungime 4. Fiecare sub-matrice este împărțită în continuare în încă două sub matrice de lungime 2. Fiecare sub-matrice este apoi împărțită în continuare într-o sub-matrice a câte un element fiecare. Întregul proces este procesul „Divide”.

Odată ce am împărțit matricea în sub-tablouri ale unui singur element fiecare, acum trebuie să fuzionăm aceste tablouri în ordine sortată.

Așa cum se arată în ilustrația de mai sus, considerăm fiecare subarray al unui singur element și mai întâi combinăm elementele pentru a forma sub-tablouri a două elemente în ordine sortată. Apoi, subarrayurile sortate de lungimea doi sunt sortate și combinate pentru a forma două sub-tablouri de lungime patru fiecare. Apoi combinăm aceste două sub-tablouri pentru a forma un tablou sortat complet.

Sortare iterativă de îmbinare

Algoritmul sau tehnica sortării de îmbinare pe care am văzut-o mai sus utilizează recursivitatea. Este, de asemenea, cunoscut sub numele de „ sortare recursivă de îmbinare ”.

Știm că funcțiile recursive utilizează funcția stivă de apeluri pentru a stoca starea intermediară a funcției de apelare. De asemenea, stochează alte informații de contabilitate pentru parametri etc. și prezintă cheltuieli generale în ceea ce privește stocarea înregistrării de activare a apelării funcției, precum și reluarea execuției.

Toate aceste cheltuieli generale pot fi eliminate dacă folosim funcții iterative în loc de recursive. Algoritmul de sortare de fuzionare de mai sus poate fi convertit cu ușurință în pași iterativi folosind bucle și luarea deciziilor.

La fel ca sortarea recursivă a îmbinării, sortarea iterativă a îmbinării are, de asemenea, o complexitate O (nlogn), prin urmare, în funcție de performanță, acestea se comportă la egalitate. Pur și simplu suntem capabili să coborâm cheltuielile generale.

În acest tutorial, ne-am concentrat pe sortarea recursivă a fuzionării și apoi vom implementa sortarea fuzionării recursive utilizând limbaje C ++ și Java.

Mai jos este prezentată o implementare a tehnicii de sortare a îmbinării folosind C ++.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Ieșire:

Introduceți numărul de elemente de sortat: 10

Introduceți 10 elemente de sortat: 101 10 2 43 12 54 34 64 89 76

Matricea sortată

2 10 12 34 43 54 64 76 89 101

În acest program, am definit două funcții, merge_sort și merge . În funcția merge_sort, împărțim matricea în două matrice egale și apelăm la funcția de îmbinare pe fiecare dintre aceste matrice secundare. În funcția de îmbinare, facem sortarea efectivă pe aceste subreglaje și apoi le îmbinăm într-o matrice sortată completă.

Apoi, implementăm tehnica Merge Sort în limbaj Java.

class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i

Ieșire:

Matrice de intrare

101 10 2 43 12 54 34 64 89 76

Matrice sortate folosind sortare merge

2 10 12 34 43 54 64 76 89 101

Și în implementarea Java, folosim aceeași logică pe care am folosit-o în implementarea C ++.

Merge sort este un mod eficient de sortare a listelor și este utilizat în principal pentru sortarea listelor legate. Deoarece folosește o abordare de împărțire și cucerire, tehnica de sortare a fuziunilor este la fel de eficientă pentru matrici mai mici, precum și pentru matrice mai mari.

Analiza complexității algoritmului sortare Merge

Știm că, pentru a efectua sortarea folosind sortarea merge, împărțim mai întâi matricea în două jumătăți egale. Aceasta este reprezentată de „log n”, care este o funcție logaritmică, iar numărul de pași parcurși este cel mult log (n + 1).

Apoi pentru a găsi elementul de mijloc al matricei avem nevoie de un singur pas, adică O (1).

Apoi, pentru a îmbina sub-tablourile într-o matrice de n elemente, vom lua O (n) cantitatea de timp de rulare.

Astfel, timpul total pentru efectuarea sortării de îmbinare va fi n (log n + 1), ceea ce ne oferă complexitatea în timp a lui O (n * logn).

Complexitatea timpului cel mai prostO (n * jurnal n)
Complexitatea în cel mai bun cazO (n * jurnal n)
Complexitatea timpului mediuO (n * jurnal n)
Complexitatea spațiuluiPe)

Complexitatea timpului pentru sortarea fuzionării este aceeași în toate cele trei cazuri (cel mai rău, cel mai bun și mediu), deoarece împarte întotdeauna matricea în sub-tablouri și apoi fuzionează sub-tablourile luând timp liniar.

Sortarea Merge ocupă întotdeauna o cantitate egală de spațiu ca matricele nesortate. Prin urmare, atunci când lista care urmează a fi sortată este o matrice, sortarea fuzionării nu ar trebui utilizată pentru tablouri foarte mari. Cu toate acestea, sortarea prin îmbinare poate fi utilizată mai eficient pentru sortarea listelor legate.

Concluzie

Sortarea Merge folosește strategia „împărțiți și cuceriți” care împarte matricea sau lista în numeroase sub matrici și le sortează individual și apoi se îmbină într-o matrice sortată completă.

Sortarea Merge este mai rapidă decât alte metode de sortare și funcționează eficient și pentru tablouri mai mici și mai mari.

Vom explora mai multe despre Sortare rapidă în viitorul nostru tutorial!

=> Fii atent la Ghidul de instruire pentru începători C ++ aici.

Lectură recomandată

^