✍️Writing Algorithms
Learn how to write and interpret algorithms using pseudocode.
An algorithm is a set of instructions to solve a problem. Real world examples include:
Recipe for baking a cake
Instructions for sorting a deck of cards
Steps to find the shortest route on a map
In terms of computers, algorithms are step-by-step procedures for solving a problem digitally, some examples include:
Binary search algorithm
Bubble sort algorithm
Dijkstra's algorithm for shortest path
RSA encryption algorithm
Quick sort algorithm
Here are a few problems that have been solved by algorithms:
Routing Problems: Routing packets of data around the internet by the shortest route. Finding the shortest route for a salesman to cover his territory.
Timetabling Problems: Commercial aircraft crews so that they do not exceed their permitted flight hours.
Searching Problems: Finding information on the internet or from a database.
Encrypting Problems: Encrypting data so that it cannot be read by others.
Sorting Problems: Sorting large amount of data in a specific format.
Compiling Problems: Translating high level language code into machine code.
Good Algorithms
A good algorithm must have clear and precisely stated steps that produce the correct output; It should allow for valid inputs; it must terminate at some point; it should execute efficiently, in as few steps as possible; It should be designed in such way so the algorithm is easy for others to understand and edit.
Designing an Algorithm
You can use hierarchy charts, flowcharts, or pseudocode in order to design an algorithm.
Hierarchy Charts
Hierarchy charts are very useful for identifying major tasks and breaking them down into small subtasks.
Flowcharts
Flowcharts are useful for getting down initial ideas for individual subroutines.
Pseudocode
Pseudocode can help us understand what the actual code of the subroutines may look like, so it can easily be later translated into source code by a programmer.
Sorting Algorithms
Sorting is a common operation whilst processing data. There are many sorting algorithms, some that are very simple and slow (e.g. insertion sort), while others that are more complex and fast (e.g. merge sort).
Insertion Sort
Insertion sort is an efficient algorithm for sorting a small number of elements. It works in the same way you may sort a deck of playing cards: Start with all the cards facing down, pickup each card in turn and insert it into the correct place in the deck.
How it works
Suppose we have six numbers to sort.
The pink card is the card you pick up each time.
Insert it in the right place, and pick up another.
Python Example
arr = [12, 11, 13, 5, 6]
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
print("Sorted array via insertion sort:", arr)Bubble Sort
This sorting algorithm is useful when there are small number of items to be sorted. To sort an array of n items, n-1 passes are made through the array, with each item being compared to the adjacent item and swapped if necessary.
arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print("Sorted array via bubble sort:", arr)Searching Algorithms
There are two most common searching algorithms: linear search and binary search.
Linear search starts from the beginning of the list and examines every item. On the other side, binary search uses the “divide and conquer” tactic to halve the search area each time an item is examined, this makes it much faster than linear search. A disadvantage of binary search is that it can only be used on pre-sorted data.
Python Example
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage:
my_list = [2, 4, 7, 10, 14, 19, 22, 25]
target = 14
result = binary_search(my_list, target)Last updated