Ordinamento è una delle funzioni più basilari e utili applicate ai dati. Ha lo scopo di organizzare i dati in un modo particolare, che può aumentare o diminuire in base ai requisiti. Esiste una funzione incorporata in C ++ STL con il nome di 'sort ()' che ci consente di eseguire facilmente l'algoritmo di ordinamento. In questo articolo esploreremo la funzione di ordinamento in C ++,
I seguenti puntatori verranno trattati in questo articolo:
- Funzione Sort ()
- Esempio: ordinare i dati in ordine crescente
- Esempio: per ordinare i dati in ordine decrescente
- Partial_sort
Andando avanti con questo articolo sulla funzione di ordinamento in C ++
Ordinare ( ) funzione
È una funzione incorporata del file di intestazione dell'algoritmo che viene utilizzato per ordinare i contenitori come un array, i vettori in un ordine specificato. Internamente questa funzione è implementata come Quick-sort
Quicksort è un algoritmo divide et impera. Quicksort divide innanzitutto un ampio elenco di elementi in due sottoelenchi più piccoli: gli elementi inferiori e gli elementi superiori. Quicksort quindi ordina ricorsivamente i sotto-elenchi.
I passi sono come segue:
1. Scegli un elemento casuale (di solito l'ultimo elemento), chiamato pivot, dall'elenco.
2. Riordina l'elenco in modo tale che tutti gli elementi con valori inferiori al pivot vengano prima del pivot, mentre tutti gli elementi con valori maggiori del pivot vengono dopo di esso e i valori uguali possono andare in qualsiasi modo questo processo viene chiamato operazione di partizione.
3. Ordinare ricorsivamente la sottoelenco degli elementi minori e la sottoelenco degli elementi maggiori, selezionare nuovamente un pivot nella sottoelenco e dividerle.
Il caso base della ricorsione sono elenchi di dimensione zero o uno, che non hanno mai bisogno di essere ordinati e quindi combinandoli ordiniamo la nostra lista.
Quicksort è più veloce in pratica rispetto ad altri algoritmi O (n log n) come Insertion Sort o Bubble sort. Quicksort può essere implementato con un algoritmo di partizionamento sul posto, il che significa che l'intero ordinamento può essere eseguito con solo O (log n) spazio aggiuntivo. Quicksort non è un tipo stabile.
La sua complessità è la seguente:
Caso migliore - O (n log n)
Peggiore caso - O (n ^ 2)
Caso medio - O (n log n)
Sintassi:
ordina (primo, ultimo)
Qui,
primo - è l'indice (puntatore) del primo elemento dell'intervallo da ordinare.
last - è l'indice (puntatore) dell'ultimo elemento dell'intervallo da ordinare.
Ad esempio, vogliamo ordinare gli elementi di un array 'arr' da 1 a 10 posizioni, useremo sort (arr, arr + 10) e ordinerà 10 elementi in ordine crescente.
Valore di ritorno
Nessuna
Complessità
pro e contro dell'hacking
La media della complessità di un ordinamento è N * log2 (N), dove N = ultimo - primo.
Intervallo di dati
Gli oggetti nell'intervallo [primo, ultimo) vengono modificati.
Eccezioni
Gli overload con un parametro di modello denominato ExecutionPolicy segnalano gli errori come segue:
Se l'algoritmo non riesce ad allocare la memoria, std :: bad_alloc viene lanciato come eccezione.
Se l'esecuzione di una funzione invocata come parte dell'algoritmo genera un'eccezione std :: terminate.
Andando avanti con questo articolo sulla funzione di ordinamento in C ++
Esempio: per ordinare i dati in ordine crescente:
#include using namespace std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' fornisce la dimensione dell'array totale, ovvero la dimensione di ogni carattere * no. di caratteri // in modo da ottenere no. di caratteri // dividiamo la dimensione di (array) con la dimensione di un carattere qualsiasi dell'array // qui è array [0] sort (array, array + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Produzione :
Spiegazione
Dall'esempio precedente, vediamo che la funzione sort () ordina di default un array in ordine crescente.
Andando avanti con questo articolo sulla funzione di ordinamento in C ++
Esempio: per ordinare i dati in ordine decrescente:
Per ordinare i dati dell'array in ordine decrescente dobbiamo introdurre un terzo parametro che viene utilizzato per specificare l'ordine in cui gli elementi devono essere ordinati. Possiamo usare la funzione 'maggiore ()' per ordinare i dati in ordine decrescente.
#include using namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) sort (array, array + n, maggiore ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Produzione:
tutorial passo passo ssis di sql server integration services
Exp l una nazione
Qui la funzione sort () fa un confronto in un modo che mette un elemento maggiore prima.
Andando avanti con questo articolo sulla funzione di ordinamento in C ++
Partial_sort
C ++ STL ci fornisce una funzione di ordinamento parziale, la funzione è simile alla funzione sort () ma a differenza della funzione sort () non viene utilizzata per ordinare l'intero intervallo piuttosto viene utilizzata per ordinare solo una sottoparte di esso. Ordina gli elementi nell'intervallo di [primo, ultimo), in modo tale che gli elementi prima dell'elemento centrale siano ordinati in ordine crescente, mentre gli elementi dopo il centro vengono lasciati così com'è.
Può essere usato per trovare l'elemento più grande se usiamo un oggetto funzione per ordinare per la prima posizione
Esempio
#include #include #include using namespace std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr partial_sort (vec.begin (), vec.begin () + 1, vec.end (), maggiore ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Produzione:
Spiegazione:
Il codice sopra può essere utilizzato per trovare il numero più grande in una serie, per trovare il numero più piccolo in serie è sufficiente rimuovere il comando maggiore.
Quindi siamo giunti alla fine di questo articolo sulla 'Funzione di ordinamento in C ++'. Se desideri saperne di più, dai un'occhiata al Java Training di Edureka, una società di formazione online affidabile. Edureka's sono progettati per addestrarti sia ai concetti base che avanzati di 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.