This is probably the most intuitive sorting algorithm. If you have played poker before, then this is your go-to algorithm to sort cards in your hand.
Brute Force
def sortIntegers(A: List[int]) -> List[int]:
n = len(A)
if n == 0:
return
sorted_list = []
for num in A:
i = find_insert_position(sorted_list, num)
sorted_list.insert(i, num)
return sorted_list
def find_insert_position(sorted_list: List[int], num: int) -> int:
n = len(sorted_list)
if n == 0:
return 0
for i in range(n):
if sorted_list[i] > num:
return i
return n
time O(n^2) space O(n)
def sortIntegers2(self, A: List[int]) -> None:
n = len(A)
if n == 0:
return
sorted_list = []
for num in A:
i = bisect.bisect_left(sorted_list, num)
sorted_list.insert(i, num)
return sorted_list
Insertion takes O(n) because copying the array but finding the inserting position is only O(logn) now
Code
need to swap for in-place operations
def sortIntegers(A: List[int]) -> None:
n = len(A)
if n == 0:
return
for i in range(n):
# expand sorted list to index i
insert(A, i)
def insert(nums: List[int], i: int) -> None:
j = i
for j in range(i, 0, -1):
if nums[j] < nums[j-1]:
swap(nums, j, j-1)
else:
break
def swap(nums: List[int], i: int, j: int) -> None:
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
public void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// all cards before i are sorted
insert(arr, i);
}
}
private void insert(int[] arr, int newbie) {
for (int i = newbie; i > 0 && arr[i] < arr[i-1]; i--) {
swap(arr, i, i-1);
}
}
Time Complexity
The worst case analysis in bubble sort, selection sort, and insertion sort all share a common theme - a halved square (a rugged triangle). That triangle is proportional to O(n^2).
