DataStructures-and-Algorithms

Insertion Sort

Review

Refresh your understanding of Big Oh.

Assignment

Review the pseudocode below, then trace the algorithm by stepping through the process with the provided sample array. Document your explanation by creating a blog article that shows the step-by-step output after each iteration through some sort of visual.

Once you are done with your article, code a working, tested implementation of Insertion Sort based on the pseudocode provided.

You may review an example document HERE

Pseudocode

  InsertionSort(int[] arr)

    FOR i = 1 to arr.length

      int j <-- i - 1
      int temp <-- arr[i]

      WHILE j >= 0 AND temp < arr[j]
        arr[j + 1] <-- arr[j]
        j <-- j - 1

      arr[j + 1] <-- temp

Sample Arrays

In your blog article, visually show the output of processing this input array:

[8,4,23,42,16,15]

For your own understanding, consider also stepping through these inputs:

• Reverse-sorted: [20,18,12,8,5,-2]
• Few uniques: [5,12,7,5,5,7]
• Nearly-sorted: [2,3,5,7,13,11]

Implementation

• Provide a visual step through for each of the sample arrays based on the provided pseudo code
• Convert the pseudo-code into working code in your language
• Present a complete set of working tests

Requirements

Ensure your complete code solution follows the standard requirements.

1. Write unit tests
2. Follow the template for a well-formatted README
3. Submit the assignment following these instructions

Submission

Submit a link to a pull request in your data-structures-and-algorithms repository that contains your completed version of the sorting/insertion/README.md along with your full working, tested code solution.

Stretch Goal

Share your article on LinkedIn, so that your network knows how awesome you are.