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

Question

How to sort a list of values ​​using only one variable?

EDIT: as per @Igor's comment, I asked a question.

Answer 1

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

The conclusion, of course, is the same as for Icon.

Answer 2

I suspect that I am doing your homework, but this is an interesting task. Here's the 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 

Exit:

 1 2 3 4 4 7 10 

Answer 3

You can create / record many sorting networks for each possible list size. Inside the sorting network, one variable is used for the swap operation.

I would not recommend you to do this in software, but nonetheless, it is possible.

Here's a sorting procedure for all n 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 every possible N.

More details here:

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

Answer 4

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, using the trick suggested by Nils , you can eliminate even one remaining int allocation - although, of course, this will add to the stack instead ...

Answer 5

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

Answer 6

You're not, he's already sorted. (since the question is vague, I assume the variable is synonymous with the object)

Answer 7

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 3 and 7, first assigning 3 to v and then assigning 7 out of 3, finally assigning v original place 7 After that, you can reuse v for the next exchange. For sorting, you only need an algorithm that tells you which values ​​to exchange. You can find a suitable algorithm, for example, http://en.wikipedia.org/wiki/Sorting_algorithm .