Standard Sorting Algorithms

What is a sorting algorithm?

• Sorting algorithms are precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets

What are the 3 common sorts?

• Bubble sort

• Merge sort

• Insertion sort

What is a bubble sort?

• A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in 'pairs' and swaps them if they are not in the correct order

• One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple 'passes' to sort the dataset

• The algorithm is finished when there are no more swaps to make

How do you perform a bubble sort?

Step	Instruction
1	Compare the first two values in the dataset
2	IF they are in the wrong order... Swap them
3	Compare the next two values
4	REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)
5	IF you have made any swaps... REPEAT from the start (pass 2,3,4...)
6	ELSE you have not made any swaps... STOP! the list is in the correct order

What is a merge sort?

• A merge sort is a sorting algorithm that uses the 'divide and conquer' strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order

How do you perform a merge sort?

Step	Instruction
1	Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)
2	Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)
3	REPEAT step 2 until all sub-datasets are merged together into one dataset

What is an insertion sort?

• The insertion sort sorts one item at a time by placing it in the correct position of an unsorted list. This process repeats until all items are in the correct position

• Values in the dataset can move as many places as they need

How do you perform an insertion sort?

Step	Instruction
1	Take the first value in the dataset, this is now the sorted list
2	Look at the next value in the dataset and compare it to the first value IF it is smaller insert it into the correct position to the left
3	ELSE Keep in the same position
4	REPEAT steps 2 & 3 until all values in the dataset have been compared, the list should now be in order