[Python] Quick Sort with Optimization
Implementation 1: Quick Sort (Using auxiliary space - easy to implement)\n- Firstly, we pick pivot as a random number.\n- We particle nums arrays into 3 section
**Implementation 1: Quick Sort (Using auxiliary space - easy to implement)**\n- Firstly, we pick pivot as a random number.\n- We particle `nums` arrays into 3 section:\n    - Left: All elements < pivot\n     - Mid: All elements == pivot\n     - Right: All elements > pivot\n```python\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        return self.quickSort(nums)\n\n    def quickSort(self, nums):\n        if len(nums) <= 1:\n            return nums\n\n        pivot = random.choice(nums)\n        lesser, equal, greater = [], [], []\n        for num in nums:\n            if num < pivot:\n                lesser.append(num)\n            elif num == pivot:\n                equal.append(num)\n            else:\n                greater.append(num)\n        \n        return self.quickSort(lesser) + equal + self.quickSort(greater)\n        \n```\nComplexity:\n- Time: `O(NlogN)`, where `N` is length of nums array. `O(N^2)` in the worst case, in case random value always the maximum or the minimum elements in the array, and it\'s impossible!\n- Space: `O(N)`\n---\n**Implementation 2: Quick Sort (in place)**\n- Firstly, we pick pivot as a random number.\n- We particle `nums` arrays into 3 section:\n    - Left: All elements < pivot\n     - Mid: All elements == pivot\n     - Right: All elements > pivot\n```python\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        self.quickSort(nums, 0, len(nums) - 1)\n        return nums\n\n    def quickSort(self, nums, left, right):\n        if left >= right:\n            return\n\n        pivot = nums[random.randint(left, right)]\n        i, j = left, right\n        while i <= j:\n            while i < right and nums[i] < pivot: # Find first i such that nums[i] >= pivot\n                i += 1\n            while j > left and nums[j] > pivot: # Find first j such that nums[j] <= pivot\n                j -= 1\n            if i <= j:\n                nums[i], nums[j] = nums[j], nums[i]\n                i += 1\n                j -= 1\n\n        self.quickSort(nums, left, j) # nums[left..j] are elements < pivot\n        self.quickSort(nums, i, right) # nums[i..right] are elements > pivot\n```\nComplexity:\n- Time: `O(NlogN)`, where `N` is length of nums array. `O(N^2)` in the worst case, in case random value always the maximum or the minimum elements in the array, and it\'s impossible!\n- Space: `O(logN)`, it\'s the depth of recursion stack memory
['Quickselect', 'Python3']