Please enable JavaScript.
Coggle requires JavaScript to display documents.
J276/02 - Section 4 - Algorithms (Sorting Algorithms (Bubble Sort (1. Look…
J276/02 - Section 4 - Algorithms
Computational Thinking
Three key techniques
Decomposition
- breaking down a
complex problem
into
smaller problems
and solving each one
individually
.
Abstraction
- picking out the
important bits
of information from the problem,
ignoring the specific details
that don't matter.
Algorithmic Thinking
- a
logical way
of getting from the
problem
to the
solution
. If the
steps
you take to solve a problem follow an
algorithm
then they can be reused and adapted to solve
similar problems
in the future.
The three key techniques can be used in Computer Science
1) Imagine your task is to sort a list of product names into alphabetical order.
2) One
decomposition
process might be deciding
what alphabetical order means
-
letters
are straightforward but what if some entries contain
numbers
and
punctuation
?
3) Another
decomposition
process might look at
comparing the entries
- this could be decomposed
further
into how you could compare two entries, three entries, etc.
4)
Algorithmic thinking
will put the tasks into a
step by step
process.
E.g. you might compare the first two entries and order them, then compare the third entry to each of the first two and put it in the correct place, then compare the fourth entry to each of the first three etc.
Writing Algorithms
Pseudocode
Algorithms can be written using pseudocode
Pseudocode
should follow a
similar
structure and read like an actual programming language. It
clearly
shows an algorithm's steps without
worrying
about the
finer details
such as
syntax
.
Quick
to write.
Easily converted
into any programming language.
As long as the person reading the code can
follow
it and
understand
where you're coming from, it
doesn't really
matter what way you write it.
Example: Write an algorithm using pseudocode to calculate the salary of a worker after a 10% pay increase.
Simple solution
Take worker's current salary
Multiply the salary by 1.1
Display the answer
It is
perfectly adequate
in that the problem has been
split down into steps
and it is
obvious
to the reader what needs to be done, however it
doesn't follow
or read much like an actual programming language.
More useful solution
VAR salary as INT
salary = INPUT("Enter your salary.")
newsalary = salary x 1.1
print newsalary
This solution is
better
because the
words
and
structure
resemble a
real
programming language and can be more
easily adapted
into real code. Note how
syntax hasn't been considered
because it is
not necessary
in pseudocode.
Make sure it's not
too
vague
So, even though pseudocode isn't a
formal programming language
you still need to make sure that it is
readable
, easy to
interpret
and
not too vague.
To make sure your pseudocode is not too vague, make sure you
read the question or scenario
you are basing the pseudocode algorithm on.
Upon doing this, try making a
checklist
for yourself containing
everything
you need to include so you don't
lose marks
for
missing
key things out.
Flow diagrams / Flowcharts
Different boxes for different commands
https://drive.google.com/file/d/1AYevO5_bvJ-bcQEFdAX-c_ItWjNirW9G/view?usp=sharing
Link to picture of the flow diagram boxes, quicker than writing out as you can't draw the boxes.
There are different types of flow diagrams
Sequence
- there is only one way from the start to the end.
Selection
- there are multiple ways to get from start to stop, usually involves several decisions.
Iteration
- it contains a loop that allows you to repeat a task until a certain condition is found.
Search Algorithms
Binary Search
1. Find the middle term in the ordered list.
2. If this is the item you’re looking for, then stop the search – you’ve found it.
3. If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list.
4. You’ll be left with a list that is half the size of the original list. Repeat steps 1-3 on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.
Linear Search
1. Look at the first item in the unordered list.
2. If this is the item you’re looking for, then stop the search – you’ve found it.
3. If not, then look at the next item in the list.
4. Repeat steps 2-3 until you find the item that you’re looking for or you’ve checked every item.
A linear search
checks each item of the list in turn
to see if it’s the correct one, it
stops
when it either
finds the item
it’s looking for and has checked every item.
A
linear
search is
much simpler
than a
binary
search but
not as efficient.
A linear search
can be used on any type of list,
it doesn’t have to be ordered.
In general, a
binary search takes fewer steps
to find the item you’re looking for, which makes it
more suitable for large lists
of items.
Sorting Algorithms
Bubble Sort
1. Look at the first two items in the list.
2. If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.
3. Move on to the next pair of items (the 2nd and 3rd entries) and repeat step 2.
4. Repeat step 3 until you get to the end of the list – this is called one pass. The last item will now be in the correct place, so don’t include it in the next pass.
5. Repeat steps 1-4 until there are no swaps in a pass.
The bubble sort algorithm is used to
sort an unordered list
of items.
The algorithm is
very simple to follow
but
can often take a while
to actually sort a list.
The bubble sort is considered to be
one of the simplest sorting algorithms
as it ever
only focuses on two items.
Link to table of pros and cons:
https://drive.google.com/file/d/1fdXol_Y6EUOJMXSsCtLjUFLrkAqm72o3/view?usp=sharing
Merge Sort
Small lists are easier
to sort than large lists.
It’s
easier to merge
two
ordered
lists than two
unordered
lists.
1. Split list in half (smaller lists are called sub-lists) – the second half of the sub-list should start at the middle item.
2. Keep repeating step 1 on each sub-list until all the lists only contain one item.
3. Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order.
4. Repeat step 3 until you’ve merged all the sub-lists together.
Link to table of pros and cons:
https://drive.google.com/file/d/1XlGyx0C9rKEiPRiyIPiRIy_4KmBLgVsy/view?usp=sharing
Insertion Sort
1. Look at the second item in a list.
2. Compare it to all items before it (in this case just the first item) and insert the number into the right place.
3. Repeat step for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place.
The
simplest sorting algorithm
to understand – it just takes each item in turn and puts it in the right place using the first item in the list as a starting point.
The
main disadvantage
is it
doesn’t cope
well with
very large
lists.
Best
case scenario is when the list is already ordered – requires
n-1 comparisons.
Worst
case scenario is it requires
n(n-1)/2 comparisons.
Link to advantages:
https://drive.google.com/file/d/1BLh-SfZqBSzcs5iZFNgnx5r_POzcFkyz/view?usp=sharing