Sort K sorted array | Sort nearly sorted array

This video explains a very important programming interview problem which is to sort a nearly sorted array or a k sorted array.I have explained 3 approaches for solving this problem.In this problem, given an array we need to sort it.But the array has special property of being K-sorted, which means that each element is atmost K away from its actual position in a sorted array.I have shown how to make use of this property and solve the entire problem efficiently.The first method is by using simple sorting which takes O(NlogN) time.The second method is by using insertion sort and the third method is by using Heap.I have also shown comparision between all these methods.Code for both insertion sort and heap are explained at the end of the video.

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

==========================================PLEASE DONATE=============================
==============================================================================

=======================================================================
USEFUL LINKS:

RELATED LINKS:

#heap #techdose #heapcourse

[ashokjat]

Bro I wanna Thank you from the bottom of my heart, Finally I got my first job at Zoho with a decent package.Your videos were really helpful for my preparation and I'll remember you.Thank you!!!

[iamparitosh]

I would highly recommend of your videos for everyone who finds it difficult to understand concepts easily as your video even explain the obvious things which may not be obvious for some.

[anonymousanonymous]

Instead of copy pasting code from gfg, show ur own code, code of gfg can be made much simpler

[AltafHussain-onoe]

Thank You Sir for Explaining in such a easy way.

[preetamramdhave]

This is really nice work. I have seen some other videos also from you . All are very good and easily explain. Very good work. The way you explain we can easly code the solution and understand the approach as well as the algorithm also. Apricate your work.

[MahirHasancse]

Best Explanation.
I want ask you the question about complexity.
In the time complexity,
1. For 1st k+1 element build heap = O(k+1)
2. For remaining n-k+1 element push in the heap = O((n-k+1)logk)
3. For remaining n-k+1 element pop from the heap = O((n-k+1)logk)
4. For remaining k+1 element pop from the heap = (k+1log k)+(klog k-1)+(k-1log k-2)+...+(k-k+1log k-k)
5. Traversing the whole array = O(n)
Is it correct?
What will be the complexity for the point no. 4?

[pujabhardwaj]

Thank you so much for such great really helpful

[jayneversettle]

Hi Dawg, Beautiful explanation. But why were you sayin "we gotta use minHeapy() etc etc..." when all we are using is a priority queue in Java and C++.


And In the interview, Its okay to use PriorityQueue right? I mean we don't have to implement the entire algorithm from the base and create a minHeapify() method right?

[Somethingsomethinglol]

Question: Around 12:40 you mention that we do the extract min operation (to get the 2) and then we insert the next value (8). Shouldn't we insert first and then extract? Suppose instead of the next value being 8, it were 0. Wouldn't we want to insert that 0, min heapify the heap, then extract the root (0) ?

Thank you for this series! I've spent the weekend going through this playlist. Incredibly helpful.

[mohammadyahya]

Thank you very much. Clear explanation, but I have one question at 12:58 please. Why you took please 2 and added to array when you reached 8? What if the min element is the last element? I mean if 2 is at position of 9 instead of 3?

[shalinshikhar]

The code for insertion sort which is shown at the last is not using the property of k sorted..can anyone clarify??

[harigs]

Why do you create new array when you can push it given array itset

[vasudevrao]

After k+1 times we are just removing min and adding a new element.
For removing min we do heapify and then again to add new element we do bottom up algo.
Rather then doing that cant we just replace the min element with the new element and do a heapfy ?
Pls Correct me if m wrong.

[harigs]

This problem under which topic .heap .. I have been solving questions of curious freaks coding sheet .I solved all queue problems by myself.but I was not able to solve this efficiently.. that's why I am asking..

[harigs]

What if the k==N then time complexity will be what?

[hizmzmhei]

Hello Sir, I am big fan of your work. I have a question from dynamic programming. Could you please share email so that I can send you. I am unable to solve that question. You can even make a video on that.

[venkatkrishna]

not good. you did not explain the intuition behind using min heap to solve this problem

[omkarkawatgi]

You teach less and promote your other videos more ! Not good explaining !