2

1つの変数のみを使用して値のリストをソートする方法は?

編集: @Igor のコメントによると、質問のタイトルを変更しました。

4

7 に答える 7

6

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

もちろん、出力はアイコンプログラムの場合と同じです。

于 2008-09-25T13:23:49.053 に答える
4

私はあなたのためにあなたの宿題をしているのではないかと思いますが、ちょっとそれは面白い挑戦です。アイコンの解決策は次のとおりです。

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
于 2008-09-25T12:41:52.023 に答える
2

可能なリストサイズごとに多くのソートネットワークを生成/書き込むことができます。並べ替えネットワーク内では、swap 操作に単一の変数を使用します。

ソフトウェアでこれを行うことはお勧めしませんが、それでも可能です。

これは、C で 4 までのすべての n の並べ替えルーチンです。

// 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 ごとにソーティング ネットワーク コードが必要です。

詳細はこちら：

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

于 2008-09-25T11:47:00.703 に答える
1

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つでも削除できます-もちろん、代わりにスタックに追加されます...

于 2008-09-25T13:35:17.323 に答える
1

Ruby の場合: [1, 5, 3, 7, 4, 2].sort

于 2008-11-06T12:34:22.353 に答える
0

リスト(1 5 3 7 4 2)と変数がある場合は、最初に3をに割り当て、次に3の場所に7を割り当て、最後にの値を元の場所に割り当てることvで、リストの2つの値（たとえば、3と7）を交換できます。その後、次の交換に再利用できます。ソートするには、交換する値を指示するアルゴリズムが必要です。たとえば、 http：//en.wikipedia.org/wiki/Sorting_algorithmで適切なアルゴリズムを探すことができます。vvv

于 2008-11-06T12:05:38.043 に答える
0

いいえ、それはすでにソートされています。（質問があいまいなので、変数はオブジェクトの同義語であると仮定します）

于 2008-09-25T10:29:01.517 に答える