Comment trier une liste d'entiers à l'aide d'une seule variable supplémentaire?
Question
Comment trier la liste de valeurs en utilisant une seule variable?
EDIT: selon le commentaire de @ Igor, j'ai renommé la question.
La solution
Une solution 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 sortie est bien sûr la même que pour le programme Icon.
Autres conseils
Je suppose que je fais vos devoirs pour vous, mais bon, c’est un défi intéressant. Voici une solution dans 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 sortie:
1
2
3
4
4
7
10
Vous pourriez générer / écrire beaucoup de réseaux de tri pour chaque taille de liste possible. Dans le réseau de tri, vous utilisez une seule variable pour l'opération d'échange.
Je ne vous recommanderais pas de faire cela dans un logiciel, mais c'est néanmoins possible.
Voici une routine de tri pour tous les n à 4 dans 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();
}
}
Évidemment, vous avez besoin d’un code de réseau de tri pour chaque N possible.
Plus d'infos ici:
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 fait, en utilisant l'astuce proposée par Nils , vous pouvez éliminer même l’allocation int restante - bien sûr, cela ajouterait à la pile à la place ...
En rubis: [1, 5, 3, 7, 4, 2] .sort
Vous n'avez pas, c'est déjà trié. (comme la question est vague, je supposerai que variable est un synonyme d'objet)
Si vous avez une liste (1 5 3 7 4 2)
et une variable v
, vous pouvez échanger deux valeurs de la liste, par exemple les valeurs 3 et 7, en assignant d’abord 3 à v
, puis en assignant 7 à la place de 3, puis en assignant la valeur de v
à la place originale de 7. Ensuite, vous pouvez réutilisez v
pour le prochain échange. Pour trier, vous avez simplement besoin d'un algorithme qui indique les valeurs à échanger. Vous pouvez rechercher un algorithme approprié, par exemple, à l'adresse http://fr.wikipedia.org/wiki/Sorting_algorithm .