C++の別の配列で定義された順序に従って配列を並べ替えます
このセクションでは、別のソートの問題が発生します。 2つの配列A1とA2があるとします。要素間の相対的な順序がA2の場合と同じになるように、A1を並べ替える必要があります。一部の要素がA2に存在しない場合、それらはソートされた要素の後に追加されます。 A1とA2が次のようになっていると仮定します-
A1 = {2, 1, 2, 1, 7, 5, 9, 3, 8, 6, 8} A2 = {2, 1, 8, 3}
ソート後、A1は以下のようになります-
A1 = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}
この問題を解決するために、カスタム比較メソッドを作成します。このメソッドは、要素を比較して配列に配置します。比較ロジックは以下のようになります-
- num1とnum2の両方がA2にある場合、A2のインデックスが低い数値は、他の数値よりも小さいものとして扱われます。
- num1またはnum2のいずれかがA2に存在する場合、その数は、A2には存在しないもう一方よりも小さいものとして扱われます。
- 両方がA2に存在しない場合は、自然順序付けが使用されます。
アルゴリズム
compare(num1, num2): Begin if both num1 and num2 are present in A2, then return index of num1 – index of num2 else if num1 is not in A2, then return -1 else if num2 is not in A1, then return 1 else num1 – num2 End
例
#include<iostream> #include<algorithm> using namespace std; int size = 5; int A2[5]; //global A2 will be used in compare function int search_index(int key){ int index = 0; for(int i = 0; i < size; i++){ if(A2[i] == key) return i; } return -1; } int compare(const void *num1, const void *num2){ int index1 = search_index(*(int*)num1); int index2 = search_index(*(int*)num2); if (index1 != -1 && index2 != -1) return index1 - index2; else if (index1 != -1) return -1; else if (index2 != -1) return 1; else return (*(int*)num1 - *(int*)num2); } main(){ int data[] = {2, 1, 2, 1, 7, 5, 9, 3, 8, 6, 8}; int n = sizeof(data)/sizeof(data[0]); int a2[] = {2, 1, 8, 3}; int n2 = sizeof(a2)/sizeof(a2[0]); for(int i = 0; i<n2; i++){ A2[i] = a2[i]; } qsort(data, n, sizeof(int), compare); for(int i = 0; i<n; i++){ cout << data[i] << " "; } }
出力
2 2 1 1 8 8 3 5 6 7 9
-
カウントソートを実装するC++プログラム
カウントソートは安定したソート手法であり、少数のキーに従ってオブジェクトをソートするために使用されます。キー値が同じキーの数をカウントします。この並べ替え手法は、異なるキー間の差がそれほど大きくない場合に効率的です。そうでない場合は、スペースが複雑になる可能性があります。 ソート手法のカウントの複雑さ 時間計算量:O(n + r) スペースの複雑さ:O(n + r) 入力 −ソートされていないデータのリスト:2 5 6 2 3 10 3 6 7 8 出力 −並べ替え後の配列:2 2 3 3 5 6 6 7 8 10 アルゴリズム countingSort(array、
-
シェーカーソートを実行するC++プログラム
シェーカーソートは、指定されたデータをソートするために使用されます。シェーカーソートは、バブルソートとは異なり、配列を両方向に並べ替えます。このアルゴリズムの最悪の複雑さはO(n ^ 2)です。 アルゴリズム Begin ShakerSort() function has ‘arr’ the array of data and ‘n’ the number of values, in the argument list. // Implement Sorting algorithm using