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.

Answer 1

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.

Answer 2

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

Answer 3

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:

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 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 ...

Answer 5

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

Answer 6

Vous n'avez pas, c'est déjà trié. (comme la question est vague, je supposerai que variable est un synonyme d'objet)

Answer 7

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 .