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

Question

How to sort list of values using only one variable?

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

Answer 1

Do nothing?

Answer 2

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

Answer 3

care to elaborate?

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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 .

Answer 10

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