leetcode-sorting

insertionSort.py

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.insertionSort(nums)

    def insertionSort(self, A):
        """
        思路：
            i這個指針的元素代表我們需要插入的元素, 經過一輪處理後我們希望i的左邊是partial sorted的.
            所以當i走到最後, 整個array就sort完.
            為了做到這部, 每次都create 一個指針j從i開始遞減到index 0.每一次遞減都跟上一個元素比如果比較大就交換.
        [5,2,3,1]
         i
         j
           i  
           j  -> [2,5,3,1]
         j
         [2,5,3,1]
              i
              j -> [2,3,5,1]
              i
            j
        <-----x--->
  sorted area   unsorted area
        T: O(n^2) for worst and average time complexity. Best complexity is O(n) when array is sorted already.
        S: O(1) because we don't use extra space.
        """
        n = len(A)
        for i in range(n):
            # On the left side of j, it's partial sorted array. Contrarily, on the right side of j, it's unsorted array.
            j = i 
            while j > 0 and A[j-1] > A[j]:
                A[j], A[j-1] = A[j-1], A[j]
                j -= 1
        return A