Clasificación: cómo ordenar una matriz que contiene 3 tipos de números

Question

Por ejemplo: int A[] = {3,2,1,2,3,2,1,3,1,2,3};

cómo ordenar eficazmente esta matriz?

Esto es para una entrevista de trabajo, solo necesito un pseudocódigo.

Answer 1

Problema: Usted tiene n cubos, cada cubo contiene una moneda, el valor de la moneda puede ser de 5 o 10 o 20. usted tiene que ordenar los cubos bajo esta limitación: 1. Puede utilizar este 2 funciones solamente: SwitchBaskets (Basket1, Basket2) - switch 2 cestas GetCoinValue (Basket1) - devuelve el valor de moneda en la cesta seleccionada 2. no puede definir la matriz de tamaño n 3. use la función de interruptor lo menos posible.

Mi solución simple de pseudocódigo, que puede implementarse en cualquier idioma con complejidad O (n).

voy a recoger monedas de la cesta 1) si es 5 - empujarlo a ser la primera, 2) si se 20- empujarlo a ser el último, 3) Si 10 - dejarlo donde es. 4) y mira el siguiente cubo en línea.

Editar:si no se puede empujar elementos a la primera o última posición continuación Merge sort sería lo ideal para la aplicación de pirata. Así es como funcionará:

Merge sort aprovecha la ventaja de combinar listas ya ordenadas en una nueva lista ordenada. Comienza comparando cada dos elementos (es decir, 1 con 2, luego 3 con 4 ...) e intercambiándolos si el primero debe aparecer después del segundo. Luego fusiona cada una de las listas resultantes de dos en listas de cuatro, luego combina esas listas de cuatro, y así sucesivamente; hasta que al final dos listas se fusionen en la lista ordenada final. De los algoritmos descritos aquí, este es el primero que escala bien a listas muy grandes, porque su peor tiempo de ejecución es O (n log n). Merge sort ha visto un aumento relativamente reciente en popularidad para implementaciones prácticas, que se utiliza para la rutina de ordenación estándar en los lenguajes de programación

Answer 2

Creo que la pregunta es para que usted use bucket sort. En los casos en que hay una pequeña cantidad de valores, la ordenación de depósitos puede ser mucho más rápida que la ordenación rápida más común o mergesort.

Answer 3

¿Has intentado ver el wiki por ejemplo? - http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 4

recuento de cada número y luego crean nueva matriz basada en sus recuentos ... complejidad del tiempo en O (n)

int counts[3] = {0,0,0}; 
for(int a in A) 
    counts[a-1]++; 
for(int i = 0; i < counts[0]; i++) 
    A[i] = 1; 
for(int i = counts[0]; i < counts[0] + counts[1]; i++) 
    A[i] = 2; 
for(int i = counts[0] + counts[1]; i < counts[0] + counts[1] + counts[2]; i++) 
    A[i] = 3; 

Answer 5

como Robert mencionó basketsort (o ordenamiento por casilleros) es el mejor en esta situación.

También me añadido algoritmo siguiente (en realidad es muy similar a BUSKET especie):

[pseudocódigo es Java de estilo]

crear un ciclo HashMap<Integer, Interger> map y a través de tu matriz:

for (Integer i: array) 
{ 
    Integer value = map.get(i); 
    if (value == null) 
    { 
     map.put(i, 1); 
    } 
    else 
    { 
     map.put(i, value+1); 
    } 
} 

Answer 6

La manera prometedora de ordenarlo parece ser counting sort. Vale la pena echar un vistazo a this lecture por Richard Buckland, especialmente la parte de 15:20.

De forma análoga a la clasificación por conteo, pero sería aún mejor crear una matriz que represente el dominio, inicializar todos sus elementos a 0 y luego iterar a través de su matriz y contar estos valores. Una vez que conozca esos recuentos de valores de dominio, puede reescribir los valores de su matriz en consecuencia. La complejidad de tal algoritmo sería O (n).

Aquí está el código C++ con el comportamiento tal como lo describí. Su complejidad es en realidad O (2n) sin embargo:

int A[] = {3,2,1,2,3,2,1,3,1,2,3}; 
int domain[4] = {0}; 

// count occurrences of domain values - O(n): 
int size = sizeof(A)/sizeof(int); 
for (int i = 0; i < size; ++i) 
    domain[A[i]]++; 

// rewrite values of the array A accordingly - O(n):  
for (int k = 0, i = 1; i < 4; ++i) 
    for (int j = 0; j < domain[i]; ++j) 
     A[k++] = i; 

Tenga en cuenta, que si hay gran diferencia entre los valores del dominio, el almacenamiento de dominio como una matriz es ineficiente. En ese caso, es una idea mucho mejor utilizar el mapa (gracias abhinav por señalarlo). Aquí está el código C++ que utiliza std::map para almacenar el valor de dominio - Contar apariciones pares:

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000}; 
std::map<int, int> domain; 

// count occurrences of domain values: 
int size = sizeof(A)/sizeof(int); 
for (int i = 0; i < size; ++i) 
{ 
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]); 
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first)) 
     keyItr->second++; // next occurrence 
    else 
     domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence 
} 

// rewrite values of the array A accordingly:  
int k = 0; 
for (auto i = domain.begin(); i != domain.end(); ++i) 
    for (int j = 0; j < i->second; ++j) 
     A[k++] = i->first; 

(si hay una manera de cómo utilizar std::map en el código de seguridad más eficiente, que me haga saber)

Answer 7

Este código se para C#:

Sin embargo, debe tener en cuenta los algoritmos para implementarlo de una manera no específica de lenguaje/marco. Como se sugiere, Bucket set podría ser el más eficiente. Si proporciona información detallada sobre el problema, trataría de buscar la mejor solución. Buena suerte ...

Aquí hay un ejemplo de código en C#.NET Descripción

int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 }; 
Array.Sort(intArray); 
// write array 
foreach (int i in intArray) Console.Write("{0}, ", i.ToString()); 

Answer 8

Es un problema estándar en informática: Dutch national flag problem Ver el enlace.

Answer 9

Creo que entiendo la pregunta: solo puedes usar O (1) espacio, y puedes cambiar la matriz solo intercambiando celdas. (Así que usted puede utilizar 2 operaciones de la matriz - SWAP y obtener)

Mi solución:

Uso 2 punteros de índice - una para la posición del último 1, y otro para la posición del último 2.

En el estadio I, se asume que la matriz está ordenada allready de 1 a i-1, de lo que comprueba la célula i: Si a [i] == 3 usted no hace nada. Si A [i] == 2 lo intercambia con la celda después del último 2 índice. Si A [i] == 1 lo intercambia con la celda después del último 2 índices, y luego cambia la celda después del último 2 índice (que contiene 1) con la celda después del último 1 índice.

Esta es la idea principal, debe cuidar los pequeños detalles. Complejidad general de O (n).

Answer 10

Sólo por diversión, aquí es como se llevaría a cabo "empujar los valores hasta el borde", como se sugiere ElYusubub:

sort(array) { 
    a = 0 
    b = array.length 
    # a is the first item which isn't a 1 
    while array[a] == 1 
    a++ 
    # b is the last item which isn't a 3 
    while array[b] == 3 
    b-- 

    # go over all the items from the first non-1 to the last non-3 
    for (i = a; i <= b; i++) 
    # the while loop is because the swap could result in a 3 or a 1 
    while array[i] != 2 
     if array[i] == 1 
     swap(i, a) 
     while array[a] == 1 
      a++ 
     else # array[i] == 3 
     swap(i, b) 
     while array[b] == 3 
      b-- 

En realidad, esto podría ser una solución óptima. No estoy seguro.

Answer 11

Aquí está la solución maravillosa, basada en @ElYusubov pero en lugar de empujar el cucharón (5) al principio & Cubo (15) hasta el final. Use el tamizado para que 5 avance hacia el principio y 15 hacia el final.

Cada vez que intercambiamos una cubeta de la posición final a la actual, disminuimos el final, no incrementamos el contador actual ya que necesitamos verificar nuevamente el elemento.

array = [15,5,10,5,10,10,15,5,15,10,5] 

    def swapBucket(int a, int b) { 

     if (a == b) return; 
     array[a] = array[a] + array[b] 
     array[b] = array[a] - array[b] 
     array[a] = array[a] - array[b] 

    } 

def getBucketValue(int a) { 
    return array[a]; 
} 

def start = 0, end = array.size() -1, counter = 0; 
// we can probably do away with this start,end but it helps when already sorted. 

// start - first bucket from left which is not 5 
while (start < end) { 

    if (getBucketValue(start) != 5) break; 
    start++; 

}  

// end - first bucket from right whichis not 15 
while (end > start) { 

    if (getBucketValue(end) != 15) break; 
    end--; 

} 

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1  

for (counter = start; counter < end;) { 

    def value = getBucketValue(counter) 

    if (value == 5) { swapBucket(start, counter); start++; counter++;} 
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter 
    else { counter++; } 

} 

for (key in array) { print " ${key} " } 

Answer 12

Permite resolver el problema, tenemos solo dos números en la matriz. [1,2,1,2,2,2,1,1]

Podemos ordenar en una pasada o (n) con intercambios mínimos si; Comenzamos dos punteros desde la izquierda y la derecha hasta que se encuentran. Intercambiando el elemento izquierdo con el derecho si el elemento izquierdo es más grande. (orden ascendente)

Podemos hacer otro pase, para tres números (k-1 pases). En el pase uno movimos 1 a su posición final y en el pase 2 movimos 2.

def start = 0, end = array.size() - 1; 

// Pass 1, move lowest order element (1) to their final position 
while (start < end) { 
    // first element from left which is not 1 
    for (; Array[start] == 1 && start < end ; start++); 
    // first element from right which IS 1 
    for (; Array[end] != 1 && start < end ; end--); 

    if (start < end) swap(start, end); 
}  

// In second pass we can do 10,15 

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions 

Answer 13

Esto se puede hacer muy fácilmente usando ->

algoritmo holandés de la bandera nacional http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

en lugar de utilizar 1,2,3 toman como 0,1,2

Answer 14

//Bubble sort for unsorted array - algorithm 
public void bubleSort(int arr[], int n) { //n is the length of an array 
    int temp; 
    for(int i = 0; i <= n-2; i++){ 
     for(int j = 0; j <= (n-2-i); j++){ 
      if(arr[j] > arr[j +1]){ 
       temp = arr[j]; 
       arr[j] = arr[j +1]; 
       arr[j + 1] = temp; 

      } 
     } 

    } 

Answer 15

def DNF(input,length): 
    high = length - 1 
    p = 0 
    i = 0 
    while i <= high: 
      if input[i] == 0: 
        input[i],input[p]=input[p],input[i] 
        p = p+1 
        i = i+1 
      elif input[i] == 2: 
        input[i],input[high]=input[high],input[i] 
        high = high-1 
      else: 
        i = i+1 
input = [0,1,2,2,1,0] 
print "input: ", input 
DNF(input,len(input)) 
print "output: ", input