How do I sort a list of integers using only one additional integer variable?

How to sort list of values using only one variable?

EDIT: according to @Igor's comment, I retitled the question.

From stackoverflow Igor Drincic

• Do nothing?

  From Galwegian

• You dont, it is already sorted. (as the question is vague, I shall assume variable is a synonym for an object)

  From leppie

• care to elaborate?

  From Leon Tayson

• Do you mean list with only one element, or you mean sort it using only one additional variable?

  From Pavel Feldman

• You could generate/write a lot of sorting-networks for each possible list size. Inside the sorting network you use a single variable for the swap operation.

  I wouldn't recommend that you do this in software, but it is possible nevertheless.

  Here's a sorting-routine for all n up to 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();
      }
  }
  

  Obviously you need a sorting-network code for each possible N.

  More info here:

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

  Blair Conrad : Interesting, but it seems kind of impractical.

  Nils Pipenbrinck : It is impractical. The sort-networks are useful if you do hardware design because you can do multiple compare and swaps in parallel / at the same time, but in software a loop is almost always faster. Even vor small N

  florin : It's also outside the scope of the original challenge: you are using the stack.
  From Nils Pipenbrinck

• I suspect I'm doing your homework for you, but hey it's an interesting challenge. Here's a solution in 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
  

  The output:

  1
  2
  3
  4
  4
  7
  10
  

  From Hugh Allen

• A solution 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;
  }
  

  Output is of course the same as for the Icon program.

  From Hugh Allen

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

  Actually, by using the trick proposed by Nils, you can eliminate even the one remaining int allocation - though of course that would add to the stack instead...

  From Bill Michell

• If you have a list (1 5 3 7 4 2) and a variable v, you can exchange two values of the list, for example the 3 and the 7, by first assigning 3 to v, then assigning 7 to the place of 3, finally assigning the value of v to the original place of 7. After that, you can reuse v for the next exchange. In order to sort, you just need an algorithm that tells which values to exchange. You can look for a suitable algorithm for example at http://en.wikipedia.org/wiki/Sorting_algorithm .

  From Svante

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

  From $pageUsers[$post.author].name