2

配列の最小値と最大値の両方を考慮し、それらを両端に配置する選択ソートの修正版を作成しました

アルゴリズムは次のように機能します

1. Find the minimum and the maximum value in the list.
2. Swap the minimum value with the value in the first position.
3. Swap the maximum value with the value in the last position.
4. Repeat the steps above for the remainder of the list 
(starting at the second position and ending at the second to 
 last position and narrowing the range of positions examined 
 from both ends of the array each time).

残念ながら、上記は重複値を持つ配列に対して予期しない結果を示しています。

例えば、

[9, 37, 12, 1, 13, 31, 5, 37, 36, 29, 19, 22, 20, 15, -1, 23]

にソートされました

[-1, 1, 5, 9, 12, 13, 15, 19, 20, 22, 23, 29, 31, 37, 36, 37]

実際、ここでの主な問題は、単純に重複に関してだけでなく、一般的にアルゴリズムが配列の後半部分の要素に対して適切なソートを行っていないことです。

ここに私の疑似コードがあります

    int i=0;
    while(i<=(arr.length-i-1)) {
      int minIndex = i;
      int maxIndex=arr.length-i-1; 
      for (int j = i+1; j <=arr.length-i-1; j++) {

       if (arr[j] <=arr[minIndex]) {
         minIndex = j;      
         } 
       if(arr[j]>=arr[maxIndex]){
          maxIndex = j; 
         }
      }
      swap(arr, i, minIndex);
      swap(arr, (arr.length-i-1), maxIndex); 
    i++;
    }

編集これは、アルゴリズムと対話する唯一のものである私のコードのスワップ部分です。変わらないと思いますが一応載せておきます

 private static void swap(int[] arr, int oldIndex, int newIndex){

    int temp=arr[oldIndex];
    arr[oldIndex]=arr[newIndex];
    arr[newIndex]=temp;
 }
4

5 に答える 5

3

問題が発生するiのは、たまたまmaxIndexです。これを修正するには、次を追加する必要があります。

swap(arr, i, minIndex);
if(i == maxIndex) {
     maxIndex = minIndex;
}
swap(arr, (arr.length-i-1), maxIndex);

@workを参照してください

于 2012-04-17T11:55:32.290 に答える
2

問題は、最大値が反復の最小位置から始まる場合です。問題の配列で 2 回目のループを考えてみましょう。

-1,37,12,1,13,31,5,23,36,29,19,22,20,15,9,37

i は 1、len-i-1 は 14 です。ループ後、maxindex は 1、minIndex は 3 です。

したがって、1 (i) と 3 (minIndex) を交換します。

-1,1,12,37,13,31,5,23,36,29,19,22,20,15,9,37

そして、14 (len-i-1) と 1 (maxIndex):

-1,9,12,37,13,31,5,23,36,29,19,22,20,15,1,37

おっとっと。基本的に、両方のスワップを並行して行う必要があります。

編集2 つのオーバーラップするスワップの場合、並列処理はあまり役に立ちません。これは、各スワップが配列スロットの 1 つに異なる値を入れたいからです。競合を解決する必要があります。@codaddic のソリューションはうまく機能すると思います。

于 2012-04-17T11:49:36.183 に答える
0

内側の for ループの終了条件に off-by-one エラーがあります。

  for (int j = i+1; j <=arr.length-i-1; j++) {

の代わりに開始するのと同じ理由で、<それは ではなく である必要があります。<=i+1i

文体上の推奨事項として、arr.length - i - 1変数にも値を格納します。これは、コード内で値が 4 回出現するためです。

EDIT : このエラーが問題の原因ではないことを確認しました。

于 2012-04-17T11:26:23.497 に答える
0

あなたはあまりにも多くのスワップを行っていると思います。つまり、実際に新しい最小値または最大値を見つけたかどうかに関係なく、スワップを行っています。また、両方のテストを実行する必要はありません (最小値と最大値の両方を実行することはできません。ただし、平等の些細なケースを除きます。この場合、それらがどちらの順序であるかは問題ではありません...)。

以下はあなたのアルゴリズムをよりよく表していると思います：

int arrayLength = arr.length;
for (int i=0; i<arrayLength; i++){
  for (int j=i+1; j<arrayLength; j++){
    int v = arr[j];
    if (v < arr[i]){
      swap(arr, i, j);
    } else if (v > arr[(arrayLength -1)]){
      swap(arr, (arrayLength -i-1), j);
    }
  }
}

ただし、配列を介してトップレベルの反復を行うと、これらはすべて最小値の検索によって検出されるため、実際には最大値でテストを実行して最後までスワップする必要はありません。

int arrayLength = arr.length;
for (int i=0; i<arrayLength; i++){
  for (int j=i+1; j<arrayLength; j++){
    int v = arr[j];
    if (v < arr[i]){
      swap(arr, i, j);
    } 
  }
}

より効率的になります。

編集：他の回答を確認した後、この種のスワップを並行して行うことに関するMark Reedの回答を取り上げます-それを除いて、必要に応じてスワップを行うことをお勧めします。

于 2012-04-17T12:18:53.557 に答える
-2

コメントのように、最初のスワップはうまくいきますが、2 回目のスワップは問題になります。

maxindex 変数が i にある場合、最小項は正しく配置されましたが、最大項が失われました。これは、 をチェックする特別な規定を追加することで対処できますif(i==maxterm)。この特殊なケースは、最初のスワップを通常どおりに行い、次に maxterm と minterm の場所の 2 回目のスワップを行うことで処理できます。配列を 0 からarray.length-1

両側でソートしているため、0 から (array.length-1)/2 までトラバースすることをお勧めします。終了部分は開始部分と同様に既にソートされていますが、余分な反復を行うのはなぜですか? 私が提案した修正を加えたまったく同じプログラムを作成しました。これは、数値が既にソートされているかどうかもチェックし、ループをすぐに終了します。

于 2017-03-11T14:13:23.900 に答える