Как отсортировать список целых чисел, используя только одну дополнительную целочисленную переменную?
Вопрос
Как отсортировать список значений, используя только одну переменную?
РЕДАКТИРОВАТЬ:согласно комментарию @Igor, я переименовал вопрос.
Решение
Решение на 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;
}
Вывод, естественно, такой же, как и для программы 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
Выход:
1
2
3
4
4
7
10
Вы можете создать/записать множество сетей сортировки для каждого возможного размера списка.Внутри сортировочной сети вы используете одну переменную для операции обмена.
Я бы не рекомендовал делать это программно, но тем не менее это возможно.
Вот процедура сортировки для всех n до 4 в 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();
}
}
Очевидно, вам нужен код сортирующей сети для каждого возможного N.
Дополнительная информация здесь:
В Яве:
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));
}
}
На самом деле, используя трюк предложено Нильсом, вы можете исключить даже одно оставшееся выделение int - хотя, конечно, вместо этого это добавится в стек...
В рубине:[1, 5, 3, 7, 4, 2].сортировать
Нет, это уже отсортировано.(поскольку вопрос расплывчатый, я предполагаю, что переменная является синонимом объекта)
Если у вас есть список (1 5 3 7 4 2)
и переменная v
, вы можете поменять местами два значения списка, например 3 и 7, сначала присвоив 3 v
, затем присваивая 7 месту 3 и, наконец, присваивая значение v
на исходное место 7.После этого вы можете повторно использовать v
для следующего обмена.Для сортировки вам просто нужен алгоритм, который сообщает, какие значения обменивать.Подходящий алгоритм можно поискать например на http://en.wikipedia.org/wiki/Sorting_algorithm .