Embedded Files
Terminology and Definitions
Terminology and Definitions
Algorithms
Algorithms
An algorithm is a set of steps or instructions that can be followed to complete a task or solve a problem.
Abstraction
Abstraction
Abstraction is the process of removing unnecessary detail from a problem.
Decomposition
Decomposition
Decomposition is the process of breaking a problem down into smaller sub-problems that achieve an identifiable task.
Sequence
Sequence
A set of events, actions, numbers, etc. which have a particular order and lead to a particular result.
Selection
Selection
Deciding what comes next based on the meeting of a condition
Iteration
Iteration
Repeating until an amount or condition is met.
Flow Charts
Flow Charts
Purpose
Purpose
A flowchart is a graphical way of showing an algorithm.
The symbols used to do so can be seen below.
Symbols
Symbols
Start/End
Start/End
used to show the start and stop of the algorithm
Input/Output
Input/Output
used to show where the user is going to input data or data is going to be output to the user.
Process
Process
used to show a calculation or assignment
Decision
Decision
Used to show a decision, if the answer to the question in the shape is yes, go down the yes arrow, otherwise, no arrow.
Arrow
Arrow
Used to show the direction of flow (the order of the flowchart)
Sequence
Sequence
Selection
Selection
Iteration
Iteration
Searching Algorithms
Searching Algorithms
Searching Algorithms are used to see if information or data exists.
There are two algorithms that you need to know:
Linear Search
Binary Search
Linear Search
Linear Search
A linear search is where each item is checked in order until every item is checked or the item is found.
The algorithm runs as follows:
Start at the beginning (of the array/list);
Compare each element/item until the value being searched for is found; or the end of the array/list is reached
Because the linear search algorithm simply moves up the list and checks each item, the data in the list does not need to be in order.
However, as the list gets longer the algorithm takes longer to run, making it inefficient for large lists.
Binary Search
Binary Search
Binary search is a faster method for searching for an item that is in an ordered list.
A binary search algorithm takes the data and keeps dividing it in half until it finds the item it is looking for.
The algorithm runs as follows:
Start by setting the counter to the middle position in the list.
If the value held there is a match, the search ends.
If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.
Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.
Linear Vs Binary
Linear Vs Binary
Linear Search
Linear Search
+ Much simpler than a binary search
+ Can work on unordered and ordered lists
– It is an inefficient way of searching - only works on small lists
Binary Search
Binary Search
+ Much more efficient and quicker than linear search for large lists of data
+ Gets more efficient the larger the list gets as it discard half the information every step
– The data must already be in order
Sorting Algorithms
Sorting Algorithms
Sorting Algorithms are used to put data in order.
There are two algorithms that you need to know:
Bubble Sort
Merge Sort
Bubble Sort
Bubble Sort
A bubble sort checks each item against it's neighbour, if they need to swap, it swaps them until every item is in order. it makes sure the biggest number gets to the end (if sorting ascending) and then goes back to the beginning each time it reaches the end and goes back to the beginning, this is known as a pass.
The first pass of a bubble sort is to get the most extreme element to the end.
The total number of passes required is equal to n - 1 where n is the number of items in the list.
The algorithm runs as follows:
Start at the beginning (of the array/list);
Compare each element/item to the one next to it;
If it is bigger, swap, if it isn't leave them and move on to next item;
Repeat steps 2 and 3 until list is sorted.
Merge Sort
Merge Sort
Merge sort is a faster method for sorting data in a list.
A merge sort algorithm takes the data and keeps dividing it in half until it has individual items, it then compares the items and puts them back together sorted.
The algorithm runs as follows:
Divide the list in half;
Repeat step 1 until all values are in a list on their own;
Compare item 1 and item 2, swap them if needed;
Repeat step 3 for all other items;
join the sorted lists back together, comparing them to each other and sorting as you go.
Bubble Vs Merge
Bubble Vs Merge
Bubble Sort
Bubble Sort
+ Much simpler than a merge sort
+ Can work on any set of data
– It is an inefficient way of sorting - very slow on large lists
Merge Sort
Merge Sort
+ Much quicker than bubble sort for large lists of data
– uses up a lot of storage (in RAM) as each time you divide the list, you create a new list
Efficiency of Algorithms
Efficiency of Algorithms
We have looked at two algorithms for searching a list, and two algorithms for sorting a list. In each case, either of the algorithms can be used to solve the problem, but one algorithm is much more efficient.
When performing a binary search, for example, doubling the size of the list from 1000 to 2000 items only involves halving the list one more time. Using a linear search, it could mean searching an extra thousand items!
Many problems, both simple and complex, have more than one method of solution. Consider the problem of finding the sum of the integers from 1 to n. Here are two different algorithms for solving this problem.
Algorithm 1:
total = 0
for i in range(1, n):
total = total + n
Algorithm 2:
total = n * (n + 1)/ 2
The second algorithm is clearly much more efficient, as only one instruction is executed.
Page updated
Google Sites
Report abuse