912. Sort an Array

https://leetcode.com/problems/sort-an-array/

Python

Bubble Sort

• Time: O(N^2)
• Space: O(1)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for _ in range(n-1):
            for i in range(1, n):
                if nums[i-1] > nums[i]:
                    nums[i], nums[i-1] = nums[i-1], nums[i]
        return nums

Binary Search Tree

(Timelimit Exceed)

• Time: O(N)
• Space: O(N)

class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def build(node, val):
            if not node:
                return TreeNode(val=val)
            if node.val > val:
                node.left = build(node.left, val)
            else:
                node.right = build(node.right, val)
            return node


        root = TreeNode(val=nums.pop())
        while nums:
            num = nums.pop()
            build(root, num)

        def inorder(node, result):
            if not node:
                return result

            inorder(node.left, result)
            result.append(node.val)
            inorder(node.right, result)

            return result

        return inorder(root, [])

Merge Sort - In Place

(Timelimit Exceed)

• Time: O(NlogN)
• Space: O(1)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(left, right):
            if left >= right:
                return

            pivot = left + (right - left) // 2

            # Split
            merge_sort(left, pivot)
            merge_sort(pivot+1, right)

            if nums[pivot] <= nums[pivot+1]:
                return

            # Merge Result
            l_start, l_end, r_start, r_end = left, pivot, pivot+1, right
            while l_start <= l_end and r_start <= r_end:
                # The partition is already sorted
                if nums[l_start] <= nums[r_start]:
                    l_start += 1
                    continue

                value = nums[r_start]
                i = r_start

                # Shift all elements to right by 1
                for i in range(r_start, l_start, -1):
                    nums[i] = nums[i-1]

                # Place value to first place
                nums[l_start] = value

                l_start += 1
                l_end += 1
                r_start += 1

        merge_sort(0, len(nums)-1)

        return nums

Merge Sort

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(left, right, result):
            i, j, k = 0, 0, 0
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    result[k] = left[i]
                    i += 1
                else:
                    result[k] = right[j]
                    j += 1
                k += 1
            result[k:] = left[i:] if i < len(left) else right[j:]

        def merge_sort(nums):
            if len(nums) == 1:
                return
            mid = len(nums) >> 1
            left = nums[:mid]
            right = nums[mid:]

            merge_sort(left)
            merge_sort(right)

            merge(left, right, nums)

        merge_sort(nums)
        return nums

Rust

Built-in Vec::sort()

impl Solution {
    pub fn sort_array(mut nums:  Vec<i32>) -> Vec<i32> {
        nums.sort();
        nums
    }
}

Bubble Sort

impl Solution {
    pub fn sort_array(nums: Vec<i32>) -> Vec<i32> {
        let mut swapped = true;
        let mut answer = vec![0; nums.len()];
        answer[..nums.len()].clone_from_slice(&nums);

        while swapped {
            swapped = false;
            for i in 1..answer.len() {
                if answer[i - 1] > answer[i] {
                    answer.swap(i - 1, i);
                    swapped = true
                }
            }
        }
        answer
    }
}

Prefix Sum

impl Solution {
    pub fn sort_array(nums: Vec<i32>) -> Vec<i32> {
        let length = nums.len();
        let mut v = vec![0; 100001];
        let mut r = Vec::new();

        for i in 0..length {
            v[nums[i] as usize + 50000] += 1;
        }
        for i in 0..100001 {
            while v[i] > 0 {
                r.push(i as i32 - 50000);
                v[i] -= 1;
            }
        }
        r
    }
}