Skip to content

Instantly share code, notes, and snippets.

@liyunrui

liyunrui/insertionSort.py

Last active Dec 26, 2020
Embed
What would you like to do?
leetcode-sorting
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
return self.insertionSort(nums)
def insertionSort(self, A):
"""
Idea is think of array as two sections given index j:
On the left side of j, it's partial sorted array.
On the right side of j, it's unsorted array.
[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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.