Sort an Array ใน C++

คำอธิบายปัญหา

เรียงลำดับอาร์เรย์จำนวนเต็มจากน้อยไปมาก

ตัวอย่าง: [5,2,3,1] → [1,2,3,5]

วิธีแก้ปัญหา (Quick Sort Implementation)

ใช้ Quick Sort แบบ recursive พร้อม partition แบบ Lomuto

1. partition: เลือก pivot = ค่าสุดท้าย, ย้ายค่าน้อยกว่า pivot ไปซ้าย
2. recursive sort ส่วนซ้ายและขวา

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int partition(vector<int>& nums, int low, int high) {
        int pivot = nums[high];
        int i = low - 1;
        for(int j = low; j < high; j++) {
            if(nums[j] < pivot) {
                i++;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i+1], nums[high]);
        return i + 1;
    }
    
    void quickSort(vector<int>& nums, int low, int high) {
        if(low < high) {
            int pi = partition(nums, low, high);
            quickSort(nums, low, pi - 1);
            quickSort(nums, pi + 1, high);
        }
    }
    
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

int main() {
    vector<int> v1 = {5,2,3,1};
    Solution ob;
    vector<int> res = ob.sortArray(v1);
    for(int x : res) cout << x << " ";
    return 0;
}

อินพุต

[5,2,3,1]

เอาต์พุต

[1,2,3,5]