DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Edited on

3 3

Insertion Sort

What do we understand about Insertion Sort?

  • It uses 2 loops (outer for-loop & inner while-loop) and 2 pointers
  • 1st pointer starts from 1 item after the 2nd pointer
  • 2nd pointer starts from 1 item before 1st pointer
  • 2nd loop loops decrementally till 0
  • as long as current value is more than left side value we copy the left side over to current
  • insertion happens after the 2nd loop is finished
  • Mutation is performed on the original Array
  • Time complexity
    • Best -> O(n)
    • Average -> O(n^2)
    • Worst -> O(n^2)
  • Space complexity
    • O(1)
    function InsertionSort(arr) {
        for (let i = 1; i < arr.length ; i++) {
            let currentValue = arr[i];
            let oneIndexBefore = i - 1;
            while (oneIndexBefore >= 0 && arr[oneIndexBefore] > currentValue) {
                arr[oneIndexBefore + 1] = arr[oneIndexBefore];
                oneIndexBefore--;
            }
            arr[oneIndexBefore + 1] = currentValue;
        }
        return arr;
    }
Enter fullscreen mode Exit fullscreen mode

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay