Penso che sia MergeSort, che è O (n log n). Tuttavia, il seguente output non è d’accordo: -1,0000000099000391,0000000099000427 1,0000000099000427,0000000099000346 5,0000000099000391,0000000099000346 1,0000000099000427,0000000099000345 5,0000000099000391,0000000099000345 1,0000000099000346,0000000099000345 Sto classificando un nodelist di 4 nodes per numero di sequenza, e l’ordinamento sta facendo 6 confronti. Sono perplesso perché 6> (4 log (4)). Qualcuno può spiegarmelo? PS È un mergesort, ma […]
Ho trovato questo codice in internet ed era per gli array, voglio cambiarlo per la lista doppiamente collegata (invece dell’indice dovremmo usare il puntatore), per favore aiutatemi come posso cambiare il metodo di fusione (ho cambiato metodo di ordinamento da solo) anche questo non è il mio lavoro a casa, mi piace lavorare con la […]
Non sono riuscito a trovare alcun codice operazionale di Python 3.3, quindi l’ho creato io stesso. C’è un modo per accelerarlo? Ordina circa 20000 numeri in circa 0,3-0,5 secondi def msort(x): result = [] if len(x) 0) or (len(z) > 0): if len(y) > 0 and len(z) > 0: if y[0] > z[0]: result.append(z[0]) z.pop(0) […]
Il metodo Arrays.sort Java 6 utilizza Quicksort per matrici di primitive e unisci l’ordinamento per matrici di oggetti. Credo che la maggior parte del tempo Quicksort sia più veloce di unire l’ordinamento e costa meno memoria. I miei esperimenti supportano questo, sebbene entrambi gli algoritmi siano O (n log (n)). Quindi, perché sono utilizzati algoritmi […]
Come posso implementare un quicksort concorrente o un algoritmo di mergesort per Java? Abbiamo riscontrato problemi su un Mac (virtuale) a 16 picchi dove solo un core (!) Funzionava usando l’algoritmo di ordinamento Java predefinito ed era, beh, non bello vedere quella macchina molto fine essere completamente sottoutilizzata. Quindi abbiamo scritto il nostro (l’ho scritto […]
Mi è stata fatta questa domanda durante un’intervista. Sono entrambi O (nlogn) eppure la maggior parte delle persone usa Quicksort invece di Mergesort. Perché?
Mi è stato chiesto in un’intervista e questa è la soluzione che ho fornito: public static int[] merge(int[] a, int[] b) { int[] answer = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] < b[j]) { answer[k] = […]
So che la domanda non è troppo specifica. Tutto quello che voglio è qualcuno che mi dica come convertire un ordinamento di tipo normale in un ordinamento di fusione diretto (o un ordinamento di tipo merge con overhead di spazio aggiuntivo costante). Tutto quello che posso trovare (in rete) sono le pagine che dicono “è […]