Programul Merge Sort în Java: Diferența dintre Merge Sort și Quicksort

Introducere în programul Merge Sort în JAVA

După cum sugerează și numele, programul de sortare prin îmbinare în JAVA este un algoritm de sortare. A fost conceptualizat clasic ca algoritmul de împărțire și cuceri în JAVA. Programul de sortare de îmbinare din Java funcționează prin descompunerea recursiv a unui tablou de intrare în două sau mai multe dintre subproblemele sale constitutive până când acestea sunt suficient de simple pentru a fi rezolvate direct.

Subproblemele constitutive pot fi fie similare, fie oarecum legate de problema părintelui. Soluțiile individuale pentru fiecare sub-problemă sunt apoi combinate pentru a obține soluția problemei părinte inițiale.

Cum funcționează programul Merge Sort în Java?

După cum s-a repetat mai devreme, programul de sortare de îmbinare în JAVA este un algoritm de împărțire și cucerire. Este o sortare stabilă, ceea ce înseamnă că elementele matricei își mențin pozițiile inițiale unul față de celălalt pe tot parcursul procesului de sortare.

• Divide: În acest pas, o matrice de intrare este împărțită în cele două jumătăți constitutive ale sale. Acest pas se repetă continuu pentru toate jumătățile de matrice rezultate până când nu mai există jumătate de matrice de împărțit.
• Conquer: în acest pas, matricele divizate sunt sortate și îmbinate de jos în sus pentru a ajunge la matricea sortată finală.

Diferența dintre programul Quicksort și Merge Sort în Java

Deși este similar din punct de vedere funcțional, trebuie să se pună un accent pertinent pe diferența fundamentală dintre quicksort și mergesort în JAVA.

• Mecanism : Quicksort este un algoritm de sortare intern, în loc, în timp ce mergesort este un algoritm de sortare extern, în afara locului. În sortarea rapidă, elementele sunt sortate pe baza unui element cheie cunoscut sub numele de pivot. Pivotul este, în general, valoarea de mijloc într-o matrice de intrare. Elementele cu o valoare mai mică decât pivotul sunt împinse în partea stângă a pivotului, în timp ce elementele cu o valoare mai mare în partea dreaptă a pivotului. Aici, partea stângă este denumită partiția din stânga, iar partea dreaptă este denumită partiția din dreapta. Dimpotrivă, mergesort împarte o matrice în două sub-matrice (n/2) în mod repetat până când rămâne un singur element. Apoi combină sub-matricele pentru a forma matricea sortată.
• Aplicație: În timp ce quicksort este potrivit pentru matrice mici, mergesort funcționează cu orice matrice, indiferent de dimensiunea acesteia.
• Viteză : în cazul sortării rapide, cu cât setul de date este mai mic, cu atât algoritmul este mai rapid. Mergesort, pe de altă parte, funcționează la o viteză constantă pentru toate seturile de date.
• Necesarul de spațiu și utilizarea memoriei: așa cum am menționat mai devreme, mergesort este un algoritm de sortare extern, în afara locului. Complexitatea sa spațială este O (n). Prin urmare, necesită o stocare suplimentară de (O (n)) pentru a sorta matricea auxiliară.

Citiți și: Tipuri de literale în Java cu exemple

Analiza timp-complexitate a programului de sortare fuzionare în JAVA

Programul de sortare de îmbinare în JAVA are o complexitate de timp de O (n*log n). Potrivit Binary Search, ori de câte ori un număr este împărțit în jumătate în fiecare pas, acesta poate fi reprezentat prin funcția logaritmică „log n”. Numărul de pași (cel mult) poate fi reprezentat prin log n +1. Mijlocul oricărei sub-matrice este O (1).

Astfel, pentru a fuziona sub-matrice, va fi necesar un timp de rulare de O (n). Prin urmare, timpul total pentru programul de sortare de îmbinare în JAVA devine n (log n +1). Aceasta înseamnă o complexitate de timp de O (n*log n) în toate cele trei cazuri (cel mai rău, mediu și cel mai bun), deoarece sortarea prin îmbinare necesită întotdeauna timp liniar pentru a îmbina două jumătăți.

Învață cursuri de software online de la cele mai bune universități din lume. Câștigă programe Executive PG, programe avansate de certificat sau programe de master pentru a-ți accelera cariera.

Rezumând

Așa cum datele sortate pentru oameni sunt solide din punct de vedere logic și mai ușor de înțeles, matricele sortate sunt mai ușor de gestionat pentru computere. Acesta este locul în care programul de sortare de îmbinare în JAVA se dovedește avantajos. Este un algoritm de sortare eficient, cu scop general, bazat pe comparație.

Dacă sunteți interesat să aflați mai multe despre Java, dezvoltarea de software full-stack, consultați programul Executive PG de la upGrad și IIIT-B în dezvoltarea de software full-stack, care este conceput pentru profesioniști care lucrează și oferă peste 500 de ore de formare riguroasă, 9+ proiecte și sarcini, statutul de absolvenți IIIT-B, proiecte practice practice și asistență pentru locuri de muncă cu firme de top.