introduction sorting techniques c
Elenco delle varie tecniche di ordinamento in C ++.
L'ordinamento è una tecnica implementata per disporre i dati in un ordine specifico. L'ordinamento è necessario per garantire che i dati che utilizziamo siano in un ordine particolare in modo da poter recuperare facilmente le informazioni richieste dalla pila di dati.
Se i dati sono arruffati e non ordinati, quando vogliamo una particolare informazione, dovremo cercarli uno per uno ogni volta per recuperare i dati.
=> Leggi la serie di formazione Easy C ++.
Pertanto è sempre consigliabile mantenere i nostri dati organizzati in un ordine specifico in modo che il recupero delle informazioni, così come altre operazioni eseguite sui dati, possa essere eseguito in modo semplice ed efficiente.
Archiviamo i dati sotto forma di record. Ogni record è costituito da uno o più campi. Quando ogni record ha un valore univoco di un campo particolare, lo chiamiamo campo chiave. Per esempio, in una classe, Roll No può essere un campo unico o chiave.
come convertire i video di YouTube in file wav
Possiamo ordinare i dati su un particolare campo chiave e poi disporli in ordine crescente / crescente o in ordine decrescente / decrescente.
Allo stesso modo, in un dizionario telefonico, ogni record è costituito dal nome di una persona, indirizzo e numero di telefono. In questo, il numero di telefono è un campo unico o chiave. Possiamo ordinare i dati del dizionario in questo campo del telefono. In alternativa, possiamo anche ordinare i dati in modo numerico o alfanumerico.
Quando possiamo regolare i dati da ordinare nella memoria principale stessa senza bisogno di un'altra memoria ausiliaria, lo chiamiamo come Ordinamento interno .
D'altra parte, quando abbiamo bisogno di memoria ausiliaria per memorizzare dati intermedi durante l'ordinamento, chiamiamo la tecnica come Ordinamento esterno .
In questo tutorial impareremo in dettaglio le varie tecniche di ordinamento in C ++.
Cosa imparerai:
Tecniche di ordinamento in C ++
C ++ supporta varie tecniche di ordinamento elencate di seguito.
Bubble Sort
Bubble sort è la tecnica più semplice in cui confrontiamo ogni elemento con il suo elemento adiacente e scambiamo gli elementi se non sono in ordine. In questo modo alla fine di ogni iterazione (chiamata passaggio), l'elemento più pesante viene ribollito alla fine dell'elenco.
Di seguito è riportato un esempio di Bubble Sort.
Matrice da ordinare:
Come visto sopra, poiché si tratta di un piccolo array ed è stato quasi ordinato, siamo riusciti a ottenere un array completamente ordinato in pochi passaggi.
Implementiamo la tecnica Bubble Sort in C ++.
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < Produzione:
Elenco di input ...
10 2 0 43 12
Elenco elementi ordinati ...
0 2 10 12 43
Come si vede dall'output, nella tecnica del bubble sort, ad ogni passaggio l'elemento più pesante viene ribollito fino alla fine della matrice, ordinando in tal modo la matrice completamente.
Ordina selezione
È una tecnica semplice ma facile da implementare in cui troviamo l'elemento più piccolo nell'elenco e lo mettiamo al suo posto. Ad ogni passaggio, l'elemento più piccolo successivo viene selezionato e posizionato nella posizione corretta.
Prendiamo lo stesso array dell'esempio precedente ed eseguiamo Selection Sort per ordinare questo array.
Come mostrato nell'illustrazione sopra, per il numero N di elementi prendiamo N-1 passaggi per ordinare completamente l'array. Alla fine di ogni passaggio, l'elemento più piccolo dell'array viene posizionato nella posizione corretta nell'array ordinato.
Successivamente, implementiamo l'ordinamento della selezione utilizzando C ++.
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< Produzione:
Elenco di input degli elementi da ordinare
12 45 8 15 33
L'elenco degli elementi ordinati è
8 12 15 33 45
Nell'ordinamento della selezione, ad ogni passaggio, l'elemento più piccolo dell'array viene posizionato nella posizione corretta. Quindi, alla fine del processo di ordinamento, otteniamo un array completamente ordinato.
Ordinamento di inserzione
L'ordinamento per inserzione è una tecnica in cui partiamo dal secondo elemento della lista. Confrontiamo il secondo elemento con il suo precedente (1st) e posizionarlo nella sua posizione corretta. Nel passaggio successivo, per ogni elemento, lo confrontiamo con tutti i suoi elementi precedenti e inseriamo quell'elemento nella sua posizione corretta.
Le tre tecniche di ordinamento precedenti sono semplici e facili da implementare. Queste tecniche funzionano bene quando la dimensione dell'elenco è inferiore. Man mano che l'elenco cresce di dimensioni, queste tecniche non vengono eseguite in modo efficiente.
La tecnica sarà chiara comprendendo la seguente illustrazione.
L'array da ordinare è il seguente:
Ora per ogni passaggio, confrontiamo l'elemento corrente con tutti i suoi elementi precedenti. Quindi, nel primo passaggio, iniziamo con il secondo elemento.
Quindi abbiamo bisogno di N numero di passaggi per ordinare completamente un array contenente N numero di elementi.
Implementiamo la tecnica di ordinamento per inserzione utilizzando C ++.
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < Produzione:
L'elenco di input è
12 4 3 1 15
L'elenco ordinato è
1 3 4 12 15
L'output precedente mostra l'array ordinato completo utilizzando l'ordinamento per inserimento.
Ordinamento rapido
Quicksort è l'algoritmo più efficiente che può essere utilizzato per ordinare i dati. Questa tecnica utilizza la strategia 'divide et impera' in cui il problema è suddiviso in diversi sottoproblemi e dopo aver risolto singolarmente questi sottoproblemi vengono uniti insieme per un elenco ordinato completo.
In quicksort, prima dividiamo l'elenco attorno all'elemento pivot e quindi posizioniamo gli altri elementi nelle loro posizioni corrette in base all'elemento pivot.
Come mostrato nell'illustrazione sopra, nella tecnica Quicksort dividiamo la matrice attorno a un elemento pivot in modo tale che tutti gli elementi minori del pivot siano alla sua sinistra e quelli maggiori del pivot siano alla sua destra. Quindi prendiamo questi due array in modo indipendente e li ordiniamo e poi li uniamo o li conquistiamo per ottenere un array ordinato risultante.
La chiave per Quicksort è la selezione dell'elemento pivot. Può essere il primo, l'ultimo o l'elemento centrale dell'array. Il primo passo dopo aver selezionato l'elemento pivot è posizionare il pivot nella sua posizione corretta in modo da poter dividere l'array in modo appropriato.
Implementiamo la tecnica di ordinamento rapido utilizzando C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Produzione:
Matrice di input
12 23 3 43 51
Array ordinato con Quicksort
3 12 23 43 51
Nell'implementazione quicksort sopra, abbiamo una routine di partizione che viene utilizzata per partizionare l'array di input attorno a un elemento pivot che è l'ultimo elemento dell'array. Quindi chiamiamo ricorsivamente la routine quicksort per ordinare individualmente i sotto-array come mostrato nell'illustrazione.
Unisci ordinamento
Questa è un'altra tecnica che utilizza la strategia 'Divide and conquer'. In questa tecnica, dividiamo prima l'elenco in metà uguali. Quindi eseguiamo la tecnica di ordinamento di unione su questi elenchi in modo indipendente in modo che entrambi gli elenchi siano ordinati. Infine, uniamo entrambi gli elenchi per ottenere un elenco ordinato completo.
L'ordinamento unito e l'ordinamento rapido sono più veloci della maggior parte delle altre tecniche di ordinamento. Le loro prestazioni rimangono intatte anche quando l'elenco diventa più grande.
Vediamo un'illustrazione della tecnica Merge Sort.
Nell'illustrazione sopra, vediamo che la tecnica di merge sort divide ripetutamente l'array originale in sottoarray finché non c'è un solo elemento in ogni sottoarray. Fatto ciò, i sottoarray vengono quindi ordinati in modo indipendente e uniti insieme per formare un array ordinato completo.
Successivamente, implementiamo Merge Sort usando il linguaggio 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< Produzione:
Immettere il numero di elementi da ordinare: 5
Immettere 5 elementi da ordinare: 10 21 47 3 59
Matrice ordinata
3 10 21 47 59
Shell Sort
L'ordinamento della shell è un'estensione della tecnica di ordinamento per inserzione. Nell'ordinamento per inserzione, ci occupiamo solo dell'elemento successivo mentre, nell'ordinamento della shell, forniamo un incremento o un intervallo utilizzando il quale creiamo elenchi più piccoli dall'elenco padre. Gli elementi nelle sottoliste non devono essere contigui, piuttosto sono solitamente separati da 'gap_value'.
L'ordinamento della shell è più veloce dell'ordinamento per inserzione e richiede meno spostamenti di quello dell'ordinamento per inserzione.
Se forniamo un intervallo di, avremo i seguenti sottoelenchi con ogni elemento che è a 3 elementi di distanza.
Quindi selezioniamo queste tre sottoliste.
L'array sopra che abbiamo ottenuto dopo aver unito i sotto-array ordinati è quasi ordinato. Ora possiamo eseguire l'ordinamento per inserimento su questo array per ordinare l'intero array.
Quindi vediamo che una volta che abbiamo diviso l'array in sottoliste usando l'incremento appropriato e poi le uniamo insieme otteniamo la lista quasi ordinata. La tecnica di ordinamento per inserimento in questo elenco può essere eseguita e la matrice viene ordinata in meno spostamenti rispetto all'ordinamento per inserimento originale.
Di seguito è riportata l'implementazione dell'ordinamento della shell in C ++.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Produzione:
Matrice da ordinare:
45 23 53 43 18
Array dopo l'ordinamento della shell:
18 23 43 45 53
L'ordinamento della shell agisce quindi come un enorme miglioramento rispetto all'ordinamento per inserzione e non richiede nemmeno la metà del numero di passaggi per ordinare l'array.
Ordinamento mucchio
Heapsort è una tecnica in cui la struttura dei dati dell'heap (min-heap o max-heap) viene utilizzata per ordinare l'elenco. Per prima cosa costruiamo un heap dall'elenco non ordinato e utilizziamo anche l'heap per ordinare l'array.
Heapsort è efficiente ma non così veloce o l'ordinamento Merge.
Come mostrato nell'illustrazione sopra, per prima cosa costruiamo un heap massimo dagli elementi dell'array da ordinare. Quindi attraversiamo l'heap e scambiamo l'ultimo e il primo elemento. In questo momento l'ultimo elemento è già ordinato. Quindi costruiamo di nuovo un heap massimo dagli elementi rimanenti.
Ancora una volta attraversa l'heap e scambia il primo e l'ultimo elemento e aggiungi l'ultimo elemento all'elenco ordinato. Questo processo viene continuato finché non è rimasto un solo elemento nell'heap che diventa il primo elemento dell'elenco ordinato.
Implementiamo ora l'ordinamento degli heap utilizzando C ++.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Produzione:
Matrice di input
4 17 3 12 9
Matrice ordinata
3 4 9 12 17
Finora abbiamo discusso brevemente tutte le principali tecniche di ordinamento con un'illustrazione. Impareremo ciascuna di queste tecniche in dettaglio nei nostri tutorial successivi insieme a vari esempi per comprendere ciascuna tecnica.
Conclusione
L'ordinamento è necessario per mantenere i dati ordinati e nell'ordine corretto. L'accesso non ordinato e trasandato potrebbe richiedere più tempo e quindi potrebbe influire sulle prestazioni dell'intero programma. Pertanto, per qualsiasi operazione relativa ai dati come l'accesso, la ricerca, la manipolazione, ecc., È necessario ordinare i dati.
Esistono molte tecniche di ordinamento impiegate nella programmazione. Ciascuna tecnica può essere impiegata a seconda della struttura dati che stiamo utilizzando o del tempo impiegato dall'algoritmo per ordinare i dati o dello spazio di memoria utilizzato dall'algoritmo per ordinare i dati. La tecnica che stiamo usando dipende anche dalla struttura dei dati che stiamo ordinando.
Le tecniche di ordinamento ci consentono di ordinare le nostre strutture di dati in un ordine specifico e di disporre gli elementi in ordine crescente o decrescente. Abbiamo visto le tecniche di ordinamento come Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort e Heap sort. Bubble sort e Selection sort sono più semplici e facili da implementare.
Nelle nostre successive esercitazioni vedremo in dettaglio ciascuna delle tecniche di ordinamento sopra menzionate.
=> Fare clic qui per il corso C ++ gratuito.
Lettura consigliata
- Ordinamento heap in C ++ con esempi
- Unisci ordinamento in C ++ con esempi
- Ordinamento di inserzione in C ++ con esempi
- JMeter Video 1: Introduzione, download e installazione di JMeter
- Introduzione al linguaggio di programmazione Java - Tutorial video
- Introduzione a Python e processo di installazione
- Comando di ordinamento Unix con sintassi, opzioni ed esempi
- Metodo MongoDB Sort () con esempi
