<reponame>Sanster/LeetCode<filename>sort.py
from typing import List


def bubble_sort(nums: List[int]):
    n = len(nums)
    for j in range(n - 1):
        for i in range(n - 1 - j):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]


def quicksort(nums: List[int]):
    # time: n*log(n)
    # space: O(n)
    if len(nums) <= 1:
        return nums

    less = []
    greater = []
    base = nums[0]

    for x in nums[1:]:
        if x < base:
            less.append(x)
        else:
            greater.append(x)

    return quicksort(less) + [base] + quicksort(greater)


def quicksort_inplace(arr: List[int], left=None, right=None):
    # time: n*log(n)
    # space: O(1)
    if left is None:
        left = 0
    if right is None:
        right = len(arr) - 1
    if left < right:
        partition_idx = partition(arr, left, right)
        quicksort_inplace(arr, left, partition_idx - 1)
        quicksort_inplace(arr, partition_idx + 1, right)
    return arr


def swap(arr, idx1, idx2):
    arr[idx1], arr[idx2] = arr[idx2], arr[idx1]


def partition(arr, left, right):
    # index 表示大于 pivot 第一个元素的索引
    # 最后返回 index - 1 表示主点位置
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    swap(arr, pivot, index - 1)
    return index - 1


if __name__ == "__main__":
    # nums = [5, 4, 3, 2, 1]
    # bubble_sort(nums)
    # print(nums)

    tests = [[1, 5, 3], [4, 2, 1, 3], [4, 2, 1, 3, 5], [-1, 5, 3, 4, 0], [], [0]]
    for it in tests:
        assert quicksort(it) == sorted(it), f"res: {quicksort(it)}, gt: {sorted(it)}"
        assert quicksort_inplace(it) == sorted(
            it
        ), f"res: {quicksort_inplace(it)}, gt: {sorted(it)}"

from typing import List


def bubble_sort(nums: List[int]):
    n = len(nums)
    for j in range(n - 1):
        for i in range(n - 1 - j):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]


def quicksort(nums: List[int]):
    # time: n*log(n)
    # space: O(n)
    if len(nums) <= 1:
        return nums

    less = []
    greater = []
    base = nums[0]

    for x in nums[1:]:
        if x < base:
            less.append(x)
        else:
            greater.append(x)

    return quicksort(less) + [base] + quicksort(greater)


def quicksort_inplace(arr: List[int], left=None, right=None):
    # time: n*log(n)
    # space: O(1)
    if left is None:
        left = 0
    if right is None:
        right = len(arr) - 1
    if left < right:
        partition_idx = partition(arr, left, right)
        quicksort_inplace(arr, left, partition_idx - 1)
        quicksort_inplace(arr, partition_idx + 1, right)
    return arr


def swap(arr, idx1, idx2):
    arr[idx1], arr[idx2] = arr[idx2], arr[idx1]


def partition(arr, left, right):
    # index 表示大于 pivot 第一个元素的索引
    # 最后返回 index - 1 表示主点位置
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    swap(arr, pivot, index - 1)
    return index - 1


if __name__ == "__main__":
    # nums = [5, 4, 3, 2, 1]
    # bubble_sort(nums)
    # print(nums)

    tests = [[1, 5, 3], [4, 2, 1, 3], [4, 2, 1, 3, 5], [-1, 5, 3, 4, 0], [], [0]]
    for it in tests:
        assert quicksort(it) == sorted(it), f"res: {quicksort(it)}, gt: {sorted(it)}"
        assert quicksort_inplace(it) == sorted(
            it
        ), f"res: {quicksort_inplace(it)}, gt: {sorted(it)}"
# time: n*log(n) # space: O(n) # time: n*log(n) # space: O(1) # index 表示大于 pivot 第一个元素的索引 # 最后返回 index - 1 表示主点位置 # nums = [5, 4, 3, 2, 1] # bubble_sort(nums) # print(nums)