Algorithms

An algorithm is a series of steps that you follow to do something. An instruction manual or a recipe are good examples of algorithms. We translate algorithms into code when we are programming.

There are a series of very famous algorithms in computer science. Most of the Turing Award winners won for algorithms that they wrote. Tony Hoare won for his QuickSort algorithm, Dijkstra for his networking algorithms, Hamming for his Hamming Code algorithms and many more.

These are the key aspects of a great algorithm:

the algorithm manages a large amount of data very quickly. We don’t care about small amounts of data.
the algorithm uses as little memory as possible
the algorithm handles trade-offs well. For example: space comes at the cost of memory usage. A good algorithm chooses the optimal combination of space and memory usage.
the algorithm is very creative solution to an old problem.

Big-Oh Notation

Big-Oh is the way that we say how fast a program runs. We don’t like to use seconds or milli-seconds because different computers run different speeds. Instead we measure in terms of the number of elements in the array or n.

A sequence of times from fastest to slowest:

constant time (1)
log n
n
n log n
n²
n³

Here are some basic lengths of things in terms of big-oh:

Piece of Code	Time
Assignment Statement	O(1)
Single For Loop Through an Array	O(n)
Nested For Loop Through an Array	O(n²)
If	O(1)

Why study sorting?

Sorting is a very common function. Every computer scientist knows a bunch of different ways of sorting.
Sorting allows us to practice using arrays and for loops.
The different ways of sorting are called algorithms. All advanced computer science is based on algorithms.

Types of Sorting

Bubble Sort (stops early when sorted)

The slowest sorting technique in the general case. O(n²)
It’s best case is close to O(n). Occurs when the array is almost sorted.
Slowly swaps the highest number into place.

Shaker Sort

The second slowest sorting technique in the general case. O(n²)
It’s best case is close to O(n). Occurs when the array is almost sorted. It is as fast as Bubble Sort in this case.
Slowly swaps the highest number into place. Then it swaps the lowest number into place.

Selection Sort

The third slowest sorting technique in the general case. O(n²)

It has no best case. It always takes the same amount of time.
Takes the highest number and directly trades it into place.

Insertion Sort

The second fastest sorting technique in the general case. O(n²)
It has no best case. It always takes the same amount of time.
Has a section of the array that is sorted (at the front of the array). The next number is inserted into the correct position in the sorted section.

Bin Sort

The fastest sorting technique we will learn. O(n)
It achieves it’s speed at a cost: it cannot be used unless you have integers and they fall within a small range and you know what the range is before you code the program.
Creates a bin for each number and counts the number of each number. It then directly outputs the new array.

Examples:

Bubble

4321
3421
3241
3214
2314
2134
1234

Shaker

4321

3421

3241

3214

3124

1324

1234

Selection

4321

1324

1234

Insertion

4321

3421

2341

1234

Bin

1234422113

1’s = 3
2’s = 3
3’s = 2
4’s = 2

1112223344