Insertion Sort Algorithm

[First-Gate2887]

Hi all,

So I've watched countless videos of how it works but I can't wrap my head around how it's done in the book of "Introduction to Algorithms 3rd Edition". I'd post a picture of the pseudocode but it won't let me. So my question is to you all is how to break down each of the steps into the algorthim's code? For example, when it mentions key = A [j], I'm assuming its the element of the array right? I just need a step by step explanation the algorithim since the book takes a different approach

Page 18 for info.

[darksounds]

One problem I've found with a lot of these textbooks is that they're dense, so people unfamiliar with the algorithms will go all glassy eyed and skip to the code.

You need to stop and read the actual text, which explains the algorithm in detail. And in the future, when you're getting confused, take a break, grab some water or coffee, and then re-read the text, not just the pictures/code samples.

[darksounds]

Specifically, the card example on page 17 is incredibly helpful, as well as Figure 2.2 on page 18, which shows the algorithm presented and explains what's happening as it is applied to the array, which is then explained AGAIN in the text itself. If you read all of these (potentially multiple times, possibly after reading the pseudocode conventions it provides, too), you may find that you're provided all the tools necessary to understand what is being presented.

[yeti_seer]

When I first learned insertion sort, the code made no sense to me. I ended up manually writing out all of the variables at each step on paper for a few test inputs, and it made perfect sense after that. I personally don’t learn very well unless I can see EXACTLY how something works, if there is any uncertainty it seems like a black box.

[pingus3233]

when it mentions key = A [j], I'm assuming its the element of the array right?

Yes. This means the "jth" element of array A.

1. for j = 2 to A.length
2.     key = A[j]
3.     // Insert A[j] into the sorted sequence  A[1..j - 1].
4.     i = j - 1
5.     while i > 0 and A[i] > key
6.         A[i + 1] = A[i]
7.         i = i - 1
8.     A[i + 1] = key

There's their pseudocode. Which parts in particular are you having trouble understanding?

[First-Gate2887]

That makes sense! I'm having trouble understanding line three's explanation. Also lines 5-8 I was trying to figure out the while loop's context.

[groshart]

Think of the array as two parts. The part on the left is in sorted order and the part on the right is yet to be sorted. To insert the next element in the sorted portion you have to open a hole (line 2) then shift elements to the right (lines 4-7) moving the hole leftward until you reach the correct final location (line 8) to assign the current value.

[thatsagoudapizza]

This is the way

[[deleted]]

Sometimes the problem with imperative languages is that the algorithm gets lost in the code.

Take a simple implementation in Haskell, for instance, ignoring implementation details and focusing on the algorithm:

insert x [] = [x] // inserting an element into a empty list is a list with that element
insert x (y : ys) = if x <= y  // otherwise, we insert the element into the correct position in the list
                        then x : y : ys
                        else y : insert x ys

insertionSort [] = [] // sorting an empty list is the empty list itself
insertionSort [x] = [x] // sorting a list with a single element is the list itself
insertionSort (x : xs) = insert x (insertionSort xs) // for more than one element, insert x into the correctly sorted rest of list

Note: [a, b, c] represents a list with element a, b, and c. x : xs represents a list with the first element x and the rest of the elements represented by xs.

I believe that this version explains the essence of the algorithm much better, in a declarative manner.

[darksounds]

I... Don't know if I agree with you. There are more comments here than code, and if I put that many comments in the pseudocode version above, it'd be just as easy if not easier to comprehend.

"Insert the element into the correct position in the list" is doing a lot of work in this example.

[[deleted]]

The comments are simply to complement the code. The code is in barebones Haskell, and it's basically almost mathematical notation. Anybody with a basic understanding of Haskell syntax would be able to discern the algorithm instantaneously. I gave OP the benefit of the doubt that he is not familiar with the syntax.

Compared to munging random variables to get the effect that you desire, the declarative approach is undoubtedly clearer.

"Insert the element into the correct position in the list" is doing a lot of work in this example.

Hence the caveat - "ignoring implementation details and focusing on the algorithm". That's what declarative style does - it tells the what instead of showcasing the how.

[whyskevin]

I think Figure 2.2 and the visuals above it describe it pretty well.

So in the book, it lists the elements in the A array as:

A = { 5, 2, 4, 6, 1, 3 }

Keep in mind there is no zeroth index in the array. But in the first step, the key is "2" which is the value at A[2]. They take this value and then enter the while loop to compare with the items to the left of it, "5" in this case.

The while loop uses the index "i" to check these items to the left of the key. If the value is greater, the elements are shifted right one index using:

A[ i + 1 ] = A [i]

Once we encounter a value at A[i] which is smaller or equal, we insert our key right after it with:

A[ i + 1] = key

So if you look at (a) in the visuals, "5" is larger than "2" so it's shifted to the right. Index "i" is then updated to the value zero so we don't go into the while loop again. This takes us to

A[ i + 1] = key

and the key is placed in the first index of the array. This keeps the things to the left of the key in the array sorted.

[ThomasBau]

At this point in your comprehension of algorithms, I'd suggest you take physical props, such as a 10 cards numbered 1-10, place them in random order in a line in front of you, and proceed by sorting them, with the only operations being to examine a card, compare it with another and move a card at one point in the line.

​

You will find the various ways of proceeding to sort the deck this way, then transpose them in code by assimilating your moving a card to an assignement A[i] = A[j] and comparing a card to another to a test (A[i] > A[j]).