¿Cómo ordenar una matriz con el mínimo número de escrituras?

Question

Mi amigo se hizo una pregunta en su entrevista:

El entrevistador le dio una serie de números sin clasificar y le pidió que ordenara. La restricción es que el número de escrituras debe reducirse al mínimo, mientras que no hay ninguna limitación en el número de lecturas.

Answer 1

Si la matriz es más corta (es decir, menos de 100 elementos), a Selection sort suele ser la mejor opción si también desea reducir el número de escrituras.

de Wikipedia:

Otra diferencia clave es que ordenación por selección siempre realiza Θ (n) permutas, mientras que la ordenación por inserción realiza Θ (n) intercambia en el promedio y peores casos . Debido a que los swaps requieren escribir en la matriz, la ordenación por selección es preferible si escribir en la memoria es significativamente más caro que la lectura . Este es generalmente el caso si los artículos son enormes, pero las claves son pequeñas. Otro ejemplo donde escribir veces es crucial es una matriz almacenada en EEPROM o Flash. No hay otro algoritmo con menos movimiento de datos.

Para matrices/listas más grandes Quicksort y sus amigos proporcionarán un mejor rendimiento, pero es probable que necesiten más escrituras que una ordenación por selección.

Si le interesa this is a fantastic sort visualization site que le permite ver los algoritmos de ordenamiento específicos hacer su trabajo y también "competir" con los algoritmos de clasificación diferentes entre sí.

Answer 2

Si los números están en un rango específico, la tarea puede realizarse en O (n) tiempo de cálculo, que es un caso especial de pedido, se hace creando una matriz y asignando cada número a la posición especificada.

Si los números no están en un rango, la mejor manera de hacerlo es utilizando QuickSort o HeapSort, que ordena int O (Log2N) ambos, pero algunos prefieren QuickSort, como yo.

Puede encontrar una implementación de QuickSort en cualquier idioma en casi todos los lugares, solo Google y lo encontrará en segundos.

Una adaptación de HeapSort está disponible cuando se organizan datos externos, es decir, datos que no están en la memoria, sino en el disco duro, más comunes cuando se trata de arreglos enormes.

Espero que pueda ser de ayuda ¡Saludos cordiales y la mejor de las suertes!

Answer 3

Puede usar un algoritmo muy ingenuo que satisfaga lo que necesita.

El algoritmo debe tener este aspecto:

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 búsqueda del mínimo puede costar casi nada, le cuesta al intercambio que 3 escribe, el i ++ te cuesta 1 ..

Esto se llama selection sort según lo indicado por ceniza.(Lo siento, no sabía que era la selección ordenar :()

Answer 4

El orden que mencioné en O (n) es como el tipo de selección (la publicación anterior) útil cuando tienes una pequeña gama de teclas (o están ordenando números entre 2 rangos)

Si tiene una matriz de números donde los números estarán entre -10 y 100, entonces puede crear una matriz de 110 y asegurarse de que todos los números encajen allí, si considera repetidos números de la idea es la misma, pero tendrá listas en lugar de números en la matriz ordenada

la pseudo-idea es como esta

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 tendrá la matriz final ordenada y tendrá o (N) operaciones de escritura, donde N es el rango de la matriz. Una vez más, esto es útil cuando se usan claves dentro de un rango específico, pero tal vez sea su caso.

¡Saludos y buena suerte!

Answer 5

Una opción para matrices grandes es como sigue (suponiendo n elementos):

1. inicializar una matriz con n elementos numerados 0..n-1
2. ordenar la matriz usando cualquier algoritmo de ordenación. Como función de comparación, compare los elementos en el conjunto de entrada con los números correspondientes (por ejemplo, para comparar 2 y 4, compare los elementos 2 y 4 en el conjunto de entrada). Esto convierte la matriz del paso 1 en una permutación que representa el orden ordenado del conjunto de entrada.
3. Iterate a través de los elementos en la permutación, escribiendo los bloques en el orden especificado por la matriz. Esto requiere exactamente n escribe, el mínimo.

Para clasificar in situ, en el paso 3, en su lugar, debe identificar los ciclos en la permutación, y 'rotarlos' según sea necesario para obtener un orden ordenado.

Answer 6

Clasificación de selección es no el algoritmo correcto aquí. La ordenación de selección intercambiará valores, haciendo hasta dos escrituras por selección, dando un máximo de 2n escrituras por género.

Un algoritmo que es dos veces mejor que la ordenación de selección es "cycle" sort, que no se intercambia. El tipo de ciclo dará un máximo de n escrituras por género. El número de escrituras está absolutamente minimizado. Solo escribirá un número una vez en su destino final, y solo en ese caso si aún no está allí.

Se basa en la idea de que all permutations are products of cycles y usted puede simplemente recorrer cada ciclo y escribir cada elemento en su lugar apropiado una vez.

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)); 
    } 
    } 
} 

Algunos ejemplo ejecuta  :

 
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