The NOTION of an algorithm is basic to all computer programming. Donald E. Knuth
Even you do not care about algorithms, if you program in any programming language you use, produce and read algorithms.
A Programming Language is the language you can express algorithms to the computer can understand it. So, here I want to make a difference between Programming Languages and Presentation Languages. HTML for me is not a programming language… No worries if you believe it is. 🤓
Defining Algorithms
The Oxford Dictionary define algorithm as:
A set of rules that must be followed when solving a particular problem.
Any computer program is developed to solve a problem. Or to create a problem… no worries 😉
So a program SHOULD follow a Recipe, and that is the algorithm. This is ubiquitous in any computing.
Characteristics
An algorithm is a recipe, but a recipe is not an algorithm. Why? You can understand a recipe, but a computer cannot! You are much smarter than a computer.
To be an algorithm, a set of rules must have the following features
- Finiteness
- Definiteness
- Input
- Output
- Effectiveness
1. Finiteness
An algorithm SHOULD always terminate after a finite number of steps.
There are some algorithms that search infinitely for a optimal value. Even this kind of algorithms should have a end, probably an finite number of iterations or an “stable” value.
2. Definiteness
Each step of an algorithm SHOULD be precisely defined.
You can make assumptions about something you read, but a computer cannot make any assumption. Each step should be precise.
Imagine an algorithm that says:
Divide m by n and assign x with the value
This step is defined? No! You can make questions to this step: Is x an Integer value? If we have m=4 and n=3, the result in x can be x=1 or x=1.333. Depending from the algorithm it can be any value.
The correct step should be:
Assign the x (integer) with the value of m divided by n
In an algorithm there is no space for questions in steps.
3. Input
An algorithm has zero or more inputs.
4. Output
An algorithm has one or more outputs.
5. Effectiveness
All steps need to be effective, that means it should be simple enough to be done without any other knowledge
Notation
For writing an algorithm we need:
- Numbered steps: We should be able to refer to steps
- Pseudocode: We should be able to translate the algorithm in any programming language
- Given inputs
- Given outputs
- Assignments: This represents when a variable assume a new value. Normally we use the notation
x ← ywhere means thatxwill be attributed the value ofy.
Sorting a array
How can I sort an array of integers?
GIVEN:
v → The given array
n → The length of the given array
x[i] → The value stored in the position i from the array x
START:
S1: FOR EACH i IN [0, n - 2]:
S2: min_index ← i
S3: FOR EACH j IN [i + 1, n - 1]:
S4: IF v[j] < v[min_index]?
S5: min_index ← j
S6: IF v[i] != v[min_index]?
S7: aux ← v[min_index]
S8: v[min_index] ← v[i]
S9: v[i] ← aux
About this algorithm we can ask:
- Is it finite? Yes, it will iterate over the array.
- Is it definite? Yes, every step can be done without any assumption.
- What is the input? The array and it’s length.
- What is the output? The same array, every change is made inplace
- Is it effective? Yes, it will sort any array.
Running with the pen
GIVEN:
v = [5, 100, -6, 98, -111, 0]
n = 6
S1: i ← 0 v = [5, 100, -6, 98, -111, 0] min_index = 0 aux = 0
S2: min_index ← 0 v = [5, 100, -6, 98, -111, 0] min_index = 0 aux = 0
S3: j ← 1 v = [5, 100, -6, 98, -111, 0] min_index = 0 aux = 0
S4: v[1] < v[0] ? (100 < 5) NO v = [5, 100, -6, 98, -111, 0] min_index = 0 aux = 0
S3: j ← 2 v = [5, 100, -6, 98, -111, 0] min_index = 0 aux = 0
S4: v[2] < v[0] ? (-6 < 5) YES v = [5, 100, -6, 98, -111, 0] min_index = 0 aux = 0
S5: min_index ← 2 v = [5, 100, -6, 98, -111, 0] min_index = 2 aux = 0
S3: j ← 3 v = [5, 100, -6, 98, -111, 0] min_index = 2 aux = 0
S4: v[3] < v[2] ? (98 < -6) NO v = [5, 100, -6, 98, -111, 0] min_index = 2 aux = 0
S3: j ← 4 v = [5, 100, -6, 98, -111, 0] min_index = 2 aux = 0
S4: v[4] < v[2] ? (-111 < -6) YES v = [5, 100, -6, 98, -111, 0] min_index = 2 aux = 0
S5: min_index ← 4 v = [5, 100, -6, 98, -111, 0] min_index = 4 aux = 0
S3: j ← 5 v = [5, 100, -6, 98, -111, 0] min_index = 4 aux = 0
S4: v[5] < v[4] ? (0 < -111) NO v = [5, 100, -6, 98, -111, 0] min_index = 4 aux = 0
S6: v[0] != v[4] ? (5 != -111) YES v = [5, 100, -6, 98, -111, 0] min_index = 4 aux = -111
S7: aux ← -111 v = [5, 100, -6, 98, -111, 0] min_index = 4 aux = -111
S8: v[4] ← 5 v = [5, 100, -6, 98, 5, 0] min_index = 4 aux = -111
S9: v[0] = -111 v = [-111, 100, -6, 98, 5, 0] min_index = 4 aux = -111
S1: i ← 1 v = [-111, 100, -6, 98, 5, 0] min_index = 4 aux = -111
S2: min_index ← 1 v = [-111, 100, -6, 98, 5, 0] min_index = 1 aux = -111
S3: j ← 2 v = [-111, 100, -6, 98, 5, 0] min_index = 1 aux = -111
S4: v[2] < v[1] ? (-6 < 100) YES v = [-111, 100, -6, 98, 5, 0] min_index = 1 aux = -111
S5: min_index ← 2 v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S3: j ← 3 v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S4: v[3] < v[2] ? (98 < -6) NO v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S3: j ← 4 v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S4: v[4] < v[2] ? (5 < -6) NO v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S3: j ← 5 v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S4: v[5] < v[2] ? (0 < -6) NO v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S6: v[1] != v[2] ? (100 != -6) YES v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -111
S7: aux ← -6 v = [-111, 100, -6, 98, 5, 0] min_index = 2 aux = -6
S8: v[2] ← 100 v = [-111, 100, 100, 98, 5, 0] min_index = 2 aux = -6
S9: v[1] = -6 v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S1: i ← 2 v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S2: min_index ← 2 v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S3: j ← 3 v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S4: v[3] < v[2] ? (98 < 100) NO v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S3: j ← 4 v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S4: v[4] < v[2] ? (5 < 100) YES v = [-111, -6, 100, 98, 5, 0] min_index = 2 aux = -6
S5: min_index ← 4 v = [-111, -6, 100, 98, 5, 0] min_index = 4 aux = -6
S3: j ← 5 v = [-111, -6, 100, 98, 5, 0] min_index = 4 aux = -6
S4: v[5] < v[4] ? (0 < 5) YES v = [-111, -6, 100, 98, 5, 0] min_index = 4 aux = -6
S5: min_index ← 5 v = [-111, -6, 100, 98, 5, 0] min_index = 5 aux = -6
S6: v[2] != v[5] ? (100 != 0) YES v = [-111, -6, 100, 98, 5, 0] min_index = 5 aux = -6
S7: aux ← 0 v = [-111, -6, 100, 98, 5, 0] min_index = 5 aux = 0
S8: v[5] ← 100 v = [-111, -6, 100, 98, 5, 100] min_index = 5 aux = 0
S9: v[2] = 0 v = [-111, -6, 0, 98, 5, 100] min_index = 5 aux = 0
S1: i ← 3 v = [-111, -6, 0, 98, 5, 100] min_index = 2 aux = 0
S2: min_index ← 3 v = [-111, -6, 0, 98, 5, 100] min_index = 3 aux = 0
S3: j ← 4 v = [-111, -6, 0, 98, 5, 100] min_index = 3 aux = 0
S4: v[4] < v[3] ? (5 < 98) YES v = [-111, -6, 0, 98, 5, 100] min_index = 3 aux = 0
S5: min_index ← 4 v = [-111, -6, 0, 98, 5, 100] min_index = 4 aux = 0
S3: j ← 5 v = [-111, -6, 0, 98, 5, 100] min_index = 4 aux = 0
S4: v[5] < v[4] ? (100 < 5) NO v = [-111, -6, 0, 98, 5, 100] min_index = 4 aux = 0
S6: v[3] != v[4] ? (98 != 5) YES v = [-111, -6, 0, 98, 5, 100] min_index = 4 aux = 0
S7: aux ← 5 v = [-111, -6, 0, 98, 5, 100] min_index = 5 aux = 5
S8: v[4] ← 98 v = [-111, -6, 0, 98, 98, 100] min_index = 5 aux = 5
S9: v[3] = 5 v = [-111, -6, 0, 5, 98, 100] min_index = 5 aux = 5
S1: i ← 4 v = [-111, -6, 0, 5, 98, 100] min_index = 5 aux = 5
S2: min_index ← 4 v = [-111, -6, 0, 5, 98, 100] min_index = 5 aux = 5
S3: j ← 5 v = [-111, -6, 0, 5, 98, 100] min_index = 5 aux = 5
S4: v[5] < v[4] ? (100 < 98) NO v = [-111, -6, 0, 5, 98, 100] min_index = 5 aux = 5
As we can see, given the input [5, 100, -6, 98, -111, 0], it returns the output [-111, -6, 0, 5, 98, 100]. So in the output there is no value v[i] and v[j] where i < j and v[i] > v[j], that means the array is sorted.
