하나의 추가 정수 변수 만 사용하여 정수 목록을 어떻게 정렬합니까?
문제
하나의 변수 만 사용하여 값 목록을 정렬하는 방법은 무엇입니까?
편집 : @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;
}
출력은 물론 아이콘 프로그램과 동일합니다.
다른 팁
나는 당신을 위해 당신의 숙제를하고 있다고 생각하지만, 그것은 흥미로운 도전입니다. 여기에 해결책이 있습니다 상:
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
가능한 각 목록 크기에 대해 많은 분류 네트워크를 생성/쓸 수 있습니다. 정렬 네트워크 내에서 스왑 작업에 단일 변수를 사용합니다.
나는 당신이 소프트웨어로 이것을하는 것을 권장하지는 않지만 그럼에도 불구하고 가능합니다.
다음은 C에서 최대 4 개까지의 정렬 러틴입니다.
// 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에 대해 정렬 네트워크 코드가 필요합니다.
추가 정보는 여기에 있습니다 :
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));
}
}
실제로, 트릭을 사용하여 Nils가 제안했습니다, 당신은 나머지 int 할당을 제거 할 수 있습니다. 물론 스택에 추가 될 것입니다 ...
루비에서 : [1, 5, 3, 7, 4, 2].
당신은 이미 정렬되어 있습니다. (질문이 모호하기 때문에 변수가 객체의 동의어라고 가정합니다)
목록이있는 경우 (1 5 3 7 4 2)
그리고 변수 v
, 먼저 3과 7을 할당하여 목록의 두 값 (예 : 3과 7) 값을 교환 할 수 있습니다. v
, 그런 다음 7을 3의 장소에 할당하고 마침내 값을 할당합니다. v
그 후, 당신은 재사용 할 수 있습니다. v
다음 교환을 위해. 정렬하려면 교환 할 값을 알려주는 알고리즘 만 있으면됩니다. 예를 들어 적절한 알고리즘을 찾을 수 있습니다. http://en.wikipedia.org/wiki/sorting_algorithm .