Data Science & Algorithms: Insertion Sort

Recently, I decided to start blogging on this website. And I don’t have any ideas for a blog. Well, I don’t know what the meta is here.

So, I thought I’d do a series where I explain different algorithms in different languages( Python, JavaScript).

Now, that we got the intro out of the way, let’s start with the first algorithm :). Insertion Sort

To understand the theory behind Insertion Sort I’ll give you an analogy:

Imagine that you have a list of cards( let’s say 4) in no particular order on the table. And you have to sort those cards on your left hand.

So what do you do?
Well, you’re going to get a card with your right hand, examine that card, look at the left hand.

If you don’t have any cards on your left hand you will put the right-hand card on your left hand, if you have a card on your left hand you’ll compare the card on your left hand and right hand. If the right-hand card has a higher value you will insert that card after the previous one( it’s a little confusing I know) otherwise you’ll push the card on your left hand further to make room for the right-hand card.

Sorry for the big chunk of text 🙁

Now that we understand how Insertion Sort works on a theoretical level, let’s look at how we can do this in code:

Here Is The Python Code:

# Python Code
def insertion_sort(arr):
    # Loop Through Array
    for i in range(len(arr)):
        # Store Selected Element Value In A Variable
        key = arr[i]
        # Store Previous Array Index In A Variable
        j = i - 1
        # Check If There Are Any Other Previous Elements
        # Compare Previous Array Element With Current Element
        while j >= 0 and key < arr[j]:
            # If Previous Element Has A Higher Value Than Current Element, "push it" one index further to "make space" for the current element
            arr[j + 1] = arr[j]
            j -= 1
        # Store Current Element In The Position Where It Belongs
        arr[j + 1] = key
arr = [2, -4, 0, 1, 69] # Random Array
insertion_sort(arr)
print(arr)
# Output:
# [-4, 0, 1, 2, 69]
# Python Code
def insertion_sort(arr):
    # Loop Through Array
    for i in range(len(arr)):
        # Store Selected Element Value In A Variable
        key = arr[i]
        # Store Previous Array Index In A Variable
        j = i - 1

        # Check If There Are Any Other Previous Elements
        # Compare Previous Array Element With Current Element
        while j >= 0 and key < arr[j]:
            # If Previous Element Has A Higher Value Than Current Element, "push it" one index further to "make space" for the current element
            arr[j + 1] = arr[j]
            j -= 1

        # Store Current Element In The Position Where It Belongs
        arr[j + 1] = key

arr = [2, -4, 0, 1, 69] # Random Array
insertion_sort(arr)
print(arr)

# Output:
# [-4, 0, 1, 2, 69]
# Python Code
def insertion_sort(arr):
    # Loop Through Array
    for i in range(len(arr)):
        # Store Selected Element Value In A Variable
        key = arr[i]
        # Store Previous Array Index In A Variable
        j = i - 1

        # Check If There Are Any Other Previous Elements
        # Compare Previous Array Element With Current Element
        while j >= 0 and key < arr[j]:
            # If Previous Element Has A Higher Value Than Current Element, "push it" one index further to "make space" for the current element
            arr[j + 1] = arr[j]
            j -= 1

        # Store Current Element In The Position Where It Belongs
        arr[j + 1] = key

arr = [2, -4, 0, 1, 69] # Random Array
insertion_sort(arr)
print(arr)

# Output:
# [-4, 0, 1, 2, 69]

Enter fullscreen mode Exit fullscreen mode

Here Is The JavaScript Code:

function insertionSort(arr) {
  let i, key, j;
  for (i = 1; i < arr.length; i++) {
    key = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}
let arr = [2, -4, 0, 1, 69];
insertionSort(arr);
console.log(arr);
// Output:
// [ -4, 0, 1, 2, 69 ]
function insertionSort(arr) {
  let i, key, j;
  for (i = 1; i < arr.length; i++) {
    key = arr[i];
    j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }
}

let arr = [2, -4, 0, 1, 69];
insertionSort(arr);

console.log(arr);

// Output:
// [ -4, 0, 1, 2, 69 ]
function insertionSort(arr) {
  let i, key, j;
  for (i = 1; i < arr.length; i++) {
    key = arr[i];
    j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }
}

let arr = [2, -4, 0, 1, 69];
insertionSort(arr);

console.log(arr);

// Output:
// [ -4, 0, 1, 2, 69 ]

Enter fullscreen mode Exit fullscreen mode

And that’s the end of this one! Hope you enjoyed it! Don’t forget to like!!!

原文链接：Data Science & Algorithms: Insertion Sort