13

例えば：int A[] = {3,2,1,2,3,2,1,3,1,2,3};

この配列を効率的にソートするには?

これは就職の面接用です。疑似コードだけが必要です。

4

16 に答える 16

10

それをソートする有望な方法は、count sortのようです。Richard Buckland によるこの講義、特に 15:20 からの部分は一見の価値があります。

カウントソートと同様ですが、ドメインを表す配列を作成し、そのすべての要素を 0 に初期化してから、配列を反復処理してこれらの値をカウントすることをお勧めします。ドメイン値の数がわかったら、それに応じて配列の値を書き換えることができます。このようなアルゴリズムの複雑さは O(n) になります。

これは、私が説明した動作を備えた C++ コードです。ただし、その複雑さは実際には O(2n) です。

int A[] = {3,2,1,2,3,2,1,3,1,2,3};
int domain[4] = {0};

// count occurrences of domain values - O(n):  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
    domain[A[i]]++;

// rewrite values of the array A accordingly - O(n):    
for (int k = 0, i = 1; i < 4; ++i)
    for (int j = 0; j < domain[i]; ++j)
        A[k++] = i;

ドメイン値に大きな違いがある場合、ドメインを配列として格納するのは非効率的であることに注意してください。その場合、 map を使用する方がはるかに良い考えです (指摘してくれたabhinavに感謝します)。ドメイン値の格納に使用する C++ コードはstd::map次のとおりです - 出現回数のペア:

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000};
std::map<int, int> domain;

// count occurrences of domain values:  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
{
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]);
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first))
        keyItr->second++; // next occurrence 
    else
        domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence
}

// rewrite values of the array A accordingly:    
int k = 0;
for (auto i = domain.begin(); i != domain.end(); ++i)
    for (int j = 0; j < i->second; ++j)
        A[k++] = i->first;

std::map（上記のコードでより効率的に使用する方法があれば、私に知らせてください）

于 2012-06-16T21:52:54.003 に答える
9

コンピューター サイエンスの標準的な問題:オランダの国旗の問題 リンクを参照してください。

于 2012-06-17T15:04:14.717 に答える
4

各数値をカウントし、そのカウントに基づいて新しい配列を作成します... O(n) の時間の複雑さ

 int counts[3] = {0,0,0};
 for(int a in A)
  counts[a-1]++;
 for(int i = 0; i < counts[0]; i++)
  A[i] = 1;
 for(int i = counts[0]; i < counts[0] + counts[1]; i++)
  A[i] = 2;
 for(int i = counts[0] + counts[1]; i < counts[0] + counts[1] + counts[2]; i++)
  A[i] = 3;
于 2012-06-16T21:46:04.567 に答える
3

質問は、bucket sortを使用することを意図していると思います。値の数が少ない場合、バケット ソートは、より一般的に使用されるクイックソートまたはマージソートよりもはるかに高速になる可能性があります。

于 2012-06-16T21:42:45.357 に答える
3

ロバートが述べたように、この状況ではバスケットソート (またはバケットソート) が最適です。

次のアルゴリズムも追加します (実際には busket ソートに非常に似ています)。

[疑似コードはJavaスタイル]

を作成し、HashMap<Integer, Interger> map配列を循環します。

for (Integer i : array) {
    Integer value = map.get(i);
    if (value == null) {
        map.put(i, 1);
    } else {
        map.put(i, value + 1);
    }
 }
于 2012-06-16T21:52:09.967 に答える
3

問題の説明: n 個のバケットがあり、各バケットには 1 つのコインが含まれています。コインの値は 5 または 10 または 20 のいずれかです。この制限の下でバケットをソートする必要があります: 1. この 2 つの関数のみを使用できます: SwitchBaskets (Basket1 , Basket2) – 2 つのバスケットを切り替える GetCoinValue (Basket1) – 選択したバスケットのコインの値を返す 2. サイズ n の配列を定義できない 3. switch 関数をできるだけ使用しない。

O(n) の複雑さを持つ任意の言語で実装できる、私の単純な疑似コード ソリューション。

かごからコインを取り出します 1) 5 の場合 - 最初に押します。2) 20 の場合 - 最後になるように押します。3) 10 の場合 - そのままにしておきます。4) 並んでいる次のバケットを見てください。

編集: 要素を最初または最後の位置にプッシュできない場合、海賊版の実装にはマージソートが理想的です。それがどのように機能するかは次のとおりです。

マージ ソートは、既にソートされたリストを新しいソート済みリストにマージする容易さを利用します。2 つの要素 (つまり、1 と 2、次に 3 と 4...) を比較し、最初の要素が 2 番目の要素の後に来る場合はそれらを交換することから始めます。次に、結果として得られた 2 つのリストのそれぞれを 4 つのリストにマージし、それらの 4 つのリストをマージします。最後に 2 つのリストが最終的なソート済みリストにマージされるまで。ここで説明するアルゴリズムのうち、最悪の場合の実行時間は O(n log n) であるため、これは非常に大きなリストにうまくスケーリングできる最初のアルゴリズムです。マージ ソートは、プログラミング言語の標準的なソート ルーチンに使用されており、実用的な実装として比較的最近人気が高まっています。

于 2012-06-16T22:32:42.040 に答える
2

@ElYusubov に基づくグルーヴィーなソリューションを次に示しますが、Bucket(5) を最初にプッシュし、Bucket(15) を最後にプッシュする代わりに。ふるい分けを使用して、5 が最初に移動し、15 が最後に移動します。

バケットを end から現在の位置にスワップするたびに、end をデクリメントします。要素を再度確認する必要があるため、現在のカウンターをインクリメントしません。

array = [15,5,10,5,10,10,15,5,15,10,5]

    def swapBucket(int a, int b) {

        if (a == b) return; 
        array[a] = array[a] + array[b]
        array[b] = array[a] - array[b]
        array[a] = array[a] - array[b]

    }

def getBucketValue(int a) {
    return array[a];
}

def start = 0, end = array.size() -1, counter = 0;
// we can probably do away with this start,end but it helps when already sorted.

// start - first bucket from left which is not 5
while (start < end) {

    if (getBucketValue(start) != 5) break;
    start++;

}     

// end - first bucket from right whichis not 15
while (end > start) {

    if (getBucketValue(end) != 15) break;
    end--;

}

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1      

for (counter = start; counter < end;) {

    def value = getBucketValue(counter)

    if (value == 5) { swapBucket(start, counter); start++; counter++;}
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter
    else { counter++; }

}

for (key in array) { print " ${key} " }
于 2012-06-22T17:27:08.723 に答える
2

私は質問を理解していると思います-O（1）スペースのみを使用でき、セルを交換することによってのみ配列を変更できます。（したがって、配列で2つの操作を使用できます-スワップと取得）

私の解決策：

2 つのインデックス ポインターを使用します。1 つは最後の 1 の位置、もう 1 つは最後の 2 の位置です。

ステージ i では、i 番目のセルをチェックするよりも、配列が既に 1 から i-1 にソートされていると想定します。A[i] == 3 の場合、何もしません。A[i] == 2 の場合、最後の 2 つのインデックスの後のセルと交換します。A[i] == 1 の場合、最後の 2 つのインデックスの後のセルと交換し、最後の 2 つのインデックスの後のセル (1 を含む) を最後の 1 つのインデックスの後のセルと交換します。

これが主なアイデアであり、細部に注意を払う必要があります。全体的な O(n) の複雑さ。

于 2012-06-19T21:01:52.020 に答える
1

ElYusububが提案したように、「値を遠端にプッシュする」を実装する方法は次のとおりです。

sort(array) {
  a = 0
  b = array.length
  # a is the first item which isn't a 1 
  while array[a] == 1
    a++
  # b is the last item which isn't a 3
  while array[b] == 3
    b--

  # go over all the items from the first non-1 to the last non-3
  for (i = a; i <= b; i++)
    # the while loop is because the swap could result in a 3 or a 1
    while array[i] != 2
      if array[i] == 1
        swap(i, a)
        while array[a] == 1
          a++
      else # array[i] == 3
        swap(i, b)
        while array[b] == 3
          b--

これは実際には最適なソリューションである可能性があります。わからない。

于 2012-06-21T12:59:42.050 に答える
1

たとえば、wikiを見てみましたか？- http://en.wikipedia.org/wiki/Sorting_algorithm

于 2012-06-16T21:44:59.733 に答える
1

このコードは c# 用です。

ただし、非言語/フレームワーク固有の方法で実装するには、アルゴリズムを考慮する必要があります。示唆されているように、バケットセットは効率的なものかもしれません。問題に関する詳細な情報を提供していただければ、最善の解決策を検討します。幸運を...

C# .NET のコード サンプルを次に示します。

int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 };
Array.Sort(intArray);
// write array
foreach (int i in intArray) Console.Write("{0}, ", i.ToString());
于 2012-06-16T21:53:57.203 に答える
1

これは --> を使用して非常に簡単に実行できます。

オランダ国旗アルゴリズム http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

1,2,3 を使用する代わりに、0,1,2 として使用します

于 2012-07-01T07:44:59.810 に答える
0

array に 2 つの数値しかないという問題を解決しましょう。[1,2,1,2,2,2,1,1]

最小スワップで 1 つのパス o(n) でソートできます。2 つのポインターが互いに出会うまで、左右から開始します。左の要素が大きい場合、左の要素を右と交換します。（ソート昇順）

3 つの数字 (k-1 パス) に対して、別のパスを実行できます。パス 1 で 1 を最終位置に移動し、パス 2 で 2 を移動しました。

def start = 0, end = array.size() - 1;

// Pass 1, move lowest order element (1) to their final position 
while (start < end) {
    // first element from left which is not 1
    for ( ; Array[start] ==  1 && start < end ; start++);
    // first element from right which IS 1
    for ( ; Array[end] != 1 && start < end ; end--);

    if (start < end) swap(start, end);
}     

// In second pass we can do 10,15

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions
于 2012-06-28T14:14:39.853 に答える
0 
def DNF(input,length):
    high = length - 1
    p = 0
    i = 0
    while i <= high:
            if input[i] == 0:
                    input[i],input[p]=input[p],input[i]
                    p = p+1
                    i = i+1
            elif input[i] == 2:
                    input[i],input[high]=input[high],input[i]
                    high = high-1
            else:
                    i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input
于 2013-08-06T04:51:59.167 に答える
-1 
//Bubble sort for unsorted array - algorithm
public void  bubleSort(int arr[], int n) { //n is the length of an array
    int temp;
    for(int i = 0; i <= n-2; i++){
        for(int j = 0; j <= (n-2-i); j++){
            if(arr[j] > arr[j +1]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j + 1] = temp;

            }
        }

    }
于 2012-07-05T13:36:21.960 に答える