Algorithms

Algorithms

An algorithm is a process or set of rules that is used to solve a problem. E.g., cake recipe, long division method, back-end of a search engine such as Google.

The two main factors that determine the efficiency of an algorithm are time and space:

• Time - How long does the algorithm take to solve a problem?
• Space - How much memory did the algorithm need?

Pseudocode

Pseudo code is a description outlining the steps of an algorithm in plain language. It is often used to plan out how an algorithm will function and is intended for human reading, not machine reading.

Sorting Algorithms

Simple Sort / Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning.

First Pass: 64 25 12 22 11 (11 is identified as the lowest number and placed at index 0) 11 25 12 22 64

Second Pass: 11 25 12 22 64 (25 is selected, 12 is the new lowest number, they are swapped) 11 12 25 22 64 This continues until the array is fully sorted.

Sequence of a Simple Sort

1. Initialise an unsorted list
2. Initialise an empty list
3. Repeat until unsorted list is empty a. Find the smallest item b. Move the smallest item to the sorted list
4. Stop.

• Simple sort is not an efficient algorithm.
• It requires twice as much memory as the size of the original list.
• To sort a list of size N, the algorithm needs a space complexity of 2N.
• Impractical with large lists

---

Algorithms

Drawbacks of a Simple Sort

Sequence of a Selection Sort

1. Initialise unsorted list
2. Initialise a marker
3. Loop across list a. Find minimum item to right of marker b. Swap minimum item with marker c. Advance marker
4. Stop

Insert Sort

Insert sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

First Pass: 12 11 13 5 6 (The first two elements are compared and sorted) 11 12 13 5 6

Second Pass: 11 12 13 5 6 (These numbers are correct, so no change is made) 11 12 13 5 6

This continues until the whole array is sorted.

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

---

Algorithms

First Pass: 5 1 4 2 8 (Compares first two and swaps them)

• 1 5 4 2 8 (Swap)
• 1 4 5 2 8 (Swap)
• 1 4 2 5 8 (No swap)

Second Pass: 1 4 2 5 8 (No swap)

• 1 4 2 5 8 (Swap)
• 1 2 4 5 8 (No swap)
• 1 2 4 5 8 (No swap)

Algorithm makes one more pass to confirm array is sorted.

Merge Sort

Merge sort is a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

---

Algorithms

Quick Sort

Like Merge Sort, Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of Quick sort that pick pivot in different ways.

• Always pick the first element as a pivot.
• Always pick the last element as a pivot (pictured below)
• Pick a random element as a pivot.
• Pick median as the pivot.

Sequence of a Quick Sort:

1. Choose the rightmost element in the list as the pivot
2. Create three empty lists called left_list, middle_list and right_list
3. For each element in the list a. if element is < pivot add it to left_list b. if element is == pivot add it to middle_list c. if element is > pivot add it to right_list
4. The result is a list made up by applying steps 1-3 to left_list, followed by the elements in middle_list, followed by applying steps 1-3 to right_list

Search Algorithms

Linear Search

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is the easiest searching algorithm.

---

Algorithms

Binary Search

The basic steps to perform Binary Search are:

• Sort the array in ascending order.
• Set the low index to the first element of the array and the high index to the last element.
• Set the middle index to the average of the low and high indices.
• If the element at the middle index is the target element, return the middle index.
• If the target element is less than the element at the middle index, set the high index to the middle index - 1.
• If the target element is greater than the element at the middle index, set the low index to the middle index + 1.
• Repeat steps 3-6 until the element is found or it is clear that the element is not present in the array.

---

Algorithms

Disadvantages of a Binary Search

• The data set being searched must be sorted and remain sorted.
• Can be slower than linear search (average performance is O(log n) vs. average of linear search is O(n/2).
• More complicated than linear search and unnecessary for small data sets. Only works on data with a "less-than" relationship.
• Data has to be of the same type.

Algorithmic Efficiency

Why is the study of algorithmic efficient important?

It is important to understand the time and efficiency so that different algorithms can be compared, particularly as data sets grow. It allows for the best algorithm to be selected for the specific problem. The best algorithm should be the fastest and/or use least amount of memory.

Big O Notation

Big O notation describes how the complexity of an algorithm grows relative to the size of the input (in most cases, the input will be a list).

• O(n): Time complexity increases in direct proportion to the length of the list. E.g., sorting an already sorted list (insertion sort).
• O(1): Time complexity is constant – e.g. search for the first item in a list
• O(n²): Time complexity grows to the square of the input size, e.g., insertion sort on a reverse ordered list

---

Algorithms

• O(log n): Time complexity is effected very little by the length of the list e.g. binary search in most cases
• O(n log n): Time complexity grows to nlogn of the size of the input e.g. quick sort in most cases

Summary of Big O Notation & Time Complexities

Algorithm	Worst Case Time Complexity	Best Case Time Complexity
Selection Sort	O(n²)	O(n²)
Insert Sort	O(n log n)	O(n)
Bubble Sort	O(n²)	O(n)
Merge Sort	O(n log n)	O(n log n)
Quick Sort	O(n²)	O(n log n)