Come ordinare un elenco di numeri interi usando solo una variabile intera aggiuntiva?

Question

Come ordinare un elenco di valori usando solo una variabile?

EDIT: secondo il commento di @ Igor, ho ribattezzato la domanda.

Answer 1

Una soluzione in 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;
}

L'output è ovviamente lo stesso del programma Icon.

Answer 2

Sospetto di fare i compiti per te, ma hey è una sfida interessante. Ecco una soluzione in Icona :

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

L'output:

1
2
3
4
4
7
10

Answer 3

Potresti generare / scrivere molte reti di ordinamento per ogni possibile dimensione dell'elenco. All'interno della rete di smistamento si utilizza una singola variabile per l'operazione di scambio.

Non consiglierei di farlo nel software, ma è comunque possibile.

Ecco una routine di ordinamento per tutti n fino a 4 in 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();
    }
}

Ovviamente è necessario un codice di rete di ordinamento per ogni possibile N.

Maggiori informazioni qui:

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

Answer 4

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

In realtà, usando il trucco proposta da Nils , puoi eliminare anche l'unica allocazione int rimanente, anche se ovviamente aggiungerebbe invece allo stack ...

Answer 5

In rubino: [1, 5, 3, 7, 4, 2] .sort

Answer 6

Non è già ordinato. (poiché la domanda è vaga, suppongo che la variabile sia sinonimo di un oggetto)

Answer 7

Se hai un elenco (1 5 3 7 4 2) e una variabile v , puoi scambiare due valori dell'elenco, ad esempio 3 e il 7, assegnando prima 3 a v , quindi assegnando 7 al posto di 3, assegnando infine il valore di v al posto originale di 7. Successivamente, è possibile riutilizzare v per il prossimo scambio. Per ordinare, hai solo bisogno di un algoritmo che indichi quali valori scambiare. Puoi cercare un algoritmo adatto ad esempio a http://en.wikipedia.org/wiki/Sorting_algorithm .