2.1 | Algorithms | 2.1.5

Page 1

Sort Algorithms

Sorting algorithms allow us to put data in a certain order.

Efficient sorting

An efficient sort algorithm is one which can sort a data set in a short time.

Sort algorithms

A sort algorithm is a set of instructions to arrange a data set into a particular order.

Examples of sorting algorithms

There are hundreds of sorting algorithms, but you only need to learn three:

Bubble sort.

Insertion sort.

Merge sort.

Page 2

Bubble Sort

Bubble sort is a naive sorting algorithm.

The concept

Imagine that you have a set of cards face up on the desk.

If the first two cards are in the wrong order, you swap them.

Then do the same for the second and third cards, and continue in this pattern until the end of the pack. This is known as a pass.

The highest value will 'bubble' up to the top of the pack each pass.

By repeating this enough times, the pack will get sorted.

In English

Compare the first two items of the data set:

If they are in the wrong order, swap them.

Continue for the rest of the cards in the deck.

Repeat the whole process, until a pass with no swaps happens.

Pros and cons of bubble sort

Pros:

Easy to implement.

Does not use much memory.

Cons:

Poor for efficiency.

In Pseudocode (below)

Page 3

Insertion Sort

Insertion sort is a simple sorting algorithm, which is very intuitive.

The concept

Imagine sorting a deck of cards.

Hold the deck of cards in one hand, and place a single card down on the desk.

Take a card from the top of the deck in your hand, and put it in the correct place in the other deck.

Repeat until all the cards are gone.

In English

Take the second card:

Compare to the first card, swap if needed.

Take the third card:

Compare to second card, swap if needed.

Compare to first card, swap if needed.

Take the fourth card:

Compare to all previous cards.

Repeat for all cards.

Pros and cons of insertion sort

Pros:

Easy to implement.

Little memory used.

Cons:

Not very efficient.

In pseudocode (below)

Page 4

Merge Sort

Merge sort is an example of a divide and conquer algorithm, where the problem is broken down into smaller steps.

The concept

If we have two packs of cards, which are both already in order and want to combine them, what can we do?

One solution is to only consider the top card of each pile, and create a new deck starting from the smaller of the two cards.

This will give us a combined sorted pack.

This is called merge sort.

In English

Split the lists into lists of size one.

Merge each pair of sub-lists by comparing the first value of each list and putting the smaller value into the new list first.

Continue merging until there is only one list.

Pros and cons of merge sort:

Pros:

A very efficient algorithm.

Cons:

Can be slower for small lists.

Needs additional memory.