Come implementare l'ordinamento di unione in C ++ con esempi

Cos'è il merge sort? L'ordinamento di unione è un algoritmo di ordinamento basato sul confronto che appartiene alla categoria divide et impera. L'ordinamento di unione viene utilizzato per ordinare un array in base alla strategia divide et impera che verrà trattata brevemente in questo post insieme ad altri concetti come il suo algoritmo con un esempio. Esamineremo anche la complessità temporale dell'ordinamento di unione in C ++

I seguenti suggerimenti saranno trattati in questo articolo,

• Algoritmo di divisione e conquista
• Comprensione dell'algoritmo di ordinamento unione con un esempio
• Pseudocodice per Merge Sort
• Programma in C ++ per Merge Sort
• La complessità temporale per Merge Sort

Andando avanti con questo articolo su Merge Sort in C ++

Algoritmo di divisione e conquista

Se hai già familiarità con il funzionamento di quicksort, potresti essere a conoscenza della strategia divide et impera. Divide and Conquer prevede tre passaggi principali. Per comprendere questi passaggi, consideriamo un array Hello [] con indice iniziale 'a' e indice finale 'n', quindi possiamo scrivere il nostro array nel modo seguente Hello [a & hellip..n]

Dividi - La prima mossa o il primo passo del divide et impera è dividere il problema dato in sotto-problemi o sotto-parti. Il problema qui è che i problemi secondari dovrebbero essere simili al problema originale e di dimensioni inferiori. Nel nostro caso divideremo il nostro array in 2 metà [a & hellip.m] [m + 1 & hellip..n] m si trova nel mezzo dell'indice a e n

Conquista- Una volta che abbiamo finito di dividere il nostro problema in sotto-problemi. Risolviamo questi sottoproblemi in modo ricorsivo.

Combina- In questa fase, combiniamo tutte le soluzioni dei nostri sotto-problemi in modo appropriato. In altre parole, combiniamo 2 diversi array ordinati per formare un array ordinato. Lì abbiamo il nostro array ordinato.

Andando avanti con questo articolo su Merge Sort in C ++

Comprendere l'algoritmo di ordinamento di unione con un esempio

A questo punto, sappiamo quale approccio verrà utilizzato dall'ordinamento di unione. Quindi, consideriamo un esempio e passiamo attraverso ogni passaggio da Hello [] unsorted a un array ordinato.
Esempio: Ciao [10, 3, 7, 1, 15, 14, 9, 22]

override vs sovraccarico c ++

Nell'immagine sopra, abbiamo considerato un array non ordinato e utilizzato l'ordinamento di unione per ottenere un array ordinato. Ora, esaminiamo ogni passaggio e comprendiamo l'intero algoritmo

1. Innanzitutto, abbiamo considerato un array Hello [10, 3, 7, 1, 15, 14, 9, 22] in questo array ci sono 8 elementi in totale

2. Come abbiamo visto in precedenza, l'ordinamento di unione utilizza l'approccio divide et impera per ordinare gli elementi. Abbiamo trovato m che si trova al centro del nostro array e abbiamo diviso il nostro array dal centro dove m = (a - n) / 2 'a' è l'indice dell'elemento più a sinistra en è l'indice dell'elemento più a destra del nostro array .

3. Dopo la prima divisione, abbiamo 2 parti composte da 4 elementi ciascuna. Diamo un'occhiata alla prima metà [10, 3, 7, 1].

4. Dividiamo [10, 3, 7, 1] in 2 parti [10, 3] e [7, 1]. Dopodiché li dividiamo ulteriormente in [10], [3], [7], [1]. Non è possibile un'ulteriore divisione in quanto non possiamo calcolare m. una lista contenente un singolo elemento è sempre considerata ordinata.

5. Come avviene la fusione? Scopriamolo. Il primo [10] e [3] vengono confrontati e uniti in ordine crescente [3, 10] nello stesso modo in cui otteniamo [1, 7]

qual è il metodo in javascript

6. Successivamente, confrontiamo [3, 10] e [1, 7]. Una volta confrontati, li uniamo in ordine crescente e otteniamo [1, 3, 7, 10].

7. [15, 14, 9, 2] è anche diviso e combinato in modo simile per formare [9, 14, 15, 22].

8. Nell'ultimo passaggio confrontiamo e combiniamo [15, 14, 9, 2] [9, 14, 15, 22] per darci il nostro array ordinatocioè [1, 3, 7, 9, 10, 14, 15, 22].

funzione membro statico c ++

Andando avanti con questo articolo su Merge Sort in C ++

Pseudocodice per Merge Sort

Inizia se lasciato
La funzione mergeSort () chiama se stessa ricorsivamente per dividere il nostro array fino a quando non diventa un singolo elemento e la funzione merge () viene utilizzata per unire gli array ordinati.
  Andando avanti con questo articolo su Merge Sort in C ++
 Unisci il programma di ordinamento in C ++ 
#include #include #include utilizzando lo spazio dei nomi std void merge (int a [], int Firstindex, int m, int Lastindex) // unisce i sotto-array che vengono creati durante la divisione void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Ciao [taglia], ho cout<<'Enter the elements of the array one by one:n' for(i=0 i>Ciao [i] mergeSort (Hello, 0, size - 1) cout<<'The Sorted List isn' for(i=0 i
 Produzione- 
Andando avanti con questo articolo su Merge Sort in C ++
 Complessità temporale 
La complessità temporale è un aspetto importante da considerare quando parliamo di algoritmi. Si ritiene che l'ordinamento di fusione abbia una grande complessità temporale rispetto ad altri algoritmi di ordinamento.
Tempo di esecuzione nel caso peggiore: O (n log n) 
Tempo di esecuzione del caso migliore- O (n log n) 
Tempo di esecuzione medio- O (n log n)
Con questo, arriviamo alla fine di questo articolo Merge Sort in C ++. Se desideri saperne di più, dai un'occhiata al   da Edureka, una società di apprendimento online affidabile. Il corso di formazione e certificazione Java J2EE e SOA di Edureka è progettato per formarti sia sui concetti di base che avanzati su Java insieme a vari framework Java come Hibernate e Spring.
 Hai domande per noi? Per favore, menzionalo nella sezione commenti di questo blog e ti risponderemo il prima possibile.