¿Cómo ordeno una lista de enteros usando solo una variable entera adicional?

Question

¿Cómo ordenar la lista de valores usando solo una variable?

EDITAR: según el comentario de @Igor, he retitulado la pregunta.

Answer 1

Una solución en C:

#include <stdio.h>

int main()
{
    int list[]={4,7,2,4,1,10,3};
    int n;  // the one int variable

    startsort:
    for (n=0; n< sizeof(list)/sizeof(int)-1; ++n)
        if (list[n] > list[n+1]) {
            list[n] ^= list[n+1];
            list[n+1] ^= list[n];
            list[n] ^= list[n+1];
            goto startsort;
        }

    for (n=0; n< sizeof(list)/sizeof(int); ++n)
        printf("%d\n",list[n]);
    return 0;
}

La salida es, por supuesto, la misma que para el programa Icon.

Answer 2

Sospecho que estoy haciendo tu tarea por ti, pero oye, es un desafío interesante. Aquí hay una solución en Icon :

procedure mysort(thelist)
    local n # the one integer variable
    every n := (1 to *thelist & 1 to *thelist-1) do
    if thelist[n] > thelist[n+1] then thelist[n] :=: thelist[n+1]
    return thelist
end

procedure main(args)
    every write(!mysort([4,7,2,4,1,10,3]))
end

La salida:

1
2
3
4
4
7
10

Answer 3

Podría generar / escribir muchas redes de clasificación para cada tamaño de lista posible. Dentro de la red de clasificación, se utiliza una única variable para la operación de intercambio.

No recomendaría que lo hagas en software, pero es posible de todas formas.

Aquí hay una rutina de clasificación para todos n hasta 4 en C

// define a compare and swap macro 
#define order(a,b) if ((a)<(b)) { temp=(a); (a) = (b); (b) = temp; }

static void sort2 (int *data)
// sort-network for two numbers
{
  int temp;
  order (data[0], data[1]);
}

static void sort3 (int *data)
// sort-network for three numbers
{
  int temp;
  order (data[0], data[1]);
  order (data[0], data[2]);
  order (data[1], data[2]);
}

static void sort4 (int *data)
// sort-network for four numbers
{
  int temp;
  order (data[0], data[2]);
  order (data[1], data[3]);
  order (data[0], data[1]);
  order (data[2], data[3]);
  order (data[1], data[2]);
}

void sort (int *data, int n)
{
  switch (n)
    {
    case 0:
    case 1:
      break;
    case 2:
      sort2 (data);
      break;
    case 3:
      sort3 (data);
      break;
    case 4:
      sort4 (data);
      break;
    default:
      // Sorts for n>4 are left as an exercise for the reader
      abort();
    }
}

Obviamente necesitas un código de red de clasificación para cada N. posible

Más información aquí:

http://en.wikipedia.org/wiki/Sorting_network

Answer 4

En java:

import java.util.Arrays;

/**
 * Does a bubble sort without allocating extra memory
 *
 */
public class Sort {
    // Implements bubble sort very inefficiently for CPU but with minimal variable declarations
    public static void sort(int[] array) {
        int index=0;
        while(true) {
            next:
            {
                // Scan for correct sorting. Wasteful, but avoids using a boolean parameter
                for (index=0;index<array.length-1;index++) {
                    if (array[index]>array[index+1]) break next;
                }
                // Array is now correctly sorted
                return;
            }
            // Now swap. We don't need to rescan from the start
            for (;index<array.length-1;index++) {
                if (array[index]>array[index+1]) {
                    // use xor trick to avoid using an extra integer
                    array[index]^=array[index+1];
                    array[index+1]^=array[index];
                    array[index]^=array[index+1];
                }
            }
        }
    }

    public static void main(final String argv[]) {
        int[] array=new int[] {4,7,2,4,1,10,3};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

En realidad, usando el truco propuesto por Nils , puede eliminar incluso la asignación int pendiente restante, aunque, por supuesto, eso se agregaría a la pila ...

Answer 5

En rubí: [1, 5, 3, 7, 4, 2] .sort

Answer 6

Usted no, ya está ordenado. (como la pregunta es vaga, asumiré que variable es un sinónimo de un objeto)

Answer 7

Si tiene una lista (1 5 3 7 4 2) y una variable v , puede intercambiar dos valores de la lista, por ejemplo, el 3 y el 7, asignando primero 3 a v , luego asignando 7 al lugar de 3, finalmente asignando el valor de v al lugar original de 7. Después de eso, puede reutilizar v para el siguiente intercambio. Para ordenar, solo necesita un algoritmo que indique qué valores intercambiar. Puede buscar un algoritmo adecuado, por ejemplo, en http://en.wikipedia.org/wiki/Sorting_algorithm .