 Lesson 3 - Sorting Algorithms and Divide & Conquer

Please visit the Lesson Page for more detailed info  Session Recordings:
English: https://youtu.be/M6NJUfT14aY
Hindi: https://youtu.be/W0R6m1sX1sY In this lesson, we explore the sorting problem and apply the divide-and-conquer strategy to come up with efficient algorithms for sorting.

Notebooks used in this lesson: Asking/Answering Questions :

2 Likes

Hi guys
how can someone test each individual code in a function to enable one understand it better

I am not sure if I got your question right, but I think you mean you want to test each line of a code of a function that you made? You can give a print statement and check what the above value prints and compare it with what it should print and you can do this for all confusing line in your code and later when you have removed all your confusion you can comment/remove the extra print statements.

Hi,
Could someone explain how the second step is calculated please i.e.,
(2×3)+(2×4+0×3)x+(2×2+3×5+4×0)x^2+(7×3+5×4+0×2)x^3+(7×4+5×2)x^4+(7×2)x^5?

Example:

def insertion_sort(nums):
nums = list(nums)
for i in range(len(nums)):
cur = nums.pop(i)
j = i-1
while j >=0 and nums[j] > cur:
j -= 1
j -= 1
nums.insert(j+1, cur)
return nums

Good evening everyone, Sir asked to find the time complexity of insertion_sort. Since, seeing the for loop, I understood that this loop’s complexity would be O(n) but I was not able to understand the complexity of while loop. Therefore, I am not able to tell the complexity of the insertion_sort. Can anyone help???

1 more question from this, shouldn’t the or replaces and in terminating condition of while loop as we want either of the two conditions to come to false first? Like I mean that we want that either j reaches the starting of the array or the element on nums[j] should become smaller than the cur? Please help.

The time complexity for the while loop depends,
In the best-case scenario (when the list is already sorted) nums[j] > cur would always be false and we would never enter the while loop.

The overall time complexity, in this case, would be because of the for loop (n-1) and .insert() (n-1) = O(n).

For the worst-case (when the list is in decreasing order), the while loop will be true for all values of i in for loop.
So, when i=1 while will run 1 time, when i=2 while will run 2 times … when i=n-1 while will run n-1 times.

Therefore, in total the while loop runs for 1+2+3......+(n-1) times,
= (n-1)(n-1+1)/2 {sum of n natural numbers}
= (n^2-n)/2

And the overall time complexity in the worst-case would be O(n^2).

Also, I think we need both j>=0 & nums[j]>cur as for comparison and swap, we require the nums[j]>cur condition and to check if nums[j] don’t go out of bounds we need j>=0,
Even in python if j=-1 then nums[-1] would be the last element in the list which should be greater than cur, but we will still keep comparing elements backward even when not required.

1 Like

Thanks for your reply, now I can understand why insertion sort’s complexity was O(n^1).   1 Like

in this when will be the end =None ?

def partition(nums, start=0, end=None):
# print(‘partition’, nums, start, end)
if end is None:
end = len(nums) - 1

# Initialize right and left pointers
l, r = start, end-1

# Iterate while they're apart
while r > l:
# print('  ', nums, l, r)
# Increment left pointer if number is less or equal to pivot
if nums[l] <= nums[end]:
l += 1

# Decrement right pointer if number is greater than pivot
elif nums[r] > nums[end]:
r -= 1

# Two out-of-place elements found, swap them
else:
nums[l], nums[r] = nums[r], nums[l]
# print('  ', nums, l, r)
# Place the pivot between the two parts
if nums[l] > nums[end]:
nums[l], nums[end] = nums[end], nums[l]
return l
else:
return end

i

Hey @latchireddiekalavya, If you notice carefully, the default value of end is set to None. So, when the program will be called for the first time, the value of end will be None if not specified while calling the function. Hope this will help!!  Hi guys I would like to tell u all something that by default the complexity of the Insertion sort is O(n^2) [time] . So I have updated it a by putting the concept of binary search to it and