CODEWITHSUNDEEP
arraysalgorithmsortinginsertion-sortin-place
user121
user121

Reputation: 325

k messed sorted array using Insertion sort

In the familiar problem where every element in an array is at most k positions away from it's correct location, either to the left or to the right, I don't completely understand how the Insertion sort algorithm works.

I drew it on a paper, and debugged it step. It does seem to work, and the order of time complexity is O(n.k) as well.

But my question, is that, in this problem, the element could be k positions away either in the left or in the right. However, insertion sort only checks left. How does it still manage to get it right? Could you please explain to me, how this algorithm still works, although we look only to the left, in a manner I can convince myself?

PS : Irrelevant here : If I wasn't aware of this algorithm, I would've thought of something like Selection sort, where for a given element, i, you look k positions on the left and right, to choose the smallest element.

PS : Even more irrelavant : I'm aware of the min-heap based method for this. Again, the same question, why do we only look left?

Upvotes: 2

Views: 833

Answers (3)

user3386109
user3386109

Reputation: 34839

Items to the left of the correct location get pushed right while the algorithm is processing smaller items. (Assuming that we're sorting in ascending order.) For example, if k is 3 and the initial array is 

D A B E H C F G

Let's examine how D gets to location 3 in the array. (Using zero-based indexing, D starts at index 0, and needs to move to index 3 in the array.)

The first pass starts at E, and finds that it can swap A and D resulting in

A D B E H C F G

Second pass starts at H, and swaps B and D

A B D E H C F G

Third pass starts at C, and swaps C with H, E, and D

A B C D E H F G

And now you see that D is already where it's supposed to be.

That's always going to be the case. Any element that starts to the left of its final position will be pushed right (to its final position) as smaller elements are processed. Otherwise, the smaller elements aren't in their correct locations. And an element (like D) won't get pushed past it's correct location, because the algorithm won't swap that element with elements that are larger.

Upvotes: 2

आनंद
आनंद

Reputation: 2582

It's a wrong assumption that you only need to look left. You can also start from the beginning index and look right.

But, there's something called Loop Invariant (Read more about it). The invariant of insertion sort is that the it keeps a sorted subarray(growing as the algorithm runs) to its left or its right.

Here's the link to a read which will clear it up. https://www.hackerrank.com/challenges/correctness-invariant

Upvotes: 0

Alokit Jindal
Alokit Jindal

Reputation: 1

In Insertion Sort what actually happens is we compare an element with every element to its left . So what happens is the list to the left of that element gets sorted and the list to the right of that element is not. Then we move on to the next element and repeat the same process again. This is done till we reach the last element in the list. Therefore we get the sorted list.

Upvotes: 0

Related Questions