What is an “Algorithm”, anyway?
Algorithm —
I would say people who have learned about computer science have heard it at least once. As an aside, for me, it reminds me of the kid's song I used to listen to a lot in my childhood.
When we hear the word “Algorithm,” we tend to think of complicated scientific terms, but it is something we use in our daily lives without even thinking about it. For example, in your new semester, you might count how many of your classmates you have while waiting for the class to start in your classroom. In my case, I might count them one by one, starting with the first classmate on the right corner, and then count the total number. This is also an algorithm.
In the first place, programming is to produce a result (=output) for a problem (=input), and it is our job as programmers to think about the “black box” in between.
To quote the famous Professor David J. Malan, who teaches CS50 at Harvard University,
In computer science, an algorithm is a set of instructions for solving some problems step-by-step. — “What’s an algorithm?-David J. Malan” at TED Ed
What to measure in terms of time, human and financial cost and memory vary from case to case, but it is very important for a program to consider the most efficient approach for its problem.
One measure to evaluate whether the program is written with an efficient algorithm is “Big O notation”. The Big O notation has two meanings, one is called the time calculator, which calculates the time from when the program is executed to when the process is completed. The other is called spatial computation, which calculates the amount of memory consumed during a code’s run. Both can be expressed in BigO.
There are other notations such as “Big Ω” which is the lower bound of number of steps for our algorithm, “Big Θ” which we use to describe running times of algorithms if the upper bound and lower bound is the same, but today I just try to describe “Big O” which is the upper bound of number of steps, or the worst case.
Sorting
In this section, we will use javascript in the case of sort and consider how the algorithm works in the program. Suppose we have a list of numbers stored in random order. There are several algorithms for output these as a list sorted in any order, and each has its own advantages and disadvantages. If you only consider the execution time, you might choose an algorithm that reduces that time as much as possible, but it might take much more time to write that code. We also need to consider what other algorithms are more efficient, taking into account memory consumption and cost.
1. Selection sort
Check the whole array one by one to find the minimum value and replace each one.
2. Bubble sort
It is bubble sort that we swap pairs of numbers repeatedly.
3. Merge sort
A method of dividing an array in half to the smallest possible number, then comparing the two numbers and sorting them in order, returning them one by one to the larger array if the number is smaller. This method requires the least amount of execution time, but at the same time, it requires complex code to be written.
In summary, an algorithm is a set of instructions for solving a problem. It is the programmer’s job to compare, select, and execute the most efficient algorithm for the problem.
