C Suggerimenti per lo smistamento di array

Question

 a=[1,3,6,7,1,2] 

Quale è la migliore tecnica di ordinamento per ordinare il seguente array e se ci sono duplicati su come gestirli. inoltre, che è la migliore tecnica di smistamento di tutti ....

void BubbleSort(int a[], int array_size) 
{ 
int i, j, temp; 
for (i = 0; i < (array_size - 1); ++i) 
{ 
     for (j = 0; j < array_size - 1 - i; ++j) 
     { 
      if (a[j] > a[j+1]) 
      { 
       temp = a[j+1]; 
       a[j+1] = a[j]; 
       a[j] = temp; 
      } 
     } 
} 
} 

Answer 1

In C, è possibile utilizzare il costruito nel qsort comando:

int compare(const void* a, const void* b) 
{ 
    int int_a = * ((int*) a); 
    int int_b = * ((int*) b); 

    if (int_a == int_b) return 0; 
    else if (int_a < int_b) return -1; 
    else return 1; 
} 

qsort(a, 6, sizeof(int), compare) 

vedi: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

---

Per rispondere alla seconda parte della domanda: un algoritmo di ordinamento ottimale (basato su confronto) è uno che viene eseguito con confronti O (n log (n)). Ce ne sono diversi che hanno questa proprietà (compresi l'ordinamento rapido, l'ordinamento di unione, l'ordinamento dell'heap, ecc.), Ma quale da usare dipende dal caso d'uso.

Come nota a margine, si può a volte fare meglio di O (n log (n)) se si sa qualcosa circa i dati - vedi l'articolo Wikipedia sul Radix Sort

Answer 2

Nel tuo caso particolare, il tipo più veloce è probabilmente quello descritto in this answer. È esattamente ottimizzato per un array di 6 pollici e utilizza reti di smistamento. È 20 volte (misurato su x86) più veloce della libreria qsort. Le reti di ordinamento sono ottimali per tipi di matrici a lunghezza fissa. Poiché sono una sequenza fissa di istruzioni, possono persino essere implementate facilmente dall'hardware.

In generale esistono numerosi algoritmi di ordinamento ottimizzati per casi specifici. Gli algoritmi di uso generale come heap sort o quick sort sono ottimizzati per l'ordinamento in loco di una serie di elementi. Forniscono una complessità di O (n.log (n)), n è il numero di elementi da ordinare.

La funzione di libreria qsort() è molto ben codificato ed efficiente in termini di complessità, ma utilizza una chiamata a una funzione comparizon fornito dall'utente, e questa chiamata ha un costo piuttosto elevato.

Per l'ordinamento di una grande quantità di dati gli algoritmi devono anche occuparsi dello scambio di dati da e verso il disco, questo è il tipo di ordinamento implementato nei database e la soluzione migliore se si hanno tali esigenze è mettere i dati in alcuni database e utilizzare l'ordinamento incorporato.

Answer 3

Depends

Dipende da varie cose. In generale, tuttavia, gli algoritmi che utilizzano un approccio Divide-and-Conquer/dichotomic si comportano bene per problemi di ordinamento in quanto presentano interessanti complessità del caso medio.

Basics

per capire quali algoritmi funzionano meglio, avrete bisogno di conoscenza di base di algorithms complexity e big-O notation, in modo da poter capire come si valutano in termini di average case, best case and worst case scenarios. Se necessario, dovresti anche prestare attenzione allo sorting algorithm's stability.

Ad esempio, in genere un algoritmo efficiente è quicksort. Tuttavia, se si fornisce a quicksort una lista perfettamente invertita, allora avrà un rendimento scarso (un ordinamento di selezione semplice avrà un rendimento migliore in tal caso!). Shell-sort sarebbe anche di solito un buon complemento a quicksort se si esegue una pre-analisi del proprio elenco.

dare un'occhiata a quanto segue, per "le ricerche avanzate" utilizzando divide et impera approcci:

• quicksort
• shellsort
• mergesort

E questi algoritmi più straighforward per meno quelli complessi:

• bubblesort
• selection sort
• insert sort

Ulteriori

Quanto sopra sono i soliti noti Quando si comincia, ma ci sono innumerevoli altri.

Come indicato da R. nei commenti e da kriss nella sua risposta, si consiglia di dare un'occhiata a HeapSort, che fornisce una complessità di ordinamento teoricamente migliore di un quicksort (ma non sarà spesso meglio in impostazioni pratiche). Esistono anche varianti e hybrid algorithms (ad esempio TimSort).

Answer 4

vorrei apportare alcune modifiche: In C, è possibile utilizzare il costruito nel qsort comando:

int compare(const void* a, const void* b) 
{ 
    int int_a = * ((int*) a); 
    int int_b = * ((int*) b); 

    // an easy expression for comparing 
    return (int_a > int_b) - (int_a < int_b); 
} 

qsort(a, 6, sizeof(int), compare) 

Answer 5

La tecnica migliore di smistamento di tutto dipende generalmente coincide con la dimensione di un array. Unisci sort può essere il migliore di tutti in quanto gestisce una maggiore complessità di spazio e tempo secondo l'algoritmo Big-O (questo si adatta meglio a un array di grandi dimensioni).