Come ordinare un elenco di numeri interi usando solo una variabile intera aggiuntiva?
Domanda
Come ordinare un elenco di valori usando solo una variabile?
EDIT: secondo il commento di @ Igor, ho ribattezzato la domanda.
Soluzione
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.
Altri suggerimenti
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
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:
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 ...
In rubino: [1, 5, 3, 7, 4, 2] .sort
Non è già ordinato. (poiché la domanda è vaga, suppongo che la variabile sia sinonimo di un oggetto)
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 .