A clearly defined procedure showing "what to do and in what order to achieve a goal," like a cooking recipe, is called an algorithm. Programming is the process of writing an algorithm in a form that a computer can execute. In this lesson, we will learn how algorithms are represented and the three basic control structures.
What Is an Algorithm?
An algorithm is a "clear procedure for solving a problem." Conditions of a good algorithm include ① no ambiguity in its steps (definiteness), ② always ending after a finite number of steps (finiteness), and ③ producing the correct result. Even for the same problem, processing speed can vary greatly depending on the algorithm, so designing "how to solve it" is very important.
Flowchart Symbols
A representative way to show an algorithm in a diagram is a flowchart. The main symbols are as follows.
・Terminal (rounded rectangle)…represents "start" and "end"
・Process (rectangle)…represents processing such as calculations and assignments
・Decision (diamond)…branches the flow according to a condition
・Input/Output (parallelogram)…represents data input and result output
・Flow line (arrow)…shows the order of processing
Three Basic Control Structures
Even the most complex algorithm can be represented by combining the following three structures.
① Sequence structure: execute processes in order from top to bottom.
② Selection structure (branching structure): switch the process to execute depending on whether a condition is true ("if..., otherwise...").
③ Iteration structure (repetition structure): repeat the same process while a condition is satisfied.
Start (terminal) → Input the score (parallelogram) → Score ≧ 60? (diamond) → If Yes, display "Pass"; if No, display "Fail" (parallelogram) → End (terminal)
The characteristic of a branching structure is that two arrows, Yes and No, come out of the diamond decision symbol.
Search Algorithms — Linear Search and Binary Search
There are two representative ways to "search" for a desired value among large amounts of data. Linear search examines items one by one in order from the beginning. It is simple, but takes time when there is much data (in the worst case, a number of comparisons equal to the number of data items is needed). Binary search assumes that the data is arranged in ascending order and compares the target with the middle value, narrowing the search range by half each time. Even among 100 data items, the target can be found with about seven comparisons at most (27 = 128 ≧ 100), and the method becomes more powerful as the amount of data increases.
- Algorithm = a clear, finite procedure for solving a problem.
- Flowchart symbols: terminal (start/end), rectangle (process), diamond (decision), parallelogram (input/output).
- All programs can be written using sequence, branching, and repetition (structured programming).
- Binary search requires sorted data. It is extremely fast because it narrows the range by half each time.
Practice Questions
- What shape represents "branching according to a condition" in a flowchart?
- What prerequisite must the data satisfy to use binary search?
- When searching through 1,000 sorted data items using binary search, about how many comparisons are needed at most?
Answers and Explanations
- Answer: Diamond
Explanation: A decision (branch) is represented by a diamond, with arrows separating in two directions, Yes and No. Remember that a process is a rectangle and input/output is a parallelogram. - Answer: The data must be sorted in ascending order (or descending order).
Explanation: The search decides whether the target is in the left or right half by comparing it with the middle value. This narrowing is impossible if the data is not sorted. - Answer: About 10 comparisons at most
Explanation: The range is halved with each comparison. Since 210 = 1,024 ≧ 1,000, ten comparisons are enough to narrow it down. This is much faster than linear search, which may require 1,000 comparisons in the worst case.