Lesson 3 - Sorting Algorithms and Divide & Conquer

Please visit the Lesson Page for more detailed info :point_up:

:play_or_pause_button: Session Recordings:
English: https://youtu.be/M6NJUfT14aY
Hindi: https://youtu.be/W0R6m1sX1sY

:zap: 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:

:question: Asking/Answering Questions :
Reply to this thread to ask questions. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. We will give priority to the questions with the most likes. The rest will be answered by our mentors or the community. If you see a question you know the answer to, please post your answer as a reply to that question. Let’s help each other learn!

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). :pray: :sweat_smile: :sweat_smile:

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!! :hugs: :hugs:

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
made it O(nlogn)< complexity >O(n^2).

And the code for it is attached below have a look
Regards

There are also few edge cases for this
I have made the Insertion Sort to the complexity of O(n^2) to O(nlogn)
See below for the final code