Algorithms and programming constructs

Sorting

What you need to know:-

Describe the characteristics of merge sort and bubble sort algorithms. (You will need to know how they work in order to find errors in the algorithm or to stop what the algorithm is doing)

Bubble Sort

Compares the current location with the next location
Swaps if the data is out of order
No swap if the data is in order (items are maintained in situ)

This continues…

Additional passes (iterations) through the data if there was a swap
If no swaps are performed then the data is sorted in order (has to do one pass to check this!)

Bubble Sort AlgorithmBubble sort is an algorithm used to sort (or order) elements present in a list. It sorts elements present in the list by iterating over each element in the list and moving it up by one position if it is greater than the next element.

This website shows you how a bubble sort it stepped through and is a great visual way of seeing a bubble sort in action.

Click on the red writing (Bubble Sort Algorithm) to access the link

Star Wars Bubble Sort - This shows a bubble sort putting the Star Wars films into order. (Click to see the bubble sort in action)

Copy of Copy of Star_Wars_Bubble_Sort_JLA

Merge Sort

Divide the list into smallest units (divide and conquer!)
Compare each item with the adjacent list
Merge the two adjacent lists
When all lists are merged the data is sorted order

Merge Sort AlgorithmMerge Sort is an efficient algorithm used to order/sort a list of elements in ascending or descending order. It is a type of divide and conquer algorithm: Merge sort algorithm divides the list to be sorted into two halves, recursively sorts each list by using the same algorithm on both the lists and then merges both the sorted lists back into a single sorted list.

This website shows you how a Merge sort it stepped through and is a great visual way of seeing a Merge sort in action.

Click on the red writing (Merge Sort Algorithm) to access the link

Merge Sort Algorithm:

But which one is faster?

A comparison of bubble sort and merge sort:

BBC Four - The Secret Rules of Modern Living: Algorithms, Battle of the algorithmsBoth algorithms put things in order – but they do it by different means.

Searching

What you need to know:-

Describe the characteristics of linear search and binary search algorithms. (You will need to know how they work in order to find errors in the algorithm or to stop what the algorithm is doing)