C配列の並べ替えのヒント

algorithm c sorting
C配列の並べ替えのヒント
       a=[1,3,6,7,1,2]

これは、次の配列をソートするための最良のソート手法であり、重複する場合はそれらを処理する方法です。 また、これはすべての最高のソート手法です。

 void BubbleSort(int a[], int array_size)
 {
 int i, j, temp;
 for (i = 0; i < (array_size - 1); ++i)
 {
      for (j = 0; j < array_size - 1 - i; ++j )
      {
           if (a[j] > a[j+1])
           {
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
           }
      }
 }
 }

  27  13


ベストアンサー

Cでは、組み込みの `qsort`コマンドを使用できます。

int compare( const void* a, const void* b)
{
     int int_a = * ( (int*) a );
     int int_b = * ( (int*) b );

     if ( int_a == int_b ) return 0;
     else if ( int_a < int_b ) return -1;
     else return 1;
}

qsort( a, 6, sizeof(int), compare )

参照:http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

” ” ‘

質問の2番目の部分に答えます。最適な(比較ベースの)ソートアルゴリズムは、O(n log(n))比較で実行されるアルゴリズムです。 このプロパティを持つもの(クイックソート、マージソート、ヒープソートなど)がいくつかありますが、使用するものはユースケースによって異なります。

補足事項として、データについて何か知っている場合は、O(n log(n))よりも良い結果が得られることがあります-http://en.wikipedia.org/wiki/Radix_sort[Radix Sort]のウィキペディアの記事を参照してください

43


あなたの特定のケースでは、最速のソートはおそらくhttps://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array[this answer]で説明されているものです。 6つのintの配列に対して正確に最適化され、ソートネットワークを使用します。 ライブラリqsortよりも* 20倍*(x86で測定)高速です。 並べ替えネットワークは、固定長配列の並べ替えに最適です。 命令の固定シーケンスであるため、ハードウェアで簡単に実装することもできます。

一般的に言えば、特殊なケース向けに最適化された多くのソートアルゴリズムがあります。 ヒープソートやクイックソートなどの汎用アルゴリズムは、アイテムの配列のインプレースソート用に最適化されています。 これらはO(n.log(n))の複雑さをもたらします。nはソートするアイテムの数です。

ライブラリー関数qsort()は非常によくコード化されており、複雑さの点で効率的ですが、ユーザーが提供する比較関数の呼び出しを使用します。この呼び出しにはかなりのコストがかかります。

非常に大量のデータをソートするために、アルゴリズムはディスクとの間のデータのスワッピングにも注意する必要があります。これはデータベースに実装されている種類のソートであり、そのようなニーズがある場合は、データベースにデータを入れてビルトインソート。

12


依存する

それはさまざまなものに依存します。 ただし、一般的にhttp://en.wikipedia.org/wiki/Divide_and_conquer_algorithm[Divide-and-Conquer] / dichotomicアプローチを使用するアルゴリズムは、問題のソートに適しています彼らは興味深い平均ケースの複雑さを提示します。

基本

どのアルゴリズムが最適に機能するかを理解するには、http://en.wikipedia.org/wiki/Computational_complexity_theory [algorithms complex]およびhttp://en.wikipedia.org/wiki/Big_O_notation[big-O notation]の基本的な知識が必要です。ので、http://en.wikipedia.org/wiki/Best,_worst_and_average_case [平均ケース、ベストケース、最悪ケースのシナリオ]の観点からそれらの評価を理解できます。 必要に応じて、http://en.wikipedia.org/wiki/Sorting_algorithm#Stability [ソートアルゴリズムの安定性]にも注意を払う必要があります。

たとえば、通常、効率的なアルゴリズムはクイックソートです。 ただし、quicksortに完全に反転したリストを指定すると、パフォーマンスが低下します(その場合、単純な選択ソートの方がパフォーマンスが向上します!)。 リストの事前分析を実行する場合、シェルソートは通常、クイックソートを補完するものでもあります。

分割統治アプローチを使用した「高度な検索」については、以下をご覧ください。

そして、これらのより単純なアルゴリズムのためのより直接的なアルゴリズム:

さらに

上記は、開始時の通常の容疑者ですが、他にも無数の人がいます。

Rが指摘したように コメントと彼の答えのクリスによって、あなたはhttp://en.wikipedia.org/wiki/Heapsort[HeapSort]を見てみたいかもしれません。これはクイックソートよりも理論的に優れたソートの複雑さを提供します(しかし、多くの場合、実際の設定ではより良くなります)。 また、バリアントとhttp://en.wikipedia.org/wiki/Hybrid_algorithm [ハイブリッドアルゴリズム](例: TimSort)。

5


一般的に、すべての最適なソート手法は配列のサイズに依存します。 マージソートは、Big-Oアルゴリズムに従ってスペースと時間の複雑さを管理するため、何よりも優れています(これは、大きな配列に適しています)。

2


いくつかの変更を行いたい:Cでは、組み込みの_qsort_コマンドを使用できます。

int compare( const void* a, const void* b)
{
   int int_a = * ( (int*) a );
   int int_b = * ( (int*) b );

   // an easy expression for comparing
   return (int_a > int_b) - (int_a < int_b);
}

qsort( a, 6, sizeof(int), compare )

1


タイトルとURLをコピーしました