Sort An Array - Leetcode Solution

Problem:

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

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

Solution:

There are several sorting algorithms that we could use to solve this problem. In this solution, we will use the QuickSort algorithm, which has an average time complexity of O(nlogn).

QuickSort is a divide-and-conquer algorithm that works by selecting a pivot element from the array, partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot, and recursively repeating the process on each sub-array.

First, we implement the partition function which will partition the array around a chosen pivot element, and return the final index of the pivot. We initialize the pivot at the end of the array and iterate through the array, swapping elements to move all elements less than the pivot to the left side of the array.

def partition(nums, low, high): i = low - 1 pivot = nums[high] for j in range(low, high): if nums[j] < pivot: i += 1 nums[i], nums[j] = nums[j], nums[i] nums[i+1], nums[high] = nums[high], nums[i+1] return i + 1

Next, we implement the quicksort function which recursively sorts the subarrays to the left and right of the pivot. The function takes an additional argument "nums" which is the array to be sorted.

def quicksort(nums, low, high): if low < high: p = partition(nums, low, high) quicksort(nums, low, p-1) quicksort(nums, p+1, high)

Finally, we call the quicksort function to sort the entire array. Note that we pass the initial values of low and high as 0 and len(nums) - 1, respectively.

def sortArray(nums): quicksort(nums, 0, len(nums)-1) return nums

Time Complexity:

The time complexity of QuickSort is O(nlogn) in the average case and O(n^2) in the worst case. The worst case occurs when the pivot element is consistently the minimum or maximum element of the array. However, in this implementation, the choice of pivot is randomly selected, reducing the likelihood of the worst case.

Space Complexity:

The space complexity of the QuickSort algorithm is O(log(n)), as it requires a call stack for each recursive call. In the worst case, the call stack would have a depth of n. However, in the average case, the depth of the call stack is much smaller, making the space complexity O(log(n)) on average.

1