An introduction to an algorithm for insertion sorting
Insertion sorting is a way of putting data into an order. For example, consider the data items:
6 5 3 1 8 7 2 4
You can see the animation (from Wikipedia) of how insertion sorting works but we have also included a step-by-step description below to help you understand the process.
We take the first data item. This is an ordered list of one element.
We now have an ordered list: 6. We also have all the other items to the right of 6 in an unordered list.
Then we insert the next element 5 in the correct place. We compare 5 to the element just before it, which is 6. If it is bigger than 6 or the same, we leave it in its current position. If it is smaller, we swap the data elements. We must swap them.
We now have an ordered list: 5 6. The other items to the right of 6 are an unordered list.
Then we insert the next element 3 in the correct place. We compare 3 to the element just before it, which is 6. If it is bigger than 6 or the same, we leave it in its current position. If it is smaller, we swap the data elements. We have to swap them. Then we compare again with the next element, which is 5. We must swap them.
We now have an ordered list: 3 5 6. We also have all the other items to the right of 6 in an unordered list.
Then we insert the next element 1 in the correct place. We compare 1 to the element just before it, which is 6. We have to swap them. Then we compare again with the next element, which is 5. We must swap them. Then we compare again with the next element, which is 3. We must swap them. There are no more elements to compare with so we stop.
We now have an ordered list: 1 3 5 6. We also have all the other items to the right of 6 in an unordered list.
Then we insert the next element 8 in the correct place. We compare 8 to the element just before it, which is 6. We leave them in the same position and stop.
We now have an ordered list: 1 3 5 6 8. We also have all the other items to the right of 8 in an unordered list.
Then we insert the next element 7 in the correct place. We compare 7 to the element just before it, which is 8. We have to swap them. Then we compare again with the next element, which is 6. We leave them in the same position and stop.
We now have an ordered list: 1 3 5 6 7 8. We also have all the other items to the right of 8 in an unordered list.
Then we insert the next element 2 in the correct place. We compare 2 to the element just before it, which is 8. We have to swap them. Then we compare again with the next element, which is 7. We must swap them. Then we compare again with the next element, which is 6. We must swap them. Then we compare again with the next element, which is 5. We must swap them. Then we compare again with the next element, which is 3. We must swap them. We then compare 2 to 1. We leave them in the same position and stop.
We now have an ordered list: 1 2 3 5 6 7 8. We also have all the other items to the right of 8 in an unordered list.
Then we insert the next element 4 in the correct place. We compare 4 to the element just before it, which is 8. We have to swap them. Then we compare again with the next element, which is 7. We must swap them. Then we compare again with the next element, which is 6. We must swap them. Then we compare again with the next element, which is 5. We must swap them. Then we compare again with the next element, which is 3. We leave them in the same position and stop completely, as there are no more elements.
Our final sorted list is this: 1 2 3 4 5 6 7 8
We now have a description, an algorithm, of the solution to sorting data using the insertion sort method. It would be useful to convert this into pseudo-code. We can then give it to any programmer to convert into a real program using the language they are skilled in.