C++ での 2D ベクトルの並べ替え |セット 2 (行と列の降順)
以下のセット 1 で 2D ベクトルをソートするいくつかのケースについて説明しました。 C++ での 2D ベクトルの並べ替え |セット 1 (行と列ごと) この記事ではさらに多くのケースについて説明します ケース 3 : 2D ベクトルの特定の行を降順に並べ替える このタイプの並べ替えでは、2D ベクトルの選択された行が降順に配置されます。これは、sort() を使用し、1D ベクトルの反復子を引数として渡すことによって実現されます。
CPP // C++ code to demonstrate sorting of a // row of 2D vector in descending order #include #include // for 2D vector #include // for sort() using namespace std ; int main () { // Initializing 2D vector 'vect' with // values vector & lt ; vector & lt ; int & gt ; & gt ; vect {{ 3 5 1 } { 4 8 6 } { 7 2 9 }}; // Number of rows; int m = vect . size (); // Number of columns (Assuming all rows // are of same size). We can have different // sizes though (like Java). int n = vect [ 0 ]. size (); // Displaying the 2D vector before sorting cout & lt ; & lt ; & quot ; The Matrix before sorting 1 st row is : n & quot ;; for ( int i = 0 ; i & lt ; m ; i ++ ) { for ( int j = 0 ; j & lt ; n ; j ++ ) cout & lt ; & lt ; vect [ i ][ j ] & lt ; & lt ; & quot ; & quot ;; cout & lt ; & lt ; endl ; } // Use of 'sort()' for sorting first row sort ( vect [ 0 ]. rbegin () vect [ 0 ]. rend ()); // Displaying the 2D vector after sorting cout & lt ; & lt ; & quot ; The Matrix after sorting 1 st row is : n & quot ;; for ( int i = 0 ; i & lt ; m ; i ++ ) { for ( int j = 0 ; j & lt ; n ; j ++ ) cout & lt ; & lt ; vect [ i ][ j ] & lt ; & lt ; & quot ; & quot ;; cout & lt ; & lt ; endl ; } return 0 ; }
出力：
The Matrix before sorting 1st row is: 3 5 1 4 8 6 7 2 9 The Matrix after sorting 1st row is: 5 3 1 4 8 6 7 2 9
の 時間の複雑さ このアルゴリズムの値は O(n log n) です。ここで、n はベクトルのサイズです。
の 空間の複雑さ 追加のスペースが使用されないため、このアルゴリズムの値は O(1) です。
ケース 4: 特定の列に基づいて 2D ベクトル全体を降順に並べ替えます。 このタイプのソートでは、2D ベクトルは、選択された列に基づいて降順に完全にソートされます。たとえば、選択した列が 2 番目の場合、2 番目の列で最大値を持つ行が 1 行目になり、2 番目の列で 2 番目に大きい値が 2 行目になります。 {3 5 1} {4 8 6} {7 2 9};この行列を 2 番目の列でソートすると、{4 8 6} が得られます。 // 2 番目の列で最大値を持つ行 {3 5 1} // 2 番目の列で 2 番目に大きい値を持つ行 {7 2 9} これは、ユーザー定義の明示的関数への呼び出しとして sort() の 3 番目の引数を渡すことで実現されます。
// C++ code to demonstrate sorting of a // 2D vector on basis of a column in // descending order #include #include // for 2D vector #include // for sort() using namespace std ; // Driver function to sort the 2D vector // on basis of a particular column in // descending order bool sortcol ( const vector & lt ; int & gt ; & amp ; v1 const vector & lt ; int & gt ; & amp ; v2 ) { return v1 [ 1 ] & gt ; v2 [ 1 ]; } int main () { // Initializing 2D vector 'vect' with // values vector & lt ; vector & lt ; int & gt ; & gt ; vect {{ 3 5 1 } { 4 8 6 } { 7 2 9 }}; // Number of rows; int m = vect . size (); // Number of columns (Assuming all rows // are of same size). We can have different // sizes though (like Java). int n = vect [ 0 ]. size (); // Displaying the 2D vector before sorting cout & lt ; & lt ; & quot ; The Matrix before sorting is : n & quot ;; for ( int i = 0 ; i & lt ; m ; i ++ ) { for ( int j = 0 ; j & lt ; n ; j ++ ) cout & lt ; & lt ; vect [ i ][ j ] & lt ; & lt ; & quot ; & quot ;; cout & lt ; & lt ; endl ; } // Use of 'sort()' for sorting on basis // of 2nd column in descending order sort ( vect . begin () vect . end () sortcol ); // Displaying the 2D vector after sorting cout & lt ; & lt ; & quot ; The Matrix after sorting is : n & quot ;; for ( int i = 0 ; i & lt ; m ; i ++ ) { for ( int j = 0 ; j & lt ; n ; j ++ ) cout & lt ; & lt ; vect [ i ][ j ] & lt ; & lt ; & quot ; & quot ;; cout & lt ; & lt ; endl ; } return 0 ; }
出力：
The Matrix before sorting is: 3 5 1 4 8 6 7 2 9 The Matrix after sorting is: 4 8 6 3 5 1 7 2 9
の 時間の複雑さ このアルゴリズムの O(NlogN) ここで、N は 2D ベクトルの要素の数です。これは、O(NlogN) 時間で実行される sort() 関数の使用が原因です。
の 空間の複雑さ このアルゴリズムの ○(1) 追加のデータ構造が使用されないためです。
