Come ordinare un array usando il numero minimo di scritture?

Question

Il mio amico è stato posto una domanda nella sua intervista:

L'intervistatore gli ha dato una serie di numeri non ordinati e gli ha chiesto di ordinare. La restrizione è che il numero di scritture dovrebbe essere minimizzato mentre non vi è alcuna limitazione sul numero di letture.

Answer 1

Se la matrice è più corta (ovvero inferiore a circa 100 elementi), una Selection sort è spesso la scelta migliore se si desidera ridurre anche il numero di scritture.

Da wikipedia:

Un'altra differenza fondamentale è che selezione esegue sort sempre Θ (n) swap, mentre per inserzione effettua Θ (n) scambia nella media e peggiori casi . Poiché gli swap richiedono la scrittura di nell'array, l'ordinamento di selezione è preferibile se la scrittura nella memoria è significativamente più costosa della lettura di . Questo è generalmente il caso se gli articoli sono enormi ma le chiavi sono piccole. Un altro esempio in cui la scrittura di volte è cruciale è un array memorizzato in EEPROM o Flash. Non c'è nessun altro algoritmo con meno movimento di dati.

Per gli array più grandi/elenca Quicksort e gli amici forniranno prestazioni migliori, ma possono essere ancora più probabile che sia necessario scrive di una selezione sorta.

Se sei interessato allo this is a fantastic sort visualization site che ti permette di guardare specifici algoritmi di ordinamento, fai il loro lavoro e anche "gareggia" con algoritmi di ordinamento diversi l'uno contro l'altro.

Answer 2

Se i numeri si trovano in un intervallo specifico, l'operazione può essere eseguita in tempo di elaborazione O (n), che è un caso speciale di ordine, è fatto creando una matrice e mappando ciascun numero nella posizione specificata.

Se i numeri non sono in un intervallo, il modo migliore per farlo è utilizzare QuickSort o HeapSort, che ordina int O (Log2N) entrambi, ma un altro pre-QuickSort, come me.

È possibile trovare un'implementazione QuickSort in qualsiasi lingua in quasi ogni luogo, solo su Google e lo troverete in pochi secondi.

Un adattamento di HeapSort è disponibile quando si organizzano dati esterni, si intendono dati che non sono in memmory, ma in hard disk, il più comune quando si tratta di enormi matrici.

Spero di poter essere d'aiuto I migliori saluti e buona fortuna!

Answer 3

È possibile utilizzare un algoritmo molto ingenuo che soddisfa ciò che è necessario.

L'algoritmo dovrebbe essere simile a questo:

i = 0 

do 
    search for the minimum in range [i..n) 
    swap a[i] with a[minPos] 
    i = i + 1 
repeat until i = n. 

La ricerca del minimo può costare quasi nulla, lo swap ti costa 3 scrive, l'i ++ ti costa 1 ..

Questo si chiama selection sort come indicato dalla cenere.(Scusate, non sapevo che fosse un tipo di selezione :()

Answer 4

L'ordinamento che intendevo in O (n) è come l'ordinamento di selezione (il post precedente) utile quando avete una piccola gamma di chiavi (o voi ordinare numeri tra 2 intervalli)

Se si dispone di un array di numeri in cui i numeri saranno compresi tra -10 e 100, è possibile creare un array di 110 e assicurarsi che tutti i numeri si adattino a tale valore, se si considerano ripetuti numeri l'idea è la stessa, ma si avrà liste al posto dei numeri nella matrice ordinata

la pseudo-idea è come questo

N: max value of your array 
tosort //array to be sorted 
sorted = int[N] 

for i = 0 to length(tosort) 
do 
    sorted[tosort[i]]++; 
end 

finalarray = int[length(tosort)] 

k = 0 
for i = 0 to N 
do 
    if (sorted[i] > 0) 
    finalarray[k] = i 
    k++; 
    endif 
end 

finalarray avrà l'array ordinato finale e si avranno o (N) operazioni di scrittura, dove N è l'intervallo dell'array. Ancora una volta, questo è utile quando si usano le chiavi all'interno di un intervallo specifico, ma forse è il tuo caso.

Cordiali saluti e buona fortuna!

Answer 5

Una possibilità per grandi array è (supponendo n elementi) come segue:

1. inizializzare un array con n elementi numerati 0..n-1
2. ordine dell'array utilizzando qualsiasi algoritmo di ordinamento. Come funzione di confronto, confronta gli elementi nel set di input con i numeri corrispondenti (ad esempio, per confrontare 2 e 4, confronta il 2 ° e il 4 ° elemento nel set di input). Ciò trasforma la matrice dal passaggio 1 in una permutazione che rappresenta l'ordine ordinato dell'insieme di input.
3. Iterate attraverso gli elementi nella permutazione, scrivendo i blocchi nell'ordine specificato dalla matrice. Ciò richiede esattamente n scritture, il minimo.

Per ordinare sul posto, al punto 3 occorre invece identificare i cicli nella permutazione e "ruotarli" secondo necessità per ottenere un ordine ordinato.

Answer 6

L'ordinamento di selezione è non l'algoritmo corretto qui. L'ordinamento della selezione scambierà i valori, fino a due scritture per selezione, dando un massimo di 2n scritture per ordinamento.

Un algoritmo doppio rispetto alla selezione è "cycle" sort, che non si scambia. L'ordinamento del ciclo darà un massimo di n scritture per ordinamento. Il numero di scritture è assolutamente ridotto al minimo. Scriverà un numero solo una volta fino alla sua destinazione finale, e solo allora se non lo è già.

Si basa sull'idea che è all permutations are products of cycles e puoi semplicemente scorrere ogni ciclo e scrivere ogni elemento nella posizione corretta una volta.

import java.util.Random; 
import java.util.Collections; 
import java.util.Arrays; 

public class CycleSort { 
    public static final <T extends Comparable<T>> int cycleSort(final T[] array) { 
    int writes = 0; 

    // Loop through the array to find cycles to rotate. 
    for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) { 
     T item = array[cycleStart]; 

     // Find where to put the item. 
     int pos = cycleStart; 
     for (int i = cycleStart + 1; i < array.length; i++) 
     if (array[i].compareTo(item) < 0) pos++; 

     // If the item is already there, this is not a cycle. 
     if (pos == cycleStart) continue; 

     // Otherwise, put the item there or right after any duplicates. 
     while (item.equals(array[pos])) pos++; 
     { 
     final T temp = array[pos]; 
     array[pos] = item; 
     item = temp; 
     } 
     writes++; 

     // Rotate the rest of the cycle. 
     while (pos != cycleStart) { 
     // Find where to put the item. 
     pos = cycleStart; 
     for (int i = cycleStart + 1; i < array.length; i++) 
      if (array[i].compareTo(item) < 0) pos++; 

     // Put the item there or right after any duplicates. 
     while (item.equals(array[pos])) pos++; 
     { 
      final T temp = array[pos]; 
      array[pos] = item; 
      item = temp; 
     } 
     writes++; 
     } 
    } 
    return writes; 
    } 

    public static final void main(String[] args) { 
    final Random rand = new Random(); 

    final Integer[] array = new Integer[8]; 
    for (int i = 0; i < array.length; i++) { array[i] = rand.nextInt(8); } 

    for (int iteration = 0; iteration < 10; iteration++) { 
     System.out.printf("array: %s ", Arrays.toString(array)); 
     final int writes = cycleSort(array); 
     System.out.printf("sorted: %s writes: %d\n", Arrays.toString(array), writes); 
     Collections.shuffle(Arrays.asList(array)); 
    } 
    } 
} 

Alcuni esempio esegue  :

 
array: [3, 2, 6, 1, 3, 1, 4, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [1, 3, 4, 1, 3, 2, 4, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 4 
array: [3, 3, 1, 1, 4, 4, 2, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [1, 1, 3, 2, 4, 3, 6, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [3, 2, 3, 4, 6, 4, 1, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 
array: [6, 2, 4, 3, 1, 3, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6 
array: [6, 3, 2, 4, 3, 1, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 5 
array: [4, 2, 6, 1, 1, 4, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 
array: [4, 3, 3, 1, 2, 4, 6, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 
array: [1, 6, 4, 2, 4, 1, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7 

 
array: [5, 1, 2, 3, 4, 3, 7, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 5 
array: [5, 1, 7, 3, 2, 3, 4, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6 
array: [4, 0, 3, 1, 5, 2, 7, 3] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 8 
array: [4, 0, 7, 3, 5, 1, 3, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [3, 4, 2, 7, 5, 3, 1, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [0, 5, 3, 2, 3, 7, 1, 4] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6 
array: [1, 4, 3, 7, 2, 3, 5, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [1, 5, 0, 7, 3, 3, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7 
array: [0, 5, 7, 3, 3, 4, 2, 1] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 4 
array: [7, 3, 1, 0, 3, 5, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7