The process for implementing algorithms is like trying to explain a complex subject to a small child - in this case, the child is the machine. You must understand to concept of the algorithm yourself, and then start to break it into parts, then do it again, and again, until you are left with instructions so simple that they can be written as an instruction in code.
Let's take, for example, an Insertion Algorithm:
- Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. It operates
by beginning at the end of the sequence and shifting each element one
place to the right until a suitable position is found for the new
element. The function has the side effect of overwriting the value
stored immediately after the sorted sequence in the array.
- To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert each element encountered into its
correct position. The ordered sequence into which the element is
inserted is stored at the beginning of the array in the set of indices
already examined. Each insertion overwrites a single value: the value
being inserted.
Lets take the first step - it describes a function called Insert, so it means we'll need a function called Insert. That's simple enough. What should it do? lets write it down (simply copying the sentence above, breaking it into steps):
function Insert(array, new_item)
1. begin at the end of the sequence
2. shift each element one place to the right until a suitable position is found for the new element
end
Step 1 is simple enough, but step 2 is still a little complex - let's break it down: it describes a loop ("each element"), an operation ("shift one place to the right"), and a stop condition ("until a suitable position is found")
2'. each element
2'a. shift one place to the right
2'b. until a suitable position is found
or, if we want to turn it into a condition within a loop, we'll write it like:
2''. is element larger than new_item?
yes -> a. shift one place to the right
b. go to previous element
no -> a. insert new_item in next position
b. break
starting to look like code, right? Let's try to write code to match what we wrote:
function Insert(array, new_item)
current_index = array.last
while (true)
if(array[current_index] > new_item)
array[current_index+1] = array[current_index]
current_index = current_index-1
else
array[current_index+1] = new_item
return
end
end
end
This is the first step! This code (almost) works - now you switch hats to a developer, and ask yourself - are all the edge conditions handled (no - what if all elements are larger than the new_item?), is this the proper way to handle an array (only if it has more positions then elements - otherwise the first element will "fall off" the array...), how do I need to enhance its functionality to accommodate the next step of the algorithm? Can I refactor it to look/work better, and do the same thing?
function Insert(array, last_item_index, new_item)
if (last_item_index >= array.length) raise exception
for (current_index = last_item_index; current_index >= 0; current_index--)
if(array[current_index] > new_item)
array[current_index+1] = array[current_index]
else
break
end
end
array[current_index+1] = new_item
end
(this is, of course, all written in pseudocode. your implementation will be according to your language of choice, its idioms, capabilities and conventions)
