A Gentle Introduction To Computer Algorithms: Implementing the Bubble Sort algorithm in six languages.

A Gentle Introduction To Computer Algorithms: Implementing the Bubble Sort algorithm in six languages (Python, JavaScript, C++, C, Java, PHP)

Computer algorithms form one of the two core pillars of computer science (the other being data structures) and a comfortable understanding of algorithms is necessary for the programmer/developer who is intent on standing out in the field. In this article we will explore a succint overview of computer algorithms, the necessity of their study, their applications, as well learn to write one all by ourselves. The code (which comes towards the end of this article) is written in five of the most popular languages so that almost anybody can follow. All one has to do is read along with the language one is most familiar with.

The code in this article is available on GitHub here. Click on the appropriate file to view/save the source code for the algorithm in your language (C, C++, Java, JavaScript, PHP, Python).

A Gentle Dive

Computer science developed from humankind's innate need for tooling: our primal drive to find easier, faster, more efficient ways of solving problems. In the case of the first computer, the abacus, humankind wanted a way to perform basic arithmetic under the hot and scorching sun of their open-air market stalls. Think about it: if you lived 4400 years ago (in a world without iPhones and the Internet, mind you), would you:

1. Want to tally your pebbles by hand every time?

or

1. Carry around a wooden box capable of keeping track of your profit for you?

Yeah. I knew you'd choose (2).

So, the abacus is humankind's earliest recognized attempt at teaching a machine (aka, a tool) to accomplish a task. Prior to that point in time, we had tried to teach the animals, but you know how poorly horses count!

So, the most basic lesson in this article is this: "Don't be afraid of algorithms. An algorithm is only a textbook for machines (and machines are merely tools, unless you're like me and you call them "pals") to 'read' and 'learn' from. Algorithms are nothing to be afraid of."

An algorithm is only a textbook for machines to "read" and "learn" from.

I make this point here, before you read any further, because for many people, the word "algorithm" is like a scare-crow in the barn at night. Many programmers, especially inexperienced ones, tend to avoid the subject entirely. Until they need to prepare for a interview. This world-wide fear of the second pillar of computer science is probably due to three factors, which I outline here:

1. Algorithms often (but not always) involve some kind of math.
2. Algorithms are often taught at universities by old, gray-haired professors in an old, gray-haired language like C. Many programmers who were formally trained in the craft graduate with an ingrained fear of the subject.
3. At least 50% of programmers alive** today have not received any formal instruction in computer science. They are self-taught, and usually one finds that the self-taught programmer skipped the basics (data structures and algorithms) in a hurry to start the application development part (web development, for example).

To every self-taught programmer who reads this: you're one of the most inspiring people in the world. I appreciate and admire you. Keep up the good work!

So, as I said earlier, we find many programmers who fear algorithms: the purpose of this article is to remedy that in some small, humble way.

What, Exactly, Is An Algorithm?

I won't bore you with the etymology of the word (which you can find by doing a web search). An algorithm is a process, often logical, that you pass to a computer (aka "machine", double aka "just a tool") to "teach" it to solve a problem. The website Britannica.com explains:

An algorithm is a specific procedure for solving a well-defined computational problem.
Algorithms and Complexity, Britannica.com

Britannica continues: "It requires an understanding of the alternatives available for solving a computational problem, including the hardware, networking, programming language, and performance constraints that accompany any particular solution."

Algorithms are used everywhere. When you pick up your smartphone and place a call to a friend, several algorithms make the connection, convert your voice (sound) to signals (electricity), convert these signals to radio waves, and "push" the waves far enough to a cell tower where other algorithms perform really complicated operations on the radio waves that make it possible for your friend's phone to ring. In fact, algorithms are possibly the foundation of life itself (think: one cell joins with another cell in a very specific way, and nine months later: a collection of hundreds of millions of cells is born).

You use algorithms each time you cross a street.

Yes. A breakdown of the process might help you realize this:
Step 1: You decide to cross the street. In making this decision, you have already used several algorithms (for example: "if I leave now will I be home in time for dinner? Yes. So I will.") to act on data (for example: "the time for dinner is set at 6.30pm and it's 4.30pm already, but it takes an hour and fifty minutes to get home from here") and the result of your computations spurs you into action.
Step 2: You stop at the curb/sidewalk. This small act is the result of many, many (think: hundreds or even thousands) algorithms that you have trained your brain to remember and execute over the years. Two-year olds lack these algorithms, which is why you often see them trying to play "hugs" in the middle of a busy street. Again, your brain is acting on data it receives in real-time from your eyes, ears, skin.
Step 3: You look left.
Step 4: You look right.
Step 5: You look left again.
Step 6: The road is clear so you walk briskly across.
Step 7: A horrible person speeds by while you are still halfway across.
Step 8: You jump a little. Land on the curb. Wince and give her the finger.

Sound familiar?

In reality, it often requires many more steps (for example, I have to navigate a very busy bridge twice daily: in the mornings on my way to work, in the evenings on my way back) but your brain has the right algorithms so you survive.

Do you see how simple working with algorithms is now?

Analyzing The Bubble Sort Algorithm
The Bubble Sort algorithm is a very special algorithm. It is the simplest algorithm in the world for sorting a collection of items, but this isn't what makes it so special.
The Bubble Sort algorithm is special because it can be used to teach any and every class of programmer: from newbies who are still studying data structures to mid-level developers who want to learn to optimize their code to more experienced programmers who want to gain deeper insight into the inner workings of computer systems.
Why 'Bubble'?
The special algorithm is called 'Bubble Sort' because it uses a simple method to sort collections in a manner resembling 'bubbling'. The GIF below shows this bubbling at work.

Observe how the number 8 has 'bubbled' to the end of the collection.

Basically, the algorithm sorts collections by comparing each consecutive item in the collection with its neighbor (usually the neighbor to the right). If the item is larger than the neighbor to the right (or less than the neighbor to the left), the algorithm swaps the two items (i.e the current item and the neighbor), arranging the collection in the process.
The Bubble Sort algorithm can be used to sort a collection in either ascending or descending order. In this article we will work on learning to sort in ascending order, but I will leave assignments for sorting in descending order at the end so that you can practice and master your new knowledge.

Breaking Down The Bubble Sort Algorithm
Let's imagine a collection (either a list or an array will do). This collection will look like one of these, depending on your language:

// C/C++

int arr[] = {5,3,1,4,8,7,9}; //array

// Java

int arr[] = {5,3,1,4,8,7,9}; //array

// JavaScript

let arr = [5,3,1,4,8,7,9]; //array

// PHP

$arr = array(5,3,1,4,8,7,9); //array

# Python

arr = [5,3,1,4,8,7,9] #list: Python does not have arrays

Notice how the items of each array/list are randomly distributed.

Our implementation of the Bubble Sort algorithm will start at the beginning of the collection (index 0) and compare each item with its near-right neighbor. If the item is less than its neighbor, the algorithm will leave the item in position and move on to compare the item's near-right neighbor with its own near-right neighbor.
5 (at index 0) is larger than 3 (its near-right neighbor) so our algorithm will swap their positions: index 0 becomes 3 while index 1 becomes 5*. At this point the collection will look like:

[3,5,1,4,8,7,9] #python

[3,5,1,4,8,7,9]; //JavaScript

{3,5,1,4,8,7,9}; #C/C++/Java

The algorithm will do the same thing for index 1 and index 2 (5 and 1, respectively). At this point the collection will look like:

[3,1,5,4,8,7,9] #python

{3,1,5,4,8,7,9}; #C/C++/Java/JavaScript

The algorithm will continue to do this until it gets to index 5 (7) and index 6 (9). Since 7 is less than 9, the algorithm will not swap these items.

Easy, right?

The Code: Implementing The Bubble Sort Algorithm
We have analyzed the Bubble Sort algorithm and written some pseudocode (which is what programmers call a step-by-step analysis of an algorithm written in a format that slightly resembles a real programming language. We did this in the section above this.). We are now equipped enough to implement the algorithm in our favorite programming language.

If you are not very comfortable in any of these five languages, you can still benefit maximally from this article. By following the pseudocode you can write an implementation in your language. If you get stuck, a quick web search might be of help. In any case, please, do not hesitate to reach out to me via email via [e-mail]. I'd be delighted to assist you.

Feel free to skip to your language in this section.

C

// C

#include <stdio.h>

void bubbleSort(int arr[], int n)
{
    int i, j, temp;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n-i-1; j++)
        {
            if( arr[j] > arr[j+1])
            {
                // swap the elements
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    // print the sorted array
    printf("Sorted Array: ");
    for(i = 0; i < n; i++)
    {
        printf("%d  ", arr[i]);
    }
}

int main()
{
    int arr[100], i, n, step, temp;
    // ask user for number of elements to be sorted
    printf("Enter the number of elements to be sorted: ");
    scanf("%d", &n);
    // input elements if the array
    for(i = 0; i < n; i++)
    {
        printf("Enter element no. %d: ", i+1);
        scanf("%d", &arr[i]);
    }
    // call the function bubbleSort
    bubbleSort(arr, n);

    return 0;
}

C file available on GitHub: here

C++

// C++

#include <stdio.h>

#define MAXSIZE 10 
// change the value of MAXSIZE to the number of items in your array when you test

int main() {
    int array[MAXSIZE];
    int i, j, num, temp;

    printf("Enter the count of elements \n");
    scanf("%d", &num);
    printf("Enter the elements one by one \n");
    for (i = 0; i < num; i++) {
        printf("Enter element %d of %d\n", (i+1), num);
        scanf("%d", &array[i]);
    }

    for (i = 0; i < num; i++) {
        for (j = 0; j < (num - i - 1); j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    printf("Sorted array is...\n");
    for (i = 0; i < num; i++) {
        printf("%d\n", array[i]);
    }
}

C++ file available on GitHub: here

Java

// Java

class Sort { 
    void bubbleSort(int arr[]) { 
        int n = arr.length; 
        for (int i = 0; i < n-1; i++) 
            for (int j = 0; j < n-i-1; j++) 
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[j] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
    } 

    /* Output the array */
    void printArray(int arr[]) { 
        int n = arr.length; 
        System.out.print("["):
        for (int i = 0; i < n; ++i) System.out.print(arr[i] + ", "); 
        System.out.print("["):
        System.out.println();
    } 
}

    public static void main(String args[]) { 
        Sort sort = new Sort(); 
        int arr[] = {5,3,1,4,8,7,9};
        sort.bubbleSort(arr); 
        System.out.println("Sorted array"); 
        sort.printArray(arr); 
    } 

Java file available on GitHub: here

JavaScript

class Sort {
  swap(arr, idx1, idx2) {
    if (arr[idx1] > arr[idx2]) {
      let tmp = arr[idx1];
      arr[idx1] = arr[idx2];
      arr[idx2] = tmp;
    }
    return arr;
  }

  bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
      for (let j = 0; j < arr.length - 1; j++) {
        arr = this.swap(arr, j, j + 1);
      }
    }

    return arr;
  }
}

function main() {
    const arr = [3,5,1,4,8,7,9];
    const Sort = new Sort();
    return Sort.bubbleSort(arr);
}

console.log(main());

JavaScript code available on CodeSandbox: here

Also available on GitHub: here

PHP

// PHP

class Sort {
    protected sort(array $arr, int $idx1, int $idx2) {
        if ($arr[idx1] > $arr[idx2]) {
            $tmp = $arr[idx1];
            $arr[idx1] = $arr[idx2];
            $arr[idx2] = $tmp;
        }

        return arr;
    }

    public function bubbleSort(array $arr) {
        for ($i = 0; $i < count(arr) - 1; $i++) { //perform the swap operation on each item in the array
            for ($j = 0; $j < count(arr) - 1; $j++) { //get each item and its near-right neighbor
                $arr = $this->swap($arr, $j, $j + 1); //perform the swap 
            }
        }

        return $arr;
    }

}

function main() {
    $arr = array(3,5,1,4,8,7,9);
    $sort = new Sort();
    print_r($sort->bubbleSort($arr));   
}

main();

PHP code available on GitHub: here

Python

# Python

class Sort:
    def _swap(self, arr, idx1, idx2):
        if (arr[idx1] > arr[idx2]):
            tmp = arr[idx1]
            arr[idx1] = arr[idx2]
            arr[idx2] = tmp

        return arr

    def bubbleSort(self, arr):
        for i in range(0, len(arr) - 1):
            for idx in range(0, len(arr) - 1):
                arr = self._swap(arr, idx, idx + 1)

        return arr


def main():
    arr = [3,5,1,-3,4,8,7,9]
    sort = Sort()
    sorted_arr = sort.bubbleSort(arr)
    return sorted_arr

print("Sorted list: {}".format(main()))

Python code available on GitHub: here

I hope you learned a lot. I look forward to hearing from you.
May the Code be with us all.
Cheers!

Recommended Reading:

If you want to take your study of algorithms further (and I hope that you do!), I recommend the following publications for your perusal:

1. Fundamentals of Computer Algorithms: Horowitz and Sahani.
2. JavaScript Data Structures and Algorithms: An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals
3. Algorithms In A Nutshell: A Practical Guide
4. Nine Algorithms That Changed The Future: John MacCormick
5. Coding Interview Ninja: 50 Coding Questions With Java Solitions To Practice For Your Coding Interview
6. Cracking The Coding Interview: Gayle Laakmann McDowell
7. Graphs, Networks and Algorithms: Algorithms and Computation In Mathematics
8. Analysis For Computer Scientists: Foundations, Methods and Algorithms
9. Computational Thinking: First Algorithms, Then Code
10. The Art of Computer Programming: Donald Knuth

Coming Soon:

Articles and essays planned for the next couple of weeks:

1. Introduction To Web Scraping With Python: Part 3
2. **Introduction To Statistical Analysis Using NumPy and Python
3. Bits, Bytes and Everything In-between: How Computers Really Work
4. The T-shaped Developer
5. Five Algorithms That The World Cannot Do Without

Recently Published:

1. Introduction To Web Scraping With Python: Part 2