私たちは話し合いました C の qsort()。 C++ STL は、ベクトルまたは配列 (ランダム アクセスの項目) をソートする同様の関数 sort を提供します。
通常、2 つのパラメータを取ります。最初のパラメータは、ソートを開始する必要がある配列/ベクトルのポイントで、2 番目のパラメータは、配列/ベクトルをソートするまでの長さです。 3 番目のパラメータはオプションで、要素を辞書順に並べ替える場合などに使用できます。
デフォルトでは、sort() 関数は要素を昇順に並べ替えます。
以下は、sort() の動作を示す簡単なプログラムです。
CPP
// C++ program to demonstrate default behaviour of> // sort() in STL.> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >/*Here we take two parameters, the beginning of the> >array and the length n upto which we want the array to> >be sorted*/> >sort(arr, arr + n);> >cout <<>'
Array after sorting using '> >'default sort is :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; }> |
>
>出力
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
時間計算量: O(N log N)
補助スペース: ○(1)
降順に並べ替えるにはどうすればよいですか?
sort() は、要素を並べ替える順序を指定するために使用される 3 番目のパラメーターを取ります。 great() 関数を渡すと、降順で並べ替えることができます。この関数は、より大きな要素を前に置く方法で比較を行います。
CPP
// C++ program to demonstrate descending order sort using> // greater().> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >sort(arr, arr + n, greater<>int>>());>> 'Array after sorting :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; }> |
>
>出力
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
時間計算量: O(N log N)
補助スペース: ○(1)
指定された範囲内でのみ配列を並べ替えます。 このような種類の問題に対処するには、sort 関数内の範囲について言及するだけで済みます。
以下は上記のケースの実装です。
C++
// C++ program to demonstrate sort()> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 0, 1, 5, 8, 9, 6, 7, 3, 4, 2 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >// Sort the elements which lies in the range of 2 to> >// (n-1)> >sort(arr + 2, arr + n);> >cout <<>'Array after sorting :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; } // This code is contributed by Suruchi Kumari> |
>
>出力
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
時間計算量: O(N log N)
補助スペース: O(1)
で並べ替える方法 特定の順序ですか？
独自のコンパレーター関数を作成し、それを 3 番目のパラメーターとして渡すこともできます。この比較関数は値を返します。 bool に変換可能。これは基本的に、渡された最初の引数を渡された 2 番目の引数の前に配置する必要があるかどうかを示します。
例: 以下のコードでは、間隔 {6,8} と {1,9} が CompareInterval 関数 (コンパレーター関数) の引数として渡されるとします。 i1.first (=6) として
CPP
// A C++ program to demonstrate> // STL sort() using> // our own comparator> #include> using> namespace> std;> // An interval has a start> // time and end time> struct> Interval {> >int> start, end;> };> // Compares two intervals> // according to starting times.> bool> compareInterval(Interval i1, Interval i2)> {> >return> (i1.start } int main() { Interval arr[] = { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } }; int n = sizeof(arr) / sizeof(arr[0]); // sort the intervals in increasing order of // start time sort(arr, arr + n, compareInterval); cout << 'Intervals sorted by start time :
'; for (int i = 0; i cout << '[' << arr[i].start << ',' << arr[i].end << '] '; return 0; }> |
>
>出力
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
std::sort() の時間計算量 は：
SQLで複数のテーブルから選択する
- 最良のケース – O(N log N)
- 平均ケース – O(N log N)
- 最悪の場合 – O(N log N)
空間の複雑さ: O( log N) の補助スペースを使用する場合があります。
C++
#include> #include> using> namespace> std;> template> <>class> T>>> class> Comparator {>// we pass an object of this class as> >// third arg to sort function...> public>:> >bool> operator()(T x1, T x2)> >{> >return> x1 } }; template |
>
>出力
The array before sorting is : 1 5 8 9 6 7 3 4 2 0 The array after sorting is(asc) :0 1 2 3 4 5 6 7 8 9 The array after sorting is(desc) :9 8 7 6 5 4 3 2 1 0 The array after sorting is(asc but our comparator class) :0 1 2 3 4 5 6 7 8 9 The array after sorting is(asc but our comparator function) :0 1 2 3 4 5 6 7 8 9>
時間計算量: O(N log N)
補助スペース: ○(1)