C++에서 배열 정렬

정수 배열이 있다고 가정합니다. 오름차순으로 정렬해야 합니다. 따라서 배열이 [5,2,3,1]과 같으면 결과는 [1,2,3,5]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 파티션이라는 하나의 방법을 만드십시오. 이것은 배열, 낮음 및 높음을 취합니다.

• 피벗 설정 :=낮음

• 낮은 범위에서 높은 범위의 i에 대해 – 1

  • nums[i]

• 숫자[피벗] 및 숫자[높음] 교환

• sortArr()이라는 메서드를 정의합니다. 이 메서드는 배열(낮음 및 높음)을 취합니다.

• 낮음>=높으면 반환

• partitionIndex :=파티션(숫자, 낮음, 높음)

• sortArr(숫자, 낮음, 파티션 인덱스 – 1)

• sortArr(숫자, 파티션 인덱스 + 1, 높음)

• 낮음과 높음을 0으로 전달하고 arr의 크기를 1로 전달하여 기본 메서드에서 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]