Sort an Array

Posted by Bill on March 11, 2023

Sort an Array

Given an array of integers nums, sort the array in ascending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]


Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {

    public:
        vector<int> sortArray(vector<int>& nums) {
            quick_sort(nums, 0, nums.size() - 1);
            return nums;
        }

        void quick_sort(vector<int>& nums, int l, int r)
        {

            if (l < r)
            {

                int i = l, j = r, x = nums[l];
                while (i < j)
                {

                    while(i < j && nums[j] >= x)
                        j--;
                    if(i < j)
                        nums[i++] = nums[j];

                    while(i < j && nums[i] < x)
                        i++;
                    if(i < j)
                        nums[j--] = nums[i];
                }
                nums[i] = x;
                quick_sort(nums, l, i - 1);
                quick_sort(nums, i + 1, r);
            }
        }
};