7

N の数値範囲 (例: [1 から 100]) が与えられた場合、数値を桁順に並べ替えます (つまり、数値 1 から 100 の場合、並べ替えられた出力は 1 10 100 11 12 13 になります。. . 19 2 20 21..... 99

これは基数ソートと同じですが、通常の基数ソートとは逆の順序で数字がソートされます。

操作を高速化するために、各数値のすべての数字をリンクされたリストとして保存しようとしましたが、スペースの複雑さが大きくなります。

質問には実用的なアルゴリズムが必要です。

すべての回答から、「文字列への変換」はオプションですが、これを行う方法は他にありませんか? また、上記の文字列の並べ替えのアルゴリズムも指定できます。

4

7 に答える 7

11

好きな並べ替えアルゴリズムを使用しますが、数値を数値ではなく文字列として比較します。これは基本的に、ハミング数の字句ソートです。Cでのノームソートの例を次に示します。

#include <stdlib.h>
#include <string.h>

void sort(int* array, int length) {
    int* iter = array;
    char buf1[12], buf2[12];
    while(iter++ < array+length) {
        if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) {
            iter++;
        } else {
            *iter ^= *(iter+1);
            *(iter+1) ^= *iter;
            *iter ^= *(iter+1);
            iter--;
        }
    }
}

もちろん、これには非標準itoa関数がに存在する必要がありstdlib.hます。より標準的な代替手段はを使用することsprintfですが、それはコードをもう少し乱雑にします。配列全体を最初に文字列に変換し、次に並べ替えてから、元に戻す方がよいでしょう。

編集：参考までに、ここでの関連ビットはでありstrcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0、これは。を置き換え*iter >= *(iter-1)ます。

于 2010-08-01T13:05:35.837 に答える
4

私には解決策がありますが、正確にはアルゴリズムではありません。あなたがする必要があるのは、すべての数値を文字列に変換し、それらを文字列としてソートすることです。

于 2010-08-01T13:06:09.503 に答える
3

再帰関数を使用してそれを行う方法は次のとおりです (コードは Java です)。

void doOperation(List<Integer> list, int prefix, int minimum, int maximum) {
    for (int i = 0; i <= 9; i++) {
        int newNumber = prefix * 10 + i;
        if (newNumber >= minimum && newNumber <= maximum) {
            list.add(newNumber);
        }
        if (newNumber > 0 && newNumber <= maximum) {
            doOperation(list, newNumber, minimum, maximum);
        }
    }
}

次のように呼び出します。

List<Integer> numberList = new ArrayList<Integer>();
int min=1, max =100;
doOperation(numberList, 0, min, max);
System.out.println(numberList.toString());

編集：

ここでC++でコードを翻訳しました：

#include <stdio.h> 

void doOperation(int list[], int &index, int prefix, int minimum, int maximum) {
    for (int i = 0; i <= 9; i++) {
        int newNumber = prefix * 10 + i;
        if (newNumber >= minimum && newNumber <= maximum) {
            list[index++] = newNumber;
        }
        if (newNumber > 0 && newNumber <= maximum) {
            doOperation(list, index, newNumber, minimum, maximum);
        }
    }
}

int main(void) { 
        int min=1, max =100;
        int* numberList = new int[max-min+1];
        int index = 0;
        doOperation(numberList, index, 0, min, max);
        printf("["); 
        for(int i=0; i<max-min+1; i++) {
                printf("%d ", numberList[i]); 
        }
        printf("]"); 
        return 0; 
}

minimum基本的に、アイデアは次のとおりです。各数字（0〜9）について、〜の間にある場合は配列に追加しmaximumます。次に、この数字をプレフィックスとして同じ関数を呼び出します。同じことを行います。各桁について、それをプレフィックス ( prefix * 10 + i) に追加し、範囲内にある場合は配列に追加します。newNumberが最大値を超えると停止します。

于 2010-08-01T13:34:34.243 に答える
2

数値の保存方法を最適化します。特定の桁に簡単にアクセスできる2進化10進数（BCD）タイプを使用します。次に、現在のアルゴリズムを使用できます。これは、SteveJessopが最上位桁の基数ソートとして正しく識別したものです。

より高速な操作のために、各番号のすべての数字をリンクリストとして保存しようとしましたが、スペースが非常に複雑になります。

リンクリストに各桁を格納すると、2つの異なる方法でスペースが無駄になります。

  1. 数字（0〜9）は、格納に4ビットのメモリしか必要としませんが、おそらく8〜64ビットのどこかを使用しています。またはタイプは8ビットを取り、ancharは最大64ビットを取ります。これは、最適なソリューションの2倍から16倍のメモリを使用しています。shortint
  2. リンクリストは、不要なメモリオーバーヘッドを追加します。次のリンクのメモリアドレスを格納するには、各桁に32〜64ビットを追加する必要があります。繰り返しますが、これにより、1桁あたりに必要なメモリが8倍から16倍に増加します。

よりメモリ効率の高いソリューションは、 BCD桁をメモリに連続して格納します。

  1. BCDは1桁あたり4ビットのみを使用します。
  2. 数字を配列のように連続したメモリブロックに格納します。これにより、メモリアドレスを保存する必要がなくなります。途中から簡単に挿入/削除するリンクリストの機能は必要ありません。数値を未知の長さに増やす機能が必要な場合は、はるかに少ないオーバーヘッドでそれを可能にする他の抽象データ型があります。たとえば、ベクトル。

加算/乗算などの他の演算が重要でない場合の1つのオプションは、各BCD桁と1つのBCDターミネータを格納するのに十分なメモリを割り当てることです。BCDターミネータは、BCD桁（2進数など）を表すために使用されない4ビットの任意の組み合わせにすることができます1111。ただし、この方法で保存すると、加算や乗算などの他の操作が難しくなります。

これは、文字列に変換し、それらの文字列を辞書式に並べ替えるという考え方と非常に似ていることに注意してください。整数は、コンピューターにバイナリ（基数2）として内部的に格納されます。BCDへの格納は基数10（実際には基数16ですが、6つの組み合わせは無視されます）に似ており、文字列は基数256に似ています。文字列は約2倍のメモリを使用しますが、文字列を並べ替えるために記述された効率的な関数がすでにあります。BCDは、おそらくニーズに合わせてカスタムBCDタイプを開発する必要があります。

于 2010-08-01T14:48:46.393 に答える
2

数字を文字列に変換すると、文字列比較を使用して並べ替えることができると思います。あなたはそれのためにアニーソーティングアルゴリズムを使うことができます。

"1" <" 10" <"100"<"11"..。

于 2010-08-01T13:06:01.157 に答える
1

編集：私はそれが連続した範囲であることを逃しました。そういうわけで、配列のソートについて話しているすべての答えは間違っており（基数ソートのようなものであるという質問で述べられているあなたの考えを含む）、TrueSoftの答えは正しいです。

基数ソートと同じですが、数字が逆の順序でソートされているだけです

よくわかります:-)実際にそのようにすると、おかしなことに、MSD基数ソートと呼ばれます。

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

非常に簡単に実装することも、多くの高度なテクノロジーとファンファーレを使用して実装することもできます。ほとんどのプログラミング言語では、特定の例はわずかな困難に直面しています。整数の自然なストレージ形式から10進数を抽出することは、特に高速な操作ではありません。これを無視して、最終的にどのくらいの時間がかかるかを確認する（推奨）か、並べ替える前にすべての数値を10進文字列に変換することでさらにファンファーレを追加できます。

もちろん、基数ソートとして実装する必要はありません。適切なコンパレータを使用して比較ソートアルゴリズムを使用できます。たとえば、Cでは、次のものがqsortでの使用に適しています（私がそれを台無しにした場合を除く）。

int lex_compare(void *a, void *b) {
    char a_str[12];  // assuming 32bit int
    char b_str[12];
    sprintf(a_str, "%d", *(int*)a);
    sprintf(b_str, "%d", *(int*)b);
    return strcmp(a_str,b_str);
}

多くの繰り返し作業を行うため、それほど効率的ではありませんが、簡単です。

于 2010-08-01T13:14:44.027 に答える
1

それらを文字列に変換したくないが、リストの余分なコピーを保存するのに十分なスペースがある場合は、コピー内の要素よりも小さい 10 の最大乗数を保存します。これはおそらくループで行うのが最も簡単です。x元の配列と 10 のべき乗を呼び出しますy。

int findPower(int x) {
   int y = 1;
   while (y * 10 < x) {
      y = y * 10;
   }
   return y;
}

それらを直接計算することもできます

y = exp10(floor(log10(x)));

しかし、反復は浮動小数点との変換よりも高速である可能性があると思います。

ith 要素とjth 要素を比較するには

bool compare(int i, int j) {
  if (y[i] < y[j]) {
    int ti = x[i] * (y[j] / y[i]);
    if (ti == x[j]) {
      return (y[i] < y[j]);  // the compiler will optimize this
    } else {
      return (ti < x[j]);
    }
  } else if (y[i] > y[j]) {
    int tj = x[j] * (y[i] / y[j]);
    if (x[i] == tj) {
      return (y[i] < y[j]);  // the compiler will optimize this
    } else {
      return (x[i] < tj);
    }
  } else {
     return (x[i] < x[j];
  }
}

ここで行われているのは、小さい方の数字に適切な 10 のべき乗を掛けて、2 つの数字の桁数を等しくし、それらを比較することです。2 つの変更された数値が等しい場合は、桁の長さを比較します。

y 配列を格納するスペースがない場合は、各比較でそれらを計算できます。

一般に、事前に最適化された数字変換ルーチンを使用する方がよいでしょう。

于 2010-08-01T13:47:27.570 に答える