C++で配列を並べ替える

整数の配列があるとします。それらを昇順で並べ替える必要があります。したがって、配列が[5,2,3,1]のような場合、結果は[1,2,3,5]

これを解決するには、次の手順に従います-

• パーティションと呼ばれる1つのメソッドを作成します。これには、配列、低、高が必要です

• ピボットを設定：=低

• 低から高の範囲のiの場合– 1

  • nums [i]

• nums[pivot]とnums[high]

  を交換します

• sortArr（）と呼ばれるメソッドを定義します。これは、配列、低、高を取ります

• 低>=高の場合、戻る

• partitionIndex：=partition（nums、low、high）

• sortArr（nums、low、partitionIndex – 1）

• sortArr（nums、partitionIndex + 1、high）

• ローとハイを0、サイズをarr – 1として渡すことにより、mainメソッドからsortArr（）を呼び出します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   int partition(vector <int>& nums, int low, int high){
      int pivot = low;
      for(int i = low; i < high; i++){
         if(nums[i] < nums[high]){
            swap(nums[i], nums[pivot]);
            pivot++;
         }
      }
      swap(nums[pivot], nums[high]);
      return pivot;
   }
   void sortArr(vector <int>& nums, int low, int high){
      if(low >= high) return;
      int partitionIndex = partition(nums, low, high);
      sortArr(nums, low, partitionIndex - 1);
      sortArr(nums, partitionIndex + 1, high);
   }
   vector<int> sortArray(vector<int>& nums) {
      sortArr(nums, 0, nums.size() - 1);
      return nums;
   }
};
main(){
   vector<int> v1 = {5,2,3,1};
   Solution ob;
   print_vector(ob.sortArray(v1));
}

入力

[5,2,3,1]

出力

[1,2,3,5]