Solution For Sort An Array

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.

Step by Step Implementation For Sort An Array

import java.util.*; 

class Solution {
    public int[] sortArray(int[] nums) {
        // check for empty or null array
        if (nums == null || nums.length == 0) {
            return nums;
        }
        
        // create a new array to return the sorted values
        int[] sortedArray = new int[nums.length];
        
        // create a min heap using the natural ordering of the array elements
        PriorityQueue minHeap = new PriorityQueue<>(nums.length);
        for (int i : nums) {
            minHeap.add(i);
        }
        
        // get the elements from the heap in sorted order and add them to the sorted array
        for (int i = 0; i < nums.length; i++) {
            sortedArray[i] = minHeap.poll();
        }
        
        return sortedArray;
    }
}

def sortArray(self, nums: List[int]) -> List[int]:
    
    # base case
    if len(nums) == 0:
        return []
    
    # choose pivot (can be random)
    pivot = nums[0]
    
    # initialize left and right arrays
    left = []
    right = []
    
    # put elements in left or right array depending on if they are less than or greater than the pivot
    for i in range(1, len(nums)):
        if nums[i] < pivot:
            left.append(nums[i])
        else:
            right.append(nums[i])
            
    # recursively call sortArray on left and right arrays
    left = self.sortArray(left)
    right = self.sortArray(right)
    
    # return the sorted array
    return left + [pivot] + right

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



// sort an array in ascending order
function sortArray(nums) {
    // sort the array in ascending order
    nums.sort(function(a, b){return a-b});
    return nums;
}

vector sortArray(vector& nums) {
    int n = nums.size();
    if (n == 0) return nums;
    int min = nums[0];
    int max = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < min) min = nums[i];
        if (nums[i] > max) max = nums[i];
    }
    int range = max - min + 1;
    vector counts(range);
    for (int i = 0; i < n; i++) {
        counts[nums[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < range; i++) {
        int count = counts[i];
        while (count-- > 0) {
            nums[index++] = i + min;
        }
    }
    return nums;
}

public class Solution {
    public int[] SortArray(int[] nums) {
        // Array to store the sorted elements
        int[] sortedArray = new int[nums.Length];
        
        // Variable to keep track of the current index in the sorted array
        int currentIndex = 0;
        
        // Loop through the input array
        for(int i = 0; i < nums.Length; i++) {
            // Variable to keep track of the current smallest element
            int currentSmallest = nums[i];
            
            // Variable to keep track of the index of the current smallest element
            int currentSmallestIndex = i;
            
            // Loop through the remaining elements in the input array
            for(int j = i + 1; j < nums.Length; j++) {
                // If the current element is smaller than the current smallest element, update the current smallest element
                if(nums[j] < currentSmallest) {
                    currentSmallest = nums[j];
                    currentSmallestIndex = j;
                }
            }
            
            // Swap the current smallest element with the element at the current index
            int temp = nums[i];
            nums[i] = currentSmallest;
            nums[currentSmallestIndex] = temp;
            
            // Add the current smallest element to the sorted array
            sortedArray[currentIndex] = currentSmallest;
            currentIndex++;
        }
        
        // Return the sorted array
        return sortedArray;
    }
}