Basic Algorithm Implements in Python3

Common algorithms that are useful for code competition.

Sorting

Insertion Sort

Iterate the whole list, every time compare every element in the new list to decide where to insert the current element.

Time complexity: $o(n^2)$
Space complexity: $o(n)$

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        sorted_nums = []
        for each_num in nums:
            i = 0
            while i < len(sorted_nums):
                if sorted_nums[i] < each_num:
                    i += 1
                else:
                    break
            sorted_nums.insert(i, each_num)
        return sorted_nums

Bubble Sort

Every time sort one element to the final position.

Time complexity: $o(n^2)$
Space complexity: $o(1)$

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

Selection Sort

Every time select the minimum/maximum element, and put it to the final position.

Time complexity: $o(n^2)$
Space complexity: $o(1)$

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            cur_min, cur_min_index = 50001, -1
            for j in range(i, len(nums)):
                if nums[j] < cur_min:
                    cur_min = nums[j]
                    cur_min_index = j
            nums[i], nums[cur_min_index] = nums[cur_min_index], nums[i]
        return nums

Quick Sort

Every time, put all the smaller numbers in the left, put all the larger numbers in the right.

Time complexity: $o(n\log n)$, in worst case it would be $o(n^2)$, where pivot is always the largest/smallest element.

Space complexity: $o(n)$, key point: skip pivot when adding elements into smaller and larger.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) < 2:
            return nums
        pivot = random.choice(nums)
        smaller_nums = [item for item in nums if item < pivot]
        larger_nums = [item for item in nums if item > pivot]
        equals = [item for item in nums if item == pivot]
        return self.sortArray(smaller_nums) + equals + self.sortArray(larger_nums)

Space complexity: $o(1)$

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def helper(left: int, right: int) -> None:
            if left >= right:
                return
            pivot = nums[random.randint(left, right)]
            small_index, large_index = left, right
            p = left
            while p <= large_index:
                if nums[p] < pivot:
                    nums[small_index], nums[p] = nums[p], nums[small_index]
                    small_index += 1
                    p += 1
                elif nums[p] > pivot:
                    nums[large_index], nums[p] = nums[p], nums[large_index]
                    large_index -= 1
                else:
                    p += 1
            helper(left, small_index - 1)
            helper(large_index + 1, right)
        helper(0, len(nums) - 1)
        return nums