def selection_sort(A):
n = len(A)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if A[j] < A[min_index]:
min_index = j
# Swap the found minimum element with the first element
A[i], A[min_index] = A[min_index], A[i]
return A
def bubble_sort(A):
n = len(A)
for i in range(n):
for j in range(n - 1, i, -1):
if A[j - 1] > A[j]:
# Swap adjacent elements
A[j - 1], A[j] = A[j], A[j - 1]
return A
| # | Design Strategy | Description | Pros/Cons | Examples |
|---|---|---|---|---|
| 1. | Brute Force | - Directly based on the problem statement. | ✅ Straightforward ❌ May vary between individuals due to subjectivity. |
Selection Sort, Bubble Sort |
| 2. | Decrease and Conquer | - Decrease the problem size ($n$) to size $n-1$. | ✅: Systematic approach to problem-solving. ✅: Facilitates recursive thinking. |
|
| 2.1 | TOP-DOWN | - Do upfront work to nibble away one (or few) element(s): $n \rightarrow n-1$
MAIN IDEA: 1. I pretend to be a Lazy Manager. 2. I nibble away at the problem to make it smaller. 3. I do upfront work of adding the nibble to the solution. 4. I hand over my solution and the remaining problem to my subordinate. (They do the same.) CODING TIP: Write code from the perspective of an arbitrary lazy manager to sort the array: ..BEFORE: The managers above me would have ensured that all previous elements are sorted. (because they are lazy managers too!) ..MY JOB: I just extend the sorted region by one more element. ..AFTER: I hand over the remaining work to my subordinate. (They do the same.) |
Selection Sort, Bubble Sort | |
| 2.2 | BOTTOM-UP | - Work at the end to extend the $(n-1)^{st}$ solution: $n-1 \rightarrow n$
MAIN IDEA: 1. I pretend to be a Lazy Manager. 2. I nibble away at the problem to make it smaller. I keep the nibble for work to be done later. 3. I hand over the remaining problem to my subordinate. (They do the same.) 4. The subordinate returns their solution to me. 5. I do the (later) work of adding my nibble to the solution. 6. I hand over my solution to my manager. |
Insertion Sort |
Coding Insertion Sort:
nums:def insertion_sort(nums):
pass
i). I am to only sort this prefix/subarray (from index $0 \rightarrow i$). To do this, I depend on my subordinate.
nums[i]) and try to insert it into the appropriate position in my subordinate’s subarray (from index $0 \rightarrow i-1$). And thereby, extend the sorted region by one more element.
temp variable.def insertion_sort(nums):
temp = nums[i]
j). And as long as the value that j is pointing to is bigger than the value in the temp variable, I will keep right shifting those bigger values to the right. (to make space for the temp value to be INSERTED into its appropriate position.) Let’s add the code for right to left scan:def insertion_sort(nums):
temp = nums[i]
j = i - 1 # j is initialized to the index of the last element in the subordinate's subarray
def insertion_sort(nums):
temp = nums[i]
j = i - 1
while __________ nums[j] > temp: # As long as `nums[j]` is bigger than `temp`,
nums[j + 1] = nums[j] # We keep right shifting `nums[j]` to the right.
j -= 1 # We also keep moving the `j` index one step to the left.
nums[j] will be less than or equal to temp. And at this point, we must insert the temp value into the position to j’s right.def insertion_sort(nums):
temp = nums[i]
j = i - 1
while __________ nums[j] > temp:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = temp # We insert the `temp` value into the position to `j`'s right.
def insertion_sort(nums):
for i in range(1, len(nums)): # Manager index `i` varies from 1 to n-1.
# All the following arbitrary manager work is repeated by each manager in a bottom up order.
temp = nums[i]
j = i - 1
while __________ nums[j] > temp:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = temp
return nums # Return the sorted version of the original array.
temp value. And in this case, the j index will jump off the left end of the array and its value will become -1. ILLEGAL INDEX!j index needs to be greater than or equal to 0.def insertion_sort(nums):
for i in range(1, len(nums)):
temp = nums[i]
j = i - 1
while j >= 0 and nums[j] > temp: # j must always be greater than or equal to 0.
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = temp
return nums
temp value that we are trying to insert is smaller than all the elements within the subordinate’s subarray because let’s say we have a subarray [8, 7, 6, 5, 4, 3] and we are trying to insert 2 into its appropriate position.
j index will jump off the left end of the array and become -1.temp value into index 0. (nums[-1 + 1] -> nums[0])key).key with elements in the sorted subarray.key one position to the right.key at the correct position.[2, 4, 5, 6, 7, 8, 3]3:
3 with 8, 7, 6, 5, 4, shifting each to the right.2 is less than 3.3 after 2.