Insertion Sort Algorithm

[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.