Sort An Array Problem


Description

LeetCode Problem 912.

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

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 5 * 10^4
  • -5 * 10^4 <= nums[i] <= 5 * 10^4


Sample C++ Code using Quick Sort

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
class Solution {
public:
    int partition(vector<int> &nums, int i, int j) {
        int pivotIndex = i;
        int end = j;
        i++;
        while (i <= j) {
            while (i <= end && nums[i] < nums[pivotIndex]) i++;
            while (j >= pivotIndex && nums[j] > nums[pivotIndex]) j--;
            if (i <= j) {
                swap(nums[i++], nums[j--]);
            }
        }
        swap(nums[pivotIndex], nums[j]);
        return j;
    }
    
    void quickSort(vector<int> &nums, int l, int r) {
        if (l < r) {
            // swapping element at index l with element at random index
            swap(nums[l + rand() % (r -l + 1)], nums[l]);
            int mid = partition(nums, l, r);
            quickSort(nums, l, mid - 1);
            quickSort(nums, mid + 1, r);
        }
    }
    
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};




Related Posts

Sum Of Subsequence Widths Problem

LeetCode 891. The width of a sequence is the difference...

Sort An Array Problem

LeetCode 912. Given an array of integers nums, sort the...

Smallest Range II Problem

LeetCode 910. You are given an integer array nums and...

Reordered Power Of 2 Problem

LeetCode 869. You are given an integer n. We reorder...

Reorder Data In Log Files Problem

LeetCode 937. You are given an array of logs. Each...

Minimum Increment To Make Array Unique Problem

LeetCode 945. You are given an integer array nums. In...