DEV Community: Jared Nielsen

How to Code the Merge Sort Algorithm in JavaScript and Python

Jared Nielsen — Fri, 26 May 2023 15:22:31 +0000

If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the merge sort algorithm in JavaScript and Python.

This article originally published at jarednielsen.com

How to Code the Merge Sort Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

Why do we need another sorting algorithm? What's the problem with the Bubble, Insertion, and Selection sorting algorithms? Why is their performance so slow? They each use nested iteration. If our goal is to improve the performance of our sorting algorithm, it follows that we need to do less iteration. But how do we do that?

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria, but this time let's up the ante:

GIVEN an array of unsorted numbers
WHEN my algorithm sorts the numbers
THEN the performance is faster than quadratic time complexity

That’s our general outline. We know our input conditions (an unsorted array) and our output requirements (a sorted array), and our goal is to organize the elements in the array in ascending, or non-descending, order with an order better than O(n^2).

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm

If we are writing a sorting algorithm, we need to start with something to sort. Let’s declare an array of ‘unsorted’ integers:

[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

When we are decomposing a problem, we want to break it into the types of problems that need to be solved. We also want to break it into the smallest problems that can be solved.

What’s the smallest problem we can solve?

Two numbers. We can shift the first two off our array…

[10, 1]

… and swap them:

[1, 10]

What is actually happening when we swap values in an array?

We need to slice the values into their own arrays, then concatenate the two arrays in sequential order.

Using our smallest problem as an example, [10, 1], we would break it into the following:

[10], [1]

Then do some conditional checkeroos and concatenate the two arrays back into one:

[1] +  [10] = [1, 10]

Where have we seen this or something like it before?

Divide and conquer!

As we recalled above, in divide and conquer algorithms, we choose a pivot, and continuously divide the problem in two until we find a solution.

If you recall, our pivot is the length of the array divided by two. So, for our smallest problem where the length of our array is 2, our pivot will be 1.

Let's start pseudocoding this:

IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
    RETURN arr

SET pivot TO THE LENGTH OF arr DIVIDED BY 2

Once we set our pivot, we can divide the array in two.

IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
    RETURN arr

SET pivot TO THE LENGTH OF arr DIVIDED BY 2

SET left TO THE ELEMENTS PRECEDING pivot
SET right TO THE ELEMENTS SUCCEEDING pivot

Now what?

Now we need to run those conditional checkerinos and merge the two arrays.

Where have we see this or something like it before?

Merging two arrays!

Because we are pragmatic programmers, we are simply going to "import" that algorithm into this one. We'll do that by wrapping the pseudocode in a "FUNCTION":

FUNCTION merge(left, right)

    SET result TO AN EMPTY ARRAY

    WHILE THERE ARE ELEMENTS IN left OR right

        IF THERE ARE ELEMENTS IN BOTH ARRAYS
            IF THE FIRST VALUE IN left IS LESS THAN THE FIRST VALUE IN right
                SHIFT THE FIRST VALUE OUT OF left AND PUSH IT INTO result
            ELSE
                SHIFT THE FIRST VALUE OUT OF right AND PUSH IT INTO result
        ELSE IF THERE ARE ONLY ELEMENTS IN left
            SHIFT THE FIRST VALUE OUT OF left AND PUSH IT INTO result
        ELSE 
            SHIFT THE FIRST VALUE OUT OF right AND PUSH IT INTO result

    RETURN result

Now we can simply call our merge function in our merge sort algorithm.

IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
    RETURN arr

SET pivot TO THE LENGTH OF arr DIVIDED BY 2

SET left TO THE ELEMENTS PRECEDING pivot
SET right TO THE ELEMENTS SUCCEEDING pivot

RETURN merge(left, right)

Will this work?

Yes, but only if our array contains two elements.

What happens if we double our problem?

[10, 1, 9, 2]

If we follow the logic or our algorithm, we'll divide the array in two:

left = [10, 1]
right = [9, 2]

We'll then call our merge function like so:

merge(left, right)

Within our merge function, we will see that the first value in right is less than the first value in left, so we'll push that to result:

[9]

Uh oh! We're already in trouble!

In the next iteration we'll see that the first (and only) value in right is 2, which is less than the first value in left, 10, so we'll push 2 to result:

[9, 2]

If we follow the logic, we'll end up with a "sorted" array that looks like this:

[9, 2, 10, 1]

Not sorted, but definitely swapped!

What's the solution?

Our merge sort algorithm was beautiful when we were only working with two values.

How do we continually break a problem down into smaller, yet simliar, problems?

Recursion!

We can make recursive calls to merge sort to continually divide our problem in half until we reach our base case, at which point we'll return. And conquer!

Let's update our pseudocode:

FUNCTION merge sort
    IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
        RETURN arr

    SET pivot TO THE LENGTH OF arr DIVIDED BY 2

    SET left TO THE ELEMENTS PRECEDING pivot
    SET right TO THE ELEMENTS SUCCEEDING pivot

    RETURN merge(merge sort(left), merge sort(right))

Execute the Plan

Now it’s simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Merge Sort Algorithm in JavaScript

Let’s start with JavaScript…

const merge = (left, right) => {

    let result = [];

    while(left.length || right.length) {

        if(left.length && right.length) {
            if(left[0] < right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        } else if(left.length) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    return result;
};

const mergeSort = (arr) =>{
    if(arr.length <= 1) {
        return arr;
    }

    const pivot = arr.length / 2 ;
    const left = arr.slice(0, pivot);
    const right = arr.slice(pivot, arr.length);

  return merge(mergeSort(left), mergeSort(right));
};

How to Code the Merge Sort Algorithm in Python

Now let’s see it in Python…

def merge(left, right):
    result = []

    while (len(left) or len(right)):
        if (len(left) and len(right)):
            if (left[0] < right[0]):
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif (len(left)):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result

def merge_sort(list):
    if (len(list) <= 1):
        return list

    pivot = len(list) // 2
    left = list[0:pivot]
    right = list[pivot:]

    return merge(merge_sort(left),merge_sort(right))

Evaluate the Plan

Can we do better?

It depends!

This is a standard implementation of merge sort, but there are still more sort algorithms to learn.

We'll look at quick sort in the next tutorial.

What is the Big O Of Merge Sort Sequence?

The order of our mergeSort algorithm is O(n log n), or log linear. You can learn more in my article on the topic: Big O Log Linear Time Complexity.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Recursive Fibonacci Algorithm

Jared Nielsen — Fri, 19 May 2023 13:13:19 +0000

This article originally published at jarednielsen.com

How to Code the Recursive Fibonacci Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN a number, _n_
WHEN I call a recursive Fibonacci function
THEN I am returned the _nth_ member of the Fibonaccis sequence

That’s our general outline. We know our input conditions, an integer n, and our output requirements, the nth member of the Fibonacci sequence, and our goal is to calculate this recursively.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

If n is equal to 0, what is the equivalent Fibonacci number?

Let's map out the first 10 numbers so we're clear on the goal.

n	nth
0	0
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55

Let's pseudo/hardcode 0:

FUNCTION fibonacci
    INPUT n

    IF n IS EQUAL TO 0 
        RETURN n

What's the next smallest problem?

If we refer to our table above, we see that the result of n = 1 will return 1. We can simply add this to our conditional:

FUNCTION fibonacci
    INPUT n

    IF n IS EQUAL TO 0 OR n IS EQUAL TO 1
        RETURN n

Hey! Look at that. We just establisehd our base case. Now we need to define our recursive case.

Let's look at the next smallest problem, 2.

If our input is 2, what do we expect the return value to be?

1

How do we arrive at 1 in the Fibonacci sequence? It's the sum of the two preceding numbers, 0 and 1.

If our input is 3, what do we expect the return value to be?

2

How do we arrive at 2 in the Fibonacci sequence? It's the sum of the two preceding numbers, 1 and 1.

If our input is 4, what do we expect the return value to be?

3

In order to return a value of 3 when n is equal to 4, we know we need to add 1 and 2, the numbers that precede 3 in the Fibonacci sequence.

Do you see a pattern?

You might be tempated to say that it's simply n - 1, but what if our input is 5? What do we expect the return value to be?

Not 4.

It's 5!

In order to return a value of 5 when n is equal to 5, we know we need to add 2 and 3, the numbers that precede 5 in the Fibonacci sequence.

If we call our Fibonacci function f() for short, we know that:

f(5) = 3 + 2

And...

f(4) = 2 + 1

And...

f(3) = 1 + 1

And...

f(2) = 1 + 0

And f(1) is our base case because there aren't two preceding numbers to add to arrive at this value.

Do you see the pattern?

f(5) = f(4) + f(3)

And...

f(4) = f(3) + f(2)

And...

f(3) = f(2) + f(1)

In other words...

f(5) = (f(3) + f(2)) + (f(2) + f(1))

And so on...

Now we can make the leap to abstraction: the recursive Fibonacci, or f() of n can be expressed as f(n - 1) + f(n - 2). We can translate this to pseudocode:

FUNCTION fibonacci
    INPUT n

    IF n IS EQUAL TO 0 OR n IS EQUAL TO 1
        RETURN n

    RETURN fibonacci(n - 1) + fibonacci(n - 2)

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Recursive Fibonacci Algorithm in JavaScript

Let's start with JavaScript...

const fibonaive = n => {
 if (n == 0 || n == 1) {
   return n;
 }

 return fibonaive(n - 1) + fibonaive(n - 2);
};

How to Code the Recursive Fibonacci Algorithm in Python

Now let's see it in Python...

def fibonaive(n):
    if (n ==0) or (n == 1):
        return n

    return fibonaive(n - 1) + fibonaive(n - 2)

Evaluate the Plan

Can we do better?

We sure can!

Our solution above is referred to as a "naive" implementation of Fibonacci.

Why is it naive? Because the runtime is really bad.

What is the Big O Of Recursive Fibonacci Sequence?

It’s O(2^n).

(Actually, it’s O(1.6^n), but who’s counting?)

If you want to learn how to calculate time and space complexity, pick up your copy of The Little Book of Big O

Take a look at this diagram of our recursive call branches.

Why is this algorithm inefficient?

Overlapping subproblems! We solve the same problems repeatedly in our branches.

How many times do we solve f(0)?

How many times do we solve f(1)?

How many times do we solve f(2)?

How many times do we solve f(3)?

The answer to all of the above is: too many!

What's the solution?

Dynamic programming!

If you want to learn more, check out my article What is Dynamic Programming? Memoization and Tabulation

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Recursive Factorial Algorithm in JavaScript and Python

Jared Nielsen — Fri, 12 May 2023 18:47:55 +0000

This article originally published at jarednielsen.com

How to Code the Recursive Factorial Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN a number, `n`
WHEN I run my `factorial` function
THEN my product is calculated recursively

That’s our general outline. We know our input conditions, a whole number greater than zero, and our output requirements, the factorial product of that whole number, and our goal is to calculate the product recursively.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

n = 1

The result of n! where n is equal to 1 is 1.

INPUT n

RETURN n

Not much of an algorithm, eh?

The next smallest problem to solve is 2. The result of n! where n is equal to 2 is 2:

2 X 1 = 2

Let's hard code this in pseudocode:

INPUT n

IF n is equal to 1
    RETURN n
ELSE
    RETURN n X 1

This will only return the correct factorial if n is equal to 1 or 2. We'll fix this soon enough.

The next smallest problem is 3. The result of n! where n is equal to 3 is 6:

3 X 2 X 1 = 6

How do we pseudocode this?

We could continue to hard code each increment of n in a conditional statement, but that's not the goal or very pragmatic. It's time to look for a pattern! Let's map out the next few increments of n!:

n!	aka	product
1!	1	1
2!	2 X 1	2
3!	3 X 2 X 1	6
4!	4 X 3 X 2 X 1	24
5!	5 X 4 X 3 X 2 X 1	120

Do you see a pattern?

Each factorial is composed of the number, n, multiplied by the previous factorial. For example, 5! can also be expressed as:

5 * 4!

And 4! can also be expressed as:

4 * 3!

And so on...

Let's look at it another way. Using 5! as an example, what is 4 in relation to n when n is equal to 5?

n - 1

And what is 3 in relation to n when n is equal to 5?

n - 2

So... another way to write 5!, where n is equal to 5, could be:

n * (n - 1) * (n - 2) * (n - 3) * (n - 4)

Now we can get abstract! In each iteration, n! is equal to n multiplied by n - 1. We can express this in an equation:

n! = n * (n - 1)!

Where have we seen this or something like it before?

Recursion!

What's our base case?

What's our recursive case?

n * (n - 1)!

Let's translate this to pseudocode:

FUNCTION factorial
    INPUT n
    IF n IS EQUAL TO 0 OR 1
        RETURN 1
    ELSE
        RETURN n * factorial(n - 1)

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Recursive Factorial Algorithm in JavaScript

Let's start with JavaScript...

const factorial = n => {
    if (n == 0 || n === 1) {
        return 1;
    } else {
        return (n * factorial(n - 1));
    }
 };

How to Code the Recursive Factorial Algorithm in Python

Now let's see it in Python...

def factorial(n):
    if (n == 0) or (n == 1):
        return 1
    else: 
        return n * factorial(n - 1)

Evaluate the Plan

Can we do better?

It depends.

While recursion might be mind expanding, it's also space expanding. We want to be concerned about both time and space complexity. Each recursive call to factorial adds another function to the call stack, increasing our memory usage.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Binary Search Algorithm

Jared Nielsen — Fri, 28 Apr 2023 13:34:32 +0000

This article originally published at jarednielsen.com

How to Code the Binary Search Algorithm in JavaScript and Python

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN a sorted array
WHEN I request a specific value
THEN I am returned the location of that value in the array

That’s our general outline. We know our input conditions, a sorted array, and our output requirements, the location of a specific value in the array, and our goal is to improve the performance of a linear search.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

An array containing one number, for example: [1].

Let's pseudocode this:

INPUT arr, num

IF arr[0] == num
    RETURN 'Bingo!'
ELSE 
    RETURN FALSE

This is less of a search and more of a guessing game. What's the next smallest problem? An array containing two numbers: [1, 2].

INPUT arr, num

IF arr[0] == num
    RETURN 'Found num in the 0 index`
ELSE IF arr[1] == num
    RETURN 'Found num in the 1 index`
ELSE 
    RETURN FALSE

This is still a guessing game, but now it's binary! What did we do when we wrote those two conditionals? We cut the problem in half: [1] and [2].

Let's add one more: [1, 2, 4]. Now what? We could write conditionals for every index, but will it scale?

Can we cut this array in half? Not cleanly.

But we can select the index in the middle and check if it's greater or less than num. If num is less than the middle index, we will pivot and compare the preceding value. And if num is greater than the middle index, we will pivot and check the succeeding value. Hey! Let's call this index pivot.

If our array is [1, 2, 4], the our pivot is 2. Let's pseudocode this:

INPUT arr, num

SET pivot TO arr[1]

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    RETURN 'Found num in the 0 index'
ELSE 
    RETURN 'It's gotta be in the 2 index...'

Let's work with a slightly larger array: [1, 2, 4, 8].

There are a few small problems we need to solve here:

In order to scale, we can no longer "hard code" the value stored in pivot.
There's no "middle index". So what value do we choose for pivot?

Let's address the first problem first: we can simply divide the array in two.

INPUT arr, num

SET pivot TO LENGTH OF arr DIVIDED BY 2

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    RETURN 'Found num in the 0 index'
ELSE 
    RETURN 'It's gotta be in the 2 index...'

Using the example above, our array contains four elements. If we divide the length of our array by two, pivot will be equal to 2.

If pivot is equal to 2, the value at that index in our array is 4.

But what if there's an odd number of elements in the array?

[1, 2, 3, 4, 5]

If we divide the length of the array by 2, we get 2.5.

We simply need to round up or down. Let's round down. Our pseudocode now reads:

INPUT arr, num

SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    RETURN 'Found num in the 0 index'
ELSE 
    RETURN 'It's gotta be in the 2 index...'

When we divide the length of this array by 2 and floor the returned value, our pivot is equal to 2.

The value stored in the 2 index is 3.

Previously, we hard coded the conditional checks on either side of the pivot. Will that work here?

No, because there are now two values we need to check on either side of our pivot.

It's time to iterate!

Because we don't know how long our loop needs to run, let's use a while. Our while loops need a conditional. What do we want to use here?

If pivot is less than num, then on the next iteration we need to start with a value greater than pivot. But we need to ensure we are still checking all of the values greater than pivot.

And if pivot is greater than num, then on the next iteration we need to start with a value less than pivot. And, as above, we need to ensure we are still checking all of the values less than pivot.

Do you see a pattern?

Before we implement our while iteration, let's translate these conditionals to pseudocode:

INPUT arr, num

SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2

IF arr[pivot] == num
    RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
    START SEARCHING IN THE NEXT ITERATION AT pivot + 1
ELSE 
    SEARCH UP TO pivot - 1 IN THE NEXT ITERATION

Let's step through a hypothetical scenario using our five element array and searching for 5.

On our first iteration, we set pivot to 3.

We start our conditional checks and see that pivot is not equal to num, but that it is less than num. We can now ignore the values up to and including pivot.

In the next iteration, we'll start searching at pivot + 1, which is 4.

What happens in the next iteration?

We set pivot to the floor of the length of our array divided by 2, which is 2.

Hey! Wait! We already checked this value.

We need a new pivot.

We need to set a pivot from the remaining values to be checked. In our case, that's:

[4, 5]

If we floor the length of this array divided by 2, we get 1. But we know that's not actually the 1 index.

What do we do here?

We get abstract!

Let's declare variables to store these values in each iteration:

SET start index TO 0
SET end index TO THE LENGTH OF THE ARRAY - 1

Finally, we need to refactor our conditional statements to reassign these values in each iteration:

INPUT arr, num

SET start index TO 0
SET end index TO THE LENGTH OF THE ARRAY - 1

WHILE
    SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2

    IF arr[pivot] == num
        RETURN 'Found num at pivot'
    ELSE IF arr[pivot] < num
        SET start index TO pivot + 1
    ELSE 
        SET end index TO pivot - 1 
RETURN FALSE

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Binary Search Algorithm in JavaScript

Let's start with JavaScript...

const powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512];

const binarySearch = (arr, num) => {

   let startIndex = 0;
   let endIndex = (arr.length)-1;

   while (startIndex <= endIndex){

       let pivot = Math.floor((startIndex + endIndex)/2);

       if (arr[pivot] === num){
            return `Found ${num} at ${pivot}`;
       } else if (arr[pivot] < num){
           startIndex = pivot + 1;
       } else {
           endIndex = pivot - 1;
       }
   }
   return false;
}

How to Code the Binary Search Algorithm in Python

Now let's see it in Python...

import math

powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512]

def binarySearch(arr, num):

   startIndex = 0
   endIndex = len(arr)-1

   while (startIndex <= endIndex):

       pivot = math.floor((startIndex + endIndex)/2)

       if (arr[pivot] == num):
            return f"Found {num} at index {pivot}"
       elif (arr[pivot] < num):
           startIndex = pivot + 1
       else:
           endIndex = pivot - 1

   return false

Evaluate the Plan

Can we do better?

Of course! This is just the beginning of our exploration of search algorithms. There are variations on binary search as well as data structures based on binary search that improve the performance.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Selection Sort Algorithm in JavaScript and Python

Jared Nielsen — Fri, 21 Apr 2023 15:53:06 +0000

This article originally published at jarednielsen.com

How to Code the Selection Sort Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN an unsorted array of integers
WHEN we find the lowest unsorted value
THEN we move that value to its proper ordinal position and repeat until all values are in sequence

That’s our general outline. We know our input conditions, an unsorted array, and our output requirements, a sorted array, and our goal is to organize the elements in the array in ascending, or non-descending, order, starting with the smallest elements first.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

We need something to sort, so let's use this "unsorted" array:

[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

The first step in our process is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

[10, 1]

We see that we simply need to swap the positions of these two values. Let's pseudocode a solution to this very small problem:

INPUT array
SET first EQUAL TO THE VALUE STORED IN array[0]
SET next EQUAL TO THE VALUE STORED IN array[1]
IF next IS LESS THAN first 
    SWAP first AND next

So far so good! Let's expand our array and add another value:

[10, 1, 9]

We could hardcode another conditional to check the value stored in the third index, but we're programmers. We immediately recognize a pattern emerging where we will need to select the first value and not only compare it to the second value, but to the third value as well. And then select the second value, and compare it to the third value, all while swapping the location of values when necessary. We need to iterate.

Let's update our pseudocode:

INPUT array
FOR EACH index IN array:
    SET first EQUAL TO THE VALUE STORED IN array[0]
    SET next EQUAL TO THE VALUE STORED IN array[1]
    IF next IS LESS THAN first
        SWAP first AND next

Let's step through this...

On the first iteration, we select the first element, 10, and compare it to the next element, 1, which is less than 10, so we swap their positions. Our array now looks like this:

[1, 10, 9]

But! What happens in the next iteration? We again select the first element and compare it to the next element, which is now 9. 9 is greater than 1, so we leave it where it is.

What's the solution?

Abstraction!

We need a means of tracking and updating the index of the "known minimum value".

In this scenario, 1 is our first "known minimum value", but we can see that 9 is less than 10, so after we move 1, the current "known minimum value" to the 0 index, we need to find the next "known minimum value" and compare that to the next value and swap accordingly.

Let's refer to the "known minimum value" as min.

INPUT array
FOR EACH index IN array:
    SET min EQUAL TO index 
    SET next EQUAL TO index + 1
    IF THE VALUE STORED IN array[next] IS LESS THAN THE VALUE STORED IN array[min]:
        SET min EQUAL TO next
        SWAP THE VALUE STORED IN array[index] WITH THE VALUE STORED IN array[min]

Let's iterate over our array again:

[10, 1, 9]

On the first iteration, we select 10 because it's the first element, and the value stored inarray[min]. If the value stored in next, in this case 1, is less than the value stored in min, which it is, we reassign min the value of next. So min is now equal to 1. Now we need to swap the value currently stored in array[index], 10, with the value stored in array[min], 1. After the first iteration, our array looks like this:

[1, 10, 9]

On the next iteration, index is equal to 1, so we reassign the value of min with 1. We then reassign the value of next with index + 1, or 2. We compare the value stored in array[next], which is 9, with the value stored in array[min], which is 10. Our conditional evalutes as true, so we reassign the value of min with the value of next and then swap the value stored in array[index] with the value stored in array[min]. Our array now looks like this:

[1, 9, 10]

So far so good. Let's add another value to our array:

[10, 1, 9, 2]

Let's fast forward to the fourth iteration, where our array looks like this:

[1, 9, 10, 2]

What's going to happen here? We're only going to swap the locations of 2 and 10. Our array will look like this:

[1, 9, 2, 10]

What's wrong with our design?

We are only comparing the iterator, index, to the next value.

What's the solution?

Nested iteration. We need to compare every index to all of the following values in the array. Let's update our pseudocode:

INPUT array
FOR EACH index IN array
    SET min EQUAL TO index
    SET next TO index + 1
    FOR EACH next IN array
        IF THE VALUE STORED IN array[next] IS LESS THAN THE VALUE STORED IN array[min]
        SET min EQUAL TO next
    SWAP THE VALUES STORED IN array[index] WITH THE VALUE STORED IN array[min]

Let's step through our pseudocode, using this array:

[10, 1, 9, 2]

On the first iteration of our outer loop, we set min to index, or 0. We then enter our nested loop to iterate over the remaining, or next elements. The next element is equal to index + 1. which in this iteration is 1. Our conditional checks if the value stored in our array at index 1 is less than the value stored in our array at index 0. If this evaluates as true, we set the value of min equal to next. In this iteration, array[next] is equal to 1 and array[index] is equal to 10, so we set min equal to the value stored in next, which is 1. We are still in our nested loop, so we continue comparing the remaining values to min and discover that 1 is the lowest value in our array. We exit our nested loop and swap the value in the 0 index, which is 10, with the vale in the min index, which is 1. Our array now looks like this:

[1, 10, 9, 2]

We are now iterating at the level of our outer loop again, and we select the value in the 1 index, which is now 10. We assign it to min and enter our nested loop. The next value is 9, which is less than 10, so we assign the index of next, which is 2 to min. We continue iterating over the remaining values in our array and find that the next value, 2, is less than 9, so we assign the index of next, which is 3, to min. We exit our nested loop and swap the value stored at array[index] with the value stored in array[next]. Our array now looks like this:

[1, 2, 9, 10]

Looks like a solid plan!

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language. Let's start with JavaScript...

How to Code the Selection Sort Algorithm in JavaScript

Let's translate our pseudocode to JavaScript:

const selectionSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        let tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    return arr;
};

How to Code the Selection Sort Algorithm in Python

Now let's see it in Python...

unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

def selection_sort(arr):
    for i in range(len(arr)):
        min = i

        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min]:
                min = j

        tmp = arr[i]
        arr[i] = arr[min]
        arr[min] = tmp

    return arr

Evaluate the Plan

Can we do better? Do we need to go the end of the array? If our nested loop is comparing the value of the next index to the current index, our outer loop doesn't need to include the last index. We can shave off one operation by setting the condition of our for loop to the length of our array minus 1.

Here it is in JavaScript...

const selectionSort = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        let min = i;

        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        let tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    return arr;
};

Note that we update the second line with the following:

    for (let i = 0; i < arr.length - 1; i++) {

Here it is in Python...

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min = i

        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min]:
                min = j

        tmp = arr[i]
        arr[i] = arr[min]
        arr[min] = tmp

    return arr

As above, note that we simply update the second line with the following:

    for i in range(len(arr) - 1):

Note that we don't - 1 in the condition of the nested loop. If we did, we would never select the final value.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Bubble Sort Algorithm in JavaScript

Jared Nielsen — Fri, 14 Apr 2023 13:51:03 +0000

If you want to think like a programmer, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing common patterns in software development. In this tutorial, you will learn how to code the bubble sort algorithm in JavaScript.

This article originally published at jarednielsen.com

How to Code the Bubble Sort Algorithm in JavaScript

Let's revisit our problem solving heuristic:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let's reframe the problem as acceptance criteria:

GIVEN an array of unsorted numbers

WHEN we compare the values of two adjacent numbers and find them out of non-descending order

THEN we exchange their positions in the array

That's our general outline. We know our input conditions (an unsorted array) and our output requirements (a sorted array), and our goal is to organize the elements in the array in ascending, or non-descending, order.

Let's make a plan!

Make a Plan

Let's revisit our computational thinking heuristics as they will aid and guide is in making a plan:

Decomposition
Pattern recognition
Abstraction
Algorithm

If we are writing a sorting algorithm, we need to start with something to sort. Let’s declare an array of ‘unsorted’ integers:

[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

When we are decomposing a problem, we want to break it into the types of problems that need to be solved. We also want to break it into the smallest problems that can be solved.

What's the smallest problem we can solve?

Two numbers. We can shift the first two off our array...

[10, 1]

... and swap them:

[1, 10]

What about the next smallest problem? If we read between the lines of our acceptance criteria, we will see that we need to check a condition repeatedly, or iterate. Let's translate this to pseudocode:

FOR each element in an unsorted array

    IF the value of the element is greater than the next element

        SWAP the elements

RETURN the sorted array

Will this work? Let's think it through. If we test this with our smallest problem, [10, 1], there's no problem. It works! Let's "run" this program with our full array and map it out in a table...

Iteration	Array
1	[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]
2	[1, 10, 9, 2, 8, 3, 7, 4, 6, 5]
3	[1, 9, 10, 2, 8, 3, 7, 4, 6, 5]
4	[1, 9, 2, 10, 8, 3, 7, 4, 6, 5]
5	[1, 9, 2, 8, 10, 3, 7, 4, 6, 5]
6	[1, 9, 2, 8, 3, 10, 7, 4, 6, 5]
7	[1, 9, 2, 8, 3, 7, 10, 4, 6, 5]
8	[1, 9, 2, 8, 3, 7, 4, 10, 6, 5]
9	[1, 9, 2, 8, 3, 7, 4, 6, 10, 5]
10	[1, 9, 2, 8, 3, 7, 4, 6, 5, 10]

What's the pattern we see?

Our largest value, 10, is swapped with each iteration, but everything else remains the same.

What's the problem?

Our algorithm is only comparing and swapping two adjacent values, not all of the values in the array.

What's the solution?

More loops!

Now that we moved the largest value to the end of the array, we need to start at the beginning again and find the second largest value and move it to the penultimate position. Rinse and repeat. So for each iteration we need a nested iteration.

Here's our updated pseudocode:

FOR each element in an array

    FOR each unsorted element 

        IF the value of the element is greater than the next element

            SWAP the elements

RETURN the sorted array

Will this work? Yes... But! Can we do better? This is the crux of the algorithm, so let's think it through...

If n is the length of our array, does the nested loop need to iterate over n?

No. Why?

With each iteration we are sorting one value so the elements that remain to be sorted are n - 1.

If the starting value of n is 10 and we sort the largest value, 10, in the first iteration, how many elements remain to be sorted?

If the starting value of our next iteration, n - 1, is 9 and we sort the next largest value, also 9, how many elements remain to be sorted?

What is another way of specifying the value of 8?

If n is equal to 10, then n - 2 is equal to 8.

What about 7?

n - 3

See the pattern?

From patterns we can form abstractions.

How do we form abstractions?

Variables!

We can use the counter variable in our for loop to subtract from n.

Let's map it to a table:

i	n - i
1	9
2	8
3	7
4	6
5	5
6	4
7	3
8	2
9	1
10	0

And let's map that to our pseudocode:

FOR each element, _i_, in an array, _n_

    FOR each unsorted element, _j_, in an array, _n - i_ 

        IF the value of _j_ is greater than _j + 1_

            SWAP the elements

RETURN the sorted array

Now that we've got a plan, let's execute it!

Execute the Plan

First, we initialize our array:

const unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5];

Next, let’s declare our Bubble Sort function:

const bubbleSort = (arr) => {
    return arr;
};

Now we simply translate our pseudode line-by-line:

const bubbleSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {

        for (let j = 0; j < arr.length - i; j++) {

            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }

        }

    }

    return arr;
}

Running bubbleSort(unsorted) returns:

[
   1,  2,  3,
   4,  5,  6,
   7,  8,  9,
  10
]

Bubbles, sorted!

Evaluate the Plan

Other than using a different sort algorithm, there a few optimizations we can make to our Bubble Sort function.

Let's start with this line:

    for (let i = 0; i < arr.length; i++) {

Do we need to initialize our counter variable with 0?

No. Why?

Because our nested loop is initialized with 0, which is where the magic is happening. We are guaranteed that the first two values will be compared, so we can initialize our outer loop with 1.

const bubbleSort = (arr) => {
    for (let i = 1; i < arr.length; i++) {

        for (let j = 0; j < arr.length - i; j++) {

            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }

        }

    }

    return arr;
}

We're not done with this line:

    for (let i = 0; i < arr.length; i++) {

What else can we do? Do we need to iterate over the entire length of the array?

No. Why?

Because, as above, our nested loop is comparing the current value and the value next to it, so we can extend our generalization, n - 1, to the outer loop as well.

const bubbleSort = (arr) => {
    for (let i = 1; i < arr.length - 1; i++) {

        for (let j = 0; j < arr.length - i; j++) {

            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }

        }

    }

    return arr;
}

What if the array passed to bubbleSort was already sorted? Or mostly sorted? We wouldn't need to perform all of our iterations. How would we exit? We can declare a swapped variable and with each iteration check whether or not any elements in the array were swapped. If no elements were swapped, then the array is sorted and we can return.

const unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5];

const bubbleSort = arr => {

    let swapped = false

    for (let i = 1; i < arr.length - 1; i++) {
        swapped = false;

        for (let j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }

        if (!swapped) {
            return arr;
        }
    }

    return arr;
}

What if the array passed to bubbleSort was empty? How would we catch that? We could simply check whether or not the length of the array was true or false and return accordingly.

const bubbleSort = arr => {
    if (!arr.length) {
        return arr;
    }

    let swapped = false

    for (let i = 1; i < arr.length - 1; i++) {
        swapped = false;

        for (let j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }

        if (!swapped) {
            return arr;
        }
    }

    return arr;
}

One last optimization, if we wanted, we could get fancy with our swap and use array destructuring:

[a[j], a[j + 1]] = [a[j + 1], a[j]];

A is for Algorithms

💯 Give yourself an A. Grab your copy of A is for Algorithms

How to fix the git warning "ECDSA host key for 'github.com' differs from the key for the IP address '140.82.113.3'"

Jared Nielsen — Sat, 08 Apr 2023 14:38:10 +0000

If GitHub's recent RSA SSH host key update causes your system to throw this error:

Warning: the ECDSA host key for 'github.com' differs from the key for the IP address '140.82.113.3'

The solution is a quick fix. The next lines of the error will read something like this:

Offending key for IP in ~/.ssh/known_hosts:X
Matching host key in ~/.ssh/known_hosts:Y
Are you sure you want to continue connecting (yes/no)?

Where X is the line number containing the IP address we want to remove. So...

Run the following command:

vi ~/.ssh/known_hosts

And ⬇️ to line X and run the following to delete the line and exit vi:

dd
:x

Voila!

How to Merge Two Arrays in JavaScript and Python

Jared Nielsen — Fri, 07 Apr 2023 13:33:29 +0000

This article originally published at jarednielsen.com

How to Code the Merge Two Arrays Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN two sorted arrays
WHEN I pass the two arrays to a `merge` function
THEN I am returned one array containing the values of the original two in sequential order

That’s our general outline. We know our input conditions, two sorted arrays, and our output requirements, one array, and our goal is to merge the two original arrays in sequential order.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

[1], [2]

Let's call these two arrays left and right.

We're going to need to build a new array, so let's call it result.

Here's our pseudocode so far:

INPUT left, right

SET result TO AN EMPTY ARRAY

If the value stored in left is less than the value stored in right, we simply shift the value in left into our result array. Let's pseudocode that...

INPUT left, right

SET result TO AN EMPTY ARRAY 

IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
    SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right

We can use our ELSE to check the opposite, where the first element in right is less than left:

INPUT left, right

SET result TO AN EMPTY ARRAY 

IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
    SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
ELSE 
    SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

Will this work? If we step through it, we only shift the first value out of left. We need to iterate, but what approach to iteration do we take?

Because we don't know the size of our two arrays in advance and we are "counting down" until both arrays are empty, let's use a while loop.

While what?

While there are still values to evaluate in left or right.

INPUT left, right

SET result TO AN EMPTY ARRAY 

WHILE THERE ARE VALUES IN left OR right
    IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
        SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
    ELSE 
        SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

Let's step through it...

On our first iteration, left is 1 and right is 2. The result of the evaluation in our conditional is that left is less than right, so we shift 1 off left into result.

On the second iteration, left is empty and right is still 2. The result of the evaluation in our conditional is... what?

Well... it depends. If your language is JavaScript, then yes, right, will evaluate as less than an empty array. But if your language is Python, you are going to get an error.

Why?

Types.

JavaScript is weakly typed, meaning we can be sloppy with our operators.

But Python is strongly typed, so type matters and we can't compare a numerical value to an empty error and get the results we expect.

So... what's the solution?

We know we need to compare the values in both arrays. But we now know we only need to compare the values in both arrays when there are values to compare.

Where have we seen this or something like it before?

Conditionals!

And?

Operators!

Let's use the logical operator AND and only compare both arrays if thec ondition evaluates as true. If we add this to our pseudocode...

INPUT left, right

SET result TO AN EMPTY ARRAY 

WHILE THERE ARE VALUES IN left OR right

    IF THERE ARE ELEMENTS IN left AND right
        IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
            SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
        ELSE 
            SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

What do we do when the AND operator does not evluate as true? If it's not true, we check if there are any values in left. Otherwise, we check if there are any values in right. In both cases, we push the value to result.

Here's our complete pseudocode:

INPUT left, right

SET result TO AN EMPTY ARRAY

WHILE THERE ARE ELEMENTS IN left OR right
    IF THERE ARE ELEMENTS IN left AND right
        IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
            SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
        ELSE 
            SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left
    ELSE IF
        SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
    ELSE
        SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Merge Two Arrays Algorithm in JavaScript

Let's start with JavaScript...

const merge = (left, right) => {

    let result = [];

    while(left.length || right.length) {

        if(left.length && right.length) {
            if(left[0] < right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        } else if(left.length) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    return result;
};

How to Code the Merge Two Arrays Algorithm in Python

Now let's see it in Python...

def merge(left, right):
    result = []

    while (len(left) or len(right)):
        if (len(left) and len(right)):
            if (left[0] < right[0]):
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif (len(left)):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result

Evaluate the Plan

Can we do better?

We could get fancy with our conditionals and operators, but we wouldn't get a performance boost in doing so, just bonus points.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Array Partition Algorithm in JavaScript and Python

Jared Nielsen — Fri, 31 Mar 2023 13:26:57 +0000

This article originally published at jarednielsen.com

How to Code the Array Partition Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN an unsorted array and a range of indexes to partition between
WHEN I select a pivot value from the array and partition the array on the pivot
THEN I am returned the index of the pivot

That’s our general outline. We know our input conditions, an unsorted array and starting and ending values for the partition, and our output requirements, the index of the value used to partition the array, and our goal is to partition the array on a pivot with lower values on the left and higher values on the right.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

An array with two elements:

[1, 2]

Easy!

It's already done.

What if the array was reversed?

[2, 1]

Where have we seen this or something like it before?

Swap!

Because we are pragmatic programmers, we're going to repurpose our swap algorithm and copy/pasta it right here:

FUNCTION swap(arr, left, right)
    SET temp TO THE VALUE STORED IN arr[left]
    SET arr[left] TO THE VALUE STORED IN arr[right]
    SET arr[right] TO THE VALUE STORED IN temp

    RETURN arr

If we pass our two element array to our swap function, the output will be:

[1, 2]

But! We didn't partition on a pivot. We could pivot on one of the two existing values, but let's make it more fun and add another element to our array:

[3, 2, 1]

How do we choose our pivot?

In our array above, we could simply choose the second element containing the value 2. But what if our array looked like this?

[3, 1, 2]

Or this?

[2, 1, 3]

We don't know what our array will look like, so we need to find a programmatic approach and not try to brute force it.

We could iterate through the array, get the sum of all of the values, divide by 2, floor that value, and use it as the pivot, but that adds at least one more step to finding our solution.

What if we just select a random value from the array for the pivot?

We could generate a random number, but because we don't know what the array looks like, we can just select any value.

Which element do we select?

We know we're going to need to iterate and the standard approach to iteration is starting at 0 and incrementing by 1 to n. So let's take the path of least resistance and select n, the last, or right element in the array.

We know we need to return the index, so we're going to need to declare an index variable. But how do we initialize it?

If we're starting at left, let's set our index to left.

Let's pseudocode what we identified so far...

FUNCTION partition(arr, left, right)
    SET index TO left
    SET pivot TO arr[right]

    ...

    RETURN index

We want to start iterating at left and only iterate up to right. Rather than starting at 0, we need to begin our iteration with left, which may or may not be 0. Our for loop needs to look something like this:

FUNCTION partition(arr, left, right)
    SET index TO left
    SET pivot TO arr[right]

    FOR EACH VALUE i BETWEEN left AND right

        ...

    RETURN index

Now what?

As we iterate over the array, we need to compare the value stored in arr[i] to our pivot. What comparison are we making?

Less than?

Greater than?

Table time!

Let's map each iteration using this array:

[3, 1, 2]

This is what we know on our first iteration:

i	arr[i]	pivot	index	arr[index]
0	3	2	0	3

Our index variable and our iterator, i, are both indexing the value 3 in our arry. We can see that this value is greater than our pivot, 2. Let's see what happens in the next iteration:

i	arr[i]	pivot	index	arr[index]
0	3	2	0	3
1	1	2	0	3

Do you see a pattern? Or at least the emergence of a pattern?

Note that the value of arr[i] is now 1, but the value of arr[index] is still 3.

We need to swap the values stored in arr[i] and arr[index], so our comparison is:

        IF arr[i] IS LESS THAN pivot
            swap(arr, index, i)

And before we exit the conditional, we need to increment index.

Our pseudocode now looks like this:

FUNCTION partition(arr, left, right)
    SET index TO left
    SET pivot TO arr[right]

    FOR EACH VALUE i BETWEEN left AND THE LENGTH OF arr
        IF arr[i] IS LESS THAN pivot
            swap(arr, index, i)
            INCREMENT index BY 1

    RETURN index

And our array now looks like this:

[1, 3, 2]

But in our final iteration, our condition won't be met, so how do we make that final swap?

Let's look at that table again:

i	arr[i]	pivot	index	arr[index]
0	3	2	0	3
1	1	2	0	3
2	2	2	1	3

Our index value is correct, but the value stored in arr[index] is not. Where is that value? At the end, or right of the array. So let's swap 'em!

Our final pseudocode looks like this:

FUNCTION partition(arr, left, right)
    SET index TO left
    SET pivot TO arr[right]

    FOR EACH VALUE i BETWEEN left AND THE LENGTH OF arr
        IF arr[i] IS LESS THAN pivot
            swap(arr, index, i)
            INCREMENT index BY 1

    swap(arr, index, right)

    RETURN index

Let's step through this using a slightly larger array:

[5, 1, 4, 2, 3]

When we call our partition function, we'll use the default values of the first and last element for left and right, so left will be equal to 0 and right will be equal to the length of our arrary minus 1.

We then set our index to left and our pivot to the value stored in arr[right]. In this case, that's 3.

When we begin iterating, i is equal to left, which is 0.

The value stored in arr[i] is 5.

5 is not less than 3, so we leave it.

In the next iteration, i is equal to 1.

The value stored in arr[i] is now 1.

1 is less than 3, so we swap the values in arr[index] and arr[i], here that's 5 and 1.

Now our array looks like this:

[1, 5, 4, 2, 3]

We increment our index by 1, so its value is now 1.

In the next iteration, i is equal to 2.

The value stored in arr[i] is now 4.

4 is not less than 3, so we leave it.

In the next iteration, i is equal to 3.

The value stored in arr[i] is now 2.

2 is less than 3, so we swap the values in arr[index] and arr[i], here that's 5 and 2.

Now our array looks like this:

[1, 2, 4, 5, 3]

We increment our index by 1, so its value is now 2.

In the next iteration, i is equal to 4.

The value stored in arr[i] is now 3.

3 is not less than 3, so we leave it and exit our loop.

We still need to get our pivot in the right place, and we do this by swapping the value stored in arr[index] with the value stored in arr[right], which are 4 and 3 respectively.

Now our array looks like this:

[1, 2, 3, 5, 4]

Finally, we return our index, which is 2, where the value of our pivot is currently stored in the array.

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Array Partition Algorithm in JavaScript

Let's start with JavaScript...

const swap = (arr, left, right) => {
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;

    return arr;
}

const partition = (arr, left = 0, right = arr.length - 1) => {

    let index = left; 
    let pivot = arr[right];

    for (let i = left; i < right; i++) {
        if (arr[i] < pivot) {
            swap(arr, index, i);
            index++;
        }
    }
    swap(arr, index, right);

    return index;
}

How to Code the Array Partition Algorithm in Python

Now let's see it in Python...

def swap(arr, left, right):
    temp = arr[left]
    arr[left] = arr[right]
    arr[right] = temp

    return arr

def partitionLomuto(arr, left = 0, right = None):

    if right == None: 
        right = len(arr) - 1

    pivot = arr[right]
    index = left

    for i in range(left, right):
        if arr[i] < pivot:
            swap(arr, index, i)
            index += 1

    swap(arr, index, right)

    return index

Evaluate the Plan

Can we do better?

Yes!

This algorithm is using the Lomuto partition scheme. This approach is perfectly fine and perfect for beginners. There is another approach, the Hoare partition scheme, which is more efficient but slightly more complicated. It works by iterating forward and back through the array.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Longest Increasing Subsequence Algorithm

Jared Nielsen — Fri, 17 Mar 2023 13:36:47 +0000

This article originally published at jarednielsen.com

How to Code the Longest Increasing Subsequence Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN an unsorted array of numbers 
WHEN I calculate the longest increasing subsequence
THEN I am returned the length of that sequence

Let's use the first 16 digits following the decimal in Pi for an example.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2

Let's manually find the longest increasing subsequence. We'll place an X under the values in the sequence. The first value is obviously 1.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 
X

The second value is 2.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 
X         X

The third value is 3.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 
X         X     X

The fourth value is 5.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 
X         X     X X

The fifth value is 7.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 
X         X     X X     X

The sixth value is 9.

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 
X         X     X X     X X

The length of the longest increasing subsequence of the first 16 digits of Pi is 6.

That’s our general outline. We know our input conditions, an unsorted array of postiive integers, and our output requirements, the length of the sequence which is a value greater than or equal to 1, and our goal is to find the longest increasing subsequence of values in the array.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. Continuing with the first 16 Pi decimals, what's the smallest problem we can solve?

What's the longest subsequence?

Also 1.

What's the next smallest?

1 4

And what's the longest subsequence?

How did we calculate that?

We can see that there are two values and the last value is greater than the first, so the LIS is equal to 2. In other words, we made a comparison and tallied up the increasing values.

So what's the next smallest problem?

1 4 1

Ah! Now it gets interesting.

But the longest subsequence is still 2.

How do we solve this problem?

Again, we start a tally of increasing values. We know that the LIS is at least 1. We then compare 4 to 1, and, because 4 is greater than 1, we add 1 to our LIS tally. We compare the next value, 1, to 4, and, because 1 is less than 4, we do not add 1 to our LIS tally.

What's the next smallest problem?

1 4 1 5

Just when we thought we found the LIS we add a larger value!

How do we solve this problem?

We need to compare the current LIS, which is 3, with the previous LIS, which is 2.

This is starting to get complicated. We need a way to keep track of all these values. What if we keep a tally? There are a two approaches we can take to creating our tally:

Generate a new array of n length assigning each element a value of 1. On each iteration, reassign the corresponding value with the tally.
Initialize an array with only one element assigned a value of 1. On each iteration, add a new element containing the corresponding value of the tally.

Let's take the second approach. We can implement it without needing to use any constructors or an additional loop to generate the array.

If we start sketching out our pseudocode:

INPUT n

SET result TO 1
SET tally TO [1]

WORK SOME MAGIC! 

RETURN result

Now we need to work some magic.

We know we're going to need to iterate, and, if we need to calculate a result for every value in the array, we're going to need nested iteration.

Let's visualize this. Here's our array of four elements and our tally.

tally = [1]

array = [1, 4, 1, 5]

Following convention, we'll use the variables i and j for our outer and inner loops, respectively.

Let's initialize i with a value of 1 and j with a value of 0.

tally = [1]

            i
array = [1, 4, 1, 5]
         j

Why?

If we initialize i with 0, there's nowhere for j to go. We only need to iterate up to i. If we iterate beyond i in our nested loop, we won't get an accurate result.

In each iteration, we compare the value indexed by i and the value indexed by j. In this iteration, we see that 1 is less than 4. We take the value of our previous LIS, add 1, and update our tally. The LIS is now 2.

We start the next iteration, making the same comparisons as above...

tally = [1, 2]

               i
array = [1, 4, 1, 5]
         j

...until we reach the condition where we compare the value indexed by i and the value indexed by j and see that 4 is not less than 1, meaning our subsequence did not increase, so our LIS is unchanged.

tally = [1, 2]

               i
array = [1, 4, 1, 5]
            j

We still update our tally with this value and start the next iteration of the outer loop.

tally = [1, 2, 2]

                  i
array = [1, 4, 1, 5]
         j

Our nested loop iterates, making the same comparisons as above...

tally = [1, 2, 2]

                  i
array = [1, 4, 1, 5]
            j

...until we reach the condition where the value indexed by j is less than the value indexed by i, meaning our subsequence is increasing. We update the value in tally and exit our loops.

tally = [1, 2, 2, 3]

                  i
array = [1, 4, 1, 5]
               j

Let's update our pseudocode:

INPUT n

SET result TO 1
SET tally TO [1]

FOR EACH VALUE, i, BETWEEN 1 AND THE LENGTH OF n
    SET tally[i] TO 1
    FOR EACH VALUE, j, BETWEEN 0 AND i
        SET lis TO THE VALUE STORED IN tally[j] PLUS 1

        IF THE VALUE STORED IN n[j] IS LESS THAN THE VALUE STORED IN n[i] AND lis IS GREATER THAN THE VALUE STORED IN tally[i]
            SET tally[i] TO THE VALUE STORED IN lis
            IF lis IS GREATER THAN result
                SET result TO THE VALUE STORED IN lis

RETURN result

Let's walk through this. We pass our LIS function an unsorted array, n.

We first initialzie a result variable and give it a value of 1 because we know that the result of our LIS calculation will be at least one.

We next initialize an array, tally, with one element assigned a value of 1. We do this for two reasons:

We know that the longest increasing subsequence is at least 1. It can't be 0.
We need to keep a record of which iteration contained the longest increasing subsquence.

We initialize our outer for loop, beginning the iteration at 1 and iterating up to the length of n. We start iterating at 1 because we use i as the condition in the nested for loop. If we started at 0, the nested loop would not execute its first iteration.

With each iteration of our outer loop, we add another element to our tally array with a value of 1.

We then initialize our nested for loop, beginning the iteration at 0. As above, note that we are iterating up to i. We are only iterating up to i to count the subsequence.

Within the nested loop, we initialize a lis variable.

If the value of n[j]is less than n[i] and the value of lis is greater than the value stored in lengths[i], we set lengths[i] to lis. This is how we store our count and increase it with each iteration.

Before we exit this condition our loops, we check if lis is greater than result. If so, we need to update result with the value stored in lis. Finally, when our iterations are complete, we return result.

Let's just use the first 8 values, [1 4 1 5 9 2 6 5]. The length of the longest increasing subsequence is 4.

Table time!
| i | j | lis | lengths | result |
| --- | --- | --- | --- | --- |
| 1 | 0 | 2 | [ 1, 2, 1, 1, 1, 1, 1, 1 ] | 2 |
| 2 | 0 | 2 | [ 1, 2, 1, 1, 1, 1, 1, 1 ] | 2 |
| 2 | 1 | 3 | [ 1, 2, 1, 1, 1, 1, 1, 1 ] | 2 |
| 3 | 0 | 2 | [1, 2, 1, 2, 1, 1, 1, 1] | 2 |
| 3 | 1 | 3 | [1, 2, 1, 3, 1, 1, 1, 1] | 3 |
| 3 | 2 | 2 | [1, 2, 1, 3, 1, 1, 1, 1] | 3 |
| 4 | 0 | 2 | [1, 2, 1, 3, 2, 1, 1, 1] | 3 |
| 4 | 1 | 3 | [1, 2, 1, 3, 3, 1, 1, 1] | 3 |
| 4 | 2 | 2 | [1, 2, 1, 3, 3, 1, 1, 1] | 3 |
| 4 | 3 | 4 | [1, 2, 1, 3, 4, 1, 1, 1] | 4 |

And so on...

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Longest Increasing Subsequence Algorithm in JavaScript

Let's start with JavaScript...

const longestIncreasingSubsequence = (n) => {
    let result = 1;
    const tally = [1];

    for (let i = 1; i < n.length; i++) {
        tally[i] = 1;
        for (let j = 0; j < i; j++) {
            let lis = tally[j] + 1;

            if (n[j] < n[i] && lis > tally[i]) {
                tally[i] = lis
                if (lis > result) {
                    result = lis;
                }
            }
        }
    }
    return result; 
}

How to Code the Longest Increasing Subsequence Algorithm in Python

Now let's see it in Python...

def longest_increasing_subsequence(n):
    result = 1
    tally = [1]

    for i in range(1, len(n)):
        tally += [1]
        for j in range(i):
            lis = tally[j] + 1

            if (n[j] < n[i] and lis > tally[i]):
                tally[i] = lis

                if lis > result:
                    result = lis

    return result

Evaluate the Plan

Can we do better?

The nested iteration isn't great for performance, but there's no getting around it. There are some refactors we could make. For example, we could use the max methods in our Math modules to find the lis in place of the result reassignment. I prefer this approach as it's more legible.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Code the Sieve of Eratosthenes Algorithm

Jared Nielsen — Fri, 10 Mar 2023 14:23:54 +0000

This article originally published at jarednielsen.com

How to Code the Sieve of Eratosthenes Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN a whole number, _n_, greater than 1
WHEN I pass _n_ to the Sieve function
THEN I am returned a an array of the prime numbers between 1 and _n_

That’s our general outline. We know our input conditions, a whole number greater than 1, and our output requirements, an array of prime number between 1 and n, and our goal is to generate those prime numbers.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

2

Why not 1? Because 1 is not a prime number, so we skip it.

Like writing, there's nothing more terrifying than the blank page, so let's get something started in our pseudocode:

INPUT n
SET primes EQUAL TO AN EMPTY ARRAY

IF n IS EQUAL TO 2
    PUSH n TO primes

RETURN primes

What's the next smallest problem we can solve? 3

We might be tempted to take a brute force approach, and there are at least two:

Create a dataset of all the prime numbers and return all of the values below n.
Check if the remainder of each value in a series is equal to zero when divided by the previous values.

The first option isn't great because it defeats the purpose of programming! We would need an infinite dataset and that's a lot of data entry!

The second option would require us to perform an operation for every value in our series. If our input value was 100, we would need to perform 99 modulo operations in order to find all of the prime numbers.

🍻

What do we know about prime numbers?

A prime number is only divisible by 1 and itself.

Let's take a step back, or up, and look for a pattern. If our input, n, is 100, then the array of primes we want to return needs to contain this sequence:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Do you see a pattern?

No! The problem with primes is that there's no pattern.

Where do we see a pattern? Or patterns?

All of the composite numbers! Each number that we exclude from our final output is composed of two (or more) factors. Rather than find the primes, can we find everything else? Work like Michaelangelo and carve out a solution?

Let's look at all of the numbers between 1 and 100:

[
    1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 
   11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 
   21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
   31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 
   41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
   51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 
   61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 
   71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 
   81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 
   91, 92, 93, 94, 95, 96, 97, 98, 99, 100
]

We know that 1 is not prime, so we can cross it out. And we immediately see that half of our numbers are multiples of 2, so we can cross them all out, but keep 2, as it's the first prime number:

[
    X, 2,  3, X,  5, X,  7, X,  9, X, 
   11, X, 13, X, 15, X, 17, X, 19, X, 
   21, X, 23, X, 25, X, 27, X, 29, X, 
   31, X, 33, X, 35, X, 37, X, 39, X, 
   41, X, 43, X, 45, X, 47, X, 49, X, 
   51, X, 53, X, 55, X, 57, X, 59, X, 
   61, X, 63, X, 65, X, 67, X, 69, X, 
   71, X, 73, X, 75, X, 77, X, 79, X, 
   81, X, 83, X, 85, X, 87, X, 89, X, 
   91, X, 93, X, 95, X, 97, X, 99, X
]

Our next prime number is 3, which we want to keep, but we can proceed and cross out all multiples of 3.

[
    X, 2,  3, X,  5, X,  7, X,  X, X, 
   11, X, 13, X,  X, X, 17, X, 19, X, 
    X, X, 23, X, 25, X,  X, X, 29, X, 
   31, X,  X, X, 35, X, 37, X,  X, X, 
   41, X, 43, X,  X, X, 47, X, 49, X, 
    X, X, 53, X, 55, X,  X, X, 59, X, 
   61, X,  X, X, 65, X, 67, X,  X, X, 
   71, X, 73, X, 75, X, 77, X, 79, X, 
    X, X, 83, X, 85, X,  X, X, 89, X, 
   91, X,  X, X, 95, X, 97, X,  X, X
]

We skip 4 as it's not a prime number and we already crossed it out with multiples of 2. We then cross out multiples of 5:

[
    X, 2,  3, X,  5, X,  7, X,  X, X, 
   11, X, 13, X,  X, X, 17, X, 19, X, 
    X, X, 23, X,  X, X,  X, X, 29, X, 
   31, X,  X, X,  X, X, 37, X,  X, X, 
   41, X, 43, X,  X, X, 47, X, 49, X, 
    X, X, 53, X,  X, X,  X, X, 59, X, 
   61, X,  X, X,  X, X, 67, X,  X, X, 
   71, X, 73, X,  X, X, 77, X, 79, X, 
    X, X, 83, X,  X, X,  X, X, 89, X, 
   91, X,  X, X,  X, X, 97, X,  X, X
]

Next is 7...

[
    X, 2,  3, X,  5, X,  7, X,  X, X, 
   11, X, 13, X,  X, X, 17, X, 19, X, 
    X, X, 23, X,  X, X,  X, X, 29, X, 
   31, X,  X, X,  X, X, 37, X,  X, X, 
   41, X, 43, X,  X, X, 47, X,  X, X, 
    X, X, 53, X,  X, X,  X, X, 59, X, 
   61, X,  X, X,  X, X, 67, X,  X, X, 
   71, X, 73, X,  X, X,  X, X, 79, X, 
    X, X, 83, X,  X, X,  X, X, 89, X, 
    X, X,  X, X,  X, X, 97, X,  X, X
]

Do you see the pattern? We first removed all multiples of 2, then all multiples of 3, followed by 5 and 7. The next prime is 11, and if our array was larger, we would cross out 121, which is only divisible by 1, 11, and itself. We can now abstract a general rule for our algorithm: remove the multiples of the prime numbers, but keep the primes.

Now let's design the algorithm!

We need to generate an array, but We don't need to store the numerical values in the array because we can simply use the index. But, we need to keep in mind that our first index is 0. Because we're using a process of "subtraction", we want to set all of our values to true and then mark everyhing that is not a prime number as false.

Let's update our pseudocode to generate an array of boolean values.

INPUT n

SET bools EQUAL TO AN ARRAY OF LENGTH n
POPULATE EVERY INDEX IN bools WITH A VALUE OF true

...

We'll use the word "POPULATE" as we don't yet know, or need to know, how we will generate an array of boolean values. Maybe we'll iterate. Maybe we'll use an array method. We'll figure that out when we execute the plan. Speaking of iteration, now we need to figure out how we are changing values in our array from true to false.

INPUT n

SET bools EQUAL TO AN ARRAY OF LENGTH n
POPULATE EVERY INDEX IN bools WITH A VALUE OF true

SET primes EQUAL TO AN EMPTY ARRAY

FOR EVERY NUMBER, i, BETWEEN 2 AND num
    IF THE VALUE STORED IN bools[i] IS EQUAL TO true
        PUSH i TO primes

        ...

RETURN primes

If we continue to iterate, our conditional will continue to be met and we will push every number to primes. How do we avoid this?

🤔

We need to set all even numbers to false before we exit the conditional. Sounds like we need another loop. Do we want a for loop or a while loop? Because we don't know how many times we need the loop to run, let's use a while loop. Our nested loop needs an iterator. The convention is to name this variable j. What value do we use to initialize j?

In our first iteration, i is equal to 2, which is prime.

In our second iteration, i will be equal to 3, which is also prime.

In our thrid iteration, i will be equal to 4, which is composite.

We need to set the value of j to 4 in the first iteration.

There are two ways we can do this: addition and multiplication. Let's think through both.

If we use addition, our pseudocode would be:

        SET j EQUAL TO i PLUS 2

This will give us 4 on the first iteration. But on the next iteration, the value of i will be 3 and 3 plus 2 is 5, which is prime. Addition won't work, so let's use multiplication.

What do we do within our while loop? We simply reassign the value of j to j PLUS i. Our pseudocode now looks like this:

INPUT n

SET bools EQUAL TO AN ARRAY OF LENGTH n
POPULATE EVERY INDEX IN bools WITH A VALUE OF true

SET primes EQUAL TO AN EMPTY ARRAY


FOR EVERY NUMBER, i, BETWEEN 2 AND num
    IF THE VALUE STORED IN bools[i] IS EQUAL TO true
        PUSH i TO primes

        SET j EQUAL TO i MULTIPLIED BY 2

        WHILE j IS LESS THAN OR EQUAL TO n
            SET THE VALUE STORED IN bools[j] TO false
            SET THE VALUE OF j TO j PLUS i

RETURN primes

Let's step through our pseudocode to fully understand what's happening before we translate it into syntax.

When our for loop increments, i will be equal to 3, and our conditional will evaluate as true. We push 3 to primes then set the value of j to 3 multiplied by 2, or 6. Within the while loop, we set the value stored in the sixth index to false and then add i, which is 3, to j, which is 6. The new value of j is now 9. We continue to iterate by multiples of 3 until j is greater than or equal to n.

When our for loop increments again, i will be equal to 4. Our conditional will not evaluate as true, though, and we will proceed with the next iteration of the for loop.

When our for loop increments again, i will be equal to 5, and our conditional will evaluate as true. We push 5 to primes then set the value of j to 5 multiplied by 2, or 10. Within the while loop, we set the value stored in the tenth index to false (again) and then add i, which is 5, to j, which is 10. The new value of j is now 15. We continue to iterate by multiples of 5 until j is greater than or equal to n.

When our for loop increments again, i will be equal to 6. Our conditional will not evaluate as true, though, and we will proceed with the next iteration of the for loop.

When our for loop increments again, i will be equal to 7, our conditional will evaluate as true, and we repeat the steps above for 7 and all subsequent values.

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Sieve of Eratosthenes Algorithm in JavaScript

Let's start with JavaScript...

const sieve = (num) => {
    const bools = new Array(num + 1).fill(true);
    bools[0], bools[1] = false;

    const primes = [];

    for (let i = 2; i <= num; i++) {
        if (bools[i] === true) {
            primes.push(i);

            let j = i * 2;

            while (j <= num) {
                bools[j] = false;
                j += i;
            }
        }
    }

    return primes;
}

Let's step through this solution:

Within our sieve function, we first declare a bools array, using the Array constructor. We create the new array with a single parameter, num + 1. Why do we add 1? Because we start counting at 0. We then use the .fill() method to fill the bools array with elements equal to true. Because we know 0 and 1 are not prime, we assign bools[0] and bools[1] a value of false. We then declare an empty array, primes.

Next, we declare a for loop and initialize the iterator with a value of 2. Why 2? It's the first prime number and we already assigned bools[0] and bools[1] a value of false. Within our for loop, we declare a conditional. If the value of bools[i] is equal to true, we push it to the primes array.

Here's the fun part: within our conditional, we declare a variable, j, and assign it the value of i * 2. We then initialize a while loop, and, while j is less than or equal to n, we set the value of bools[j] to false and increment by i, using j += i.

Why? With the exception of 2, none of our prime numbers are even. By multiplying i by 2, we create a composite value to then mark false.

While j is less than n, we continue to iterate. For example, in the first iteration, i is 2. Because everything but the first two elements in bools is marked true, we push 2 to the primes array. We then set the value of j to i * i, or 2 * 2, of 4. While j, which is currently 4, is less than n, we set the value of bools[j] to false because it is true, 4 is not a prime number. We then add i, which is currently 2, to j, which is currently 4, resulting in 6. Looping again, we set the value of bools[j] to false, because it's true, 6 is not a prime number. The next iteration j would be 8, then 10, then 12, and so on until all even values were marked false.

When j is no longer less than or equal to n, we exit the while loop, exit the if block, and then enter the next iteration of our for loop where i is equal to 3. We skipped over 3, so it is still marked true, and we push it to primes. We then multiply 3 by 3, and assign j the value of 9. We set bools[j] to false and then add 3 to j, resulting in 12. This is redundant, because we already marked 12 as false, but ¯_(ツ)_/¯. In the next iteration, we mark 15 as false. We iterate until all multiples of 3 are marked false.

When j is no longer less than or equal to n, we exit the while loop, exit the if block, and then enter the next iteration of our for loop where i is equal to 4. We already marked 4 as false, so we don't enter the conditional block and continue iterating with a value of 5 assigned to i. It's still marked as true, because we skipped over it in the first and second iteratons, 2 and 3 respectively. We then multiply 5 by 5, and assign j the value of 25. We set bools[j] to false and then add 5 to j, resulting in 30. This is redundant, because we already marked 30 as false, but again, ¯_(ツ)_/¯. In the next iteration, we mark 35 as false. We iterate until all multiples of 5 are marked false.

We continue iterating over n until all elements associated with composite numbers in bools are marked false. The next prime is 7, and we set the value of j to 7 * 7, or 49, and then proceed to mark all multiples of 7 as false. The next prime is 11, when squared is 121, and so on.

Now let's see it in Python...

How to Code the Sieve of Eratosthenes Algorithm in Python

Let's see it in Python...

def sieve(n):
    bools = [True for i in range(n + 1)]
    # bools = [True] * (n + 1)
    bools[0] = False
    bools[1] = False

    primes = []

    for i in range(2, n):
        if bools[i] == True:
            primes.append(i)

        j = i * 2

        while j <= n:
            bools[j] = False
            j += i 

    return primes 

result = sieve(100)

print(result)

Evaluate the Plan

Can we do better?

We can make an optimization to our program and multiple i by itself rather than by 2:

INPUT n

SET bools EQUAL TO AN ARRAY OF LENGTH n
POPULATE EVERY INDEX IN bools WITH A VALUE OF true

SET primes EQUAL TO AN EMPTY ARRAY


FOR EVERY NUMBER, i, BETWEEN 2 AND num
    IF THE VALUE STORED IN bools[i] IS EQUAL TO true
        PUSH i TO primes

        SET j EQUAL TO i MULTIPLIED BY i

        WHILE j IS LESS THAN OR EQUAL TO n
            SET THE VALUE STORED IN bools[j] TO false
            SET THE VALUE OF j TO j PLUS i

RETURN primes

While this solution is more efficient in terms of time complexity, it's not so great for space because we need to generate an array of boolean values.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms

How to Convert Decimal to Hexadecimal in JavaScript and Python

Jared Nielsen — Fri, 03 Mar 2023 12:45:07 +0000

If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to convert numbers from decimal to hexadecimal in JavaScript and Python.

This article originally published at jarednielsen.com

How to Code a Decimal To Hexadecimal Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN a decimal
WHEN I pass it to a function
THEN the function returns the hexadecimal equivalent

That’s our general outline. We know our input conditions (a decimal) and our output requirements (a hexadecimal equivalent value), and our goal is to perform the conversion of the decimal to hexadecimal.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm

If converting a decimal to binary is simply a process of repeatedly dividing the decimal by 2 and using the remainder to build a string, how do you think we convert a decimal to any base?

We divide the decimal by the base!

Let's break that question down into smaller questions.

What is a number?

It's a symbol representing a value.

What is 1?

A symbol representing the value one.

What is 'one'?

A symbol representing the value 1. (And round and round we go...)

What is 10?

In the decimal, or base-10, numeral system, it's a value represented by two symbols. Because it's two symbols, we can't use it in base-16. What's the solution? More symbols!

Hexadecimal, or base-16, uses the first six characters of the Roman alphabet to represent the values of 10 through 15.

Decimal	Hexadecimal
10	A
11	B
12	C
13	D
14	E
15	F

If we wanted to create our own base, say, Emojidecimal, we could use whatever symbols we want:

Decimal	Hexadecimal
10	🍎
11	🍌
12	🐈
13	🐕
14	🐘
15	🦊

The symbol doesn't matter, as long as we all agree on the value that it represents. Do you think Emojidecimal will gain traction? 🤔

Let's convert 2047 to hexadecimal. The first step is to get the remainder of our dividend and divisor.

2047 % 16 = 15

Our remainder is 15, but we are no longer using base-10, so we can't add this value to our hexadecimal string. If we use the table we created above, we can see that 15 maps to F, so we start building our hexadecimal string with it, giving us:

The next step is to divide:

2047 / 16 = 127

Our quotient is 127, so we repeat the operations above:

127 % 16 = 15

Our remainder is again 15, so we add F to our hexadecimal string, giving us:

FF

We then divide 127 / 16. Our quotient is 7, so we calculate the remainder and divide 7 by 16:

7 % 16 = 7
7 / 16 < 0

Our remainder is 7, so we add it to our hexadecimal string, giving us:

7FF

INPUT NUM

SET digits TO "0123456789ABCDEF"

SET result TO AN EMPTY STRING

WHILE num IS GREATER THAN 0
  GET VALUE OF num MOD 16
  PREPEND result WITH CORRESPONDING VALUE IN digits
  REASSIGN num THE FLOOR VALUE OF decimal DIVIDED BY 2

OUTPUT result

Execute the Plan

Now it's simply a matter of translating our pseudocode into syntax. Let's start with JavaScript.

How to Code Decimal to Hexadecimal Conversion in JavaScript

Rather than prepending each remainder, we instead concatenate the result string and use a combination of string and array methods to split the string into array items, reverse the order of the array, and then join the items in a string.

const decimalToHex = (num) => {

  const digits = '0123456789ABCDEF';

  let result = '';

  while (num > 0) {
    result += digits[num % 16];
    num = Math.floor(num / 16);
  }

  return result.split('').reverse().join('');
}

How to Code Decimal to Hexadecimal Conversion in Python

def decimal_hexadecimal(num):
    digits = '0123456789ABCDEF'

    result = ''

    while num > 0:
        result += digits[num % 16]
        num = num // 16

    return ''.join(reversed(result))

Evaluate the Plan

Let's take another look at our JavaScript above. We could modify that function to accept any base, not just 16.

const decimalToBase = (num, base) => {

  const digits = '0123456789ABCDEF';

  let result = '';

  while (num > 0) {
    result += digits[num % base];
    num = Math.floor(num / base);
  }

  return result.split('').reverse().join('');
}

The split() method converts the string to an array, so we could just start with an array instead and use unshift() rather than reverse() (J4F):

const decimalToBase = (num, base) => {

  const digits = '0123456789ABCDEF';

  let result = [];

  while (num > 0) {
    result.unshift(digits[num % base]);
    num = Math.floor(num / base);
  }

  return result.join('');
}

Or we could just cheat and use the built-in toString() method and pass it 2 as an argument, meaning we want to convert our string to binary:

const decimalToBase = (num, base) => num.toString(base);

We could make the same optimizations in our Python function, or we could use built-in hex() method.

But what fun is that?

A is for Algorithms

💯 Give yourself an A. Grab your copy of A is for Algorithms