Searching and Sorting

What is a simple sort?

Selects the smallest number in one list and moves it to another list.

What is a Simple (Selection) Sort?

Marker is on first item and swaps said item with the smallest item in the list. Marker moves ahead once

What is an insertion sort?

There's a border between the first and second items. Move the next item and move the items to the left of the marker.

In an insertion sort, which side is unsorted?

Right

In an insertion sort, which side is sorted?

Left

What is a bubble sort?

Compares items beside each other. Swaps them if they are in the wrong order. Continues through the list until they're sorted

Is the Bubble Sort efficient?

No, too many comparisons

Algorithm (definition)

A series of finite, unambiguous steps followed to solve a problem. E.g. recipe

What are the essential features of algorithms?

Accuracy and precision

Algorithm process

Input →processing → output

What do rule-based algorithms use?

A set of predefined rules to make decisions.

What does a machine learning algorithm use?

They learn from datasets to create their own rules based on statistical randomness

Are rule-based algorithms simple or complex?

Simple

What is the problem with rule-based algorithms?

Error filled

Are machine learning based algorithms simple or complex?

Complex

What is the feature of machine learning algorithms?

Opportunity for non-deterministic behaviors

What is non-deterministic behaviors?

What's logical to you may not be the outcome. Not based on human biased

Best case time complexity for Linear Search

O(1)

Average case time complexity for Linear Search

O(n)

Worst case time complexity for Linear Search

O(n)

Best case time complexity for Binary Search

O(1)

Average case time complexity for Binary Search

O(log2n)

Worst case time complexity for Binary Search

O(log2n)

Best case time complexity for Simple (Selection) Sort

O(n²)

Average case time complexity for Simple (Selection) Sort

O(n²)

Worst case time complexity for Simple (Selection) Sort

O(n²)

Best case time complexity for Bubble Sort

O(n)

Average case time complexity for Bubble Sort

O(n²)

Worst case time complexity for Bubble Sort

O(n²)

Best case time complexity for Insertion Sort

O(n)

Best case time complexity for quick sort

O (n log2n)

Average case time complexity for quicksort

O (n log2n)

Worst case time complexity for quick sort

O (n2)

Does a log in the time complexity mean it is more or less efficient?

More efficient

What does O(1) mean?

That the time complexity is the same no matter how long the list is

How does a linear search work?

It iterates (goes through the list) until it finds the required item.

What does a linear search return when it finds the value required

The element’s index in the list

What value does a linear search return if it doesn’t find the value in the list?

-1

Disadvantage of binary search

List must be sorted for it to work

Explain a binary search

Divides a sorted list in half at each step. Compares the middle element (floor division) of the list with the target value. If the middle element is greater, it’ll search the left half of the list. If the middle element is smaller, it’ll search the right half. It’ll continue finding the middle and splitting the list until then target value is found or the base case is reached.

Why is binary search more efficient

It divides the list at each step, eliminating multiple items at once

What is a pivot?

The item of the list which we use to compare to the rest of the items in order to split the list

Unless stated otherwise, which item is the pivot?

The last item

What is the base case of quick sort?

When the length of the list becomes 1

What is recursion?

When a function calls itself in the function

Explain quicksort

Pivot is selected and separated from the list. Items are split into two list depending on if they’re bigger than or smaller than the pivot. Repeat the process with each individual list until they are split into one item per list.

Name two ways to improve quicksort

Sort in place without making new lists since it takes up storage. Select a middle pivot

How would Sort in place without making new lists improve quick sort?

Making new lists requires storage

How would selecting a middle pivot improve the efficiency of quick sort?

Ensures list is split evenly, making it take less time due to the amount of cycles being split between the two lists and not one list having to be split multiple times

Advantages of sorting a data set (2)

More user friendly. Easier to analyse

Disadvantages of sorting a data set (2)

Wastes time. Consumes memory and CPU

How to improve bubble sort? (2)

Algorithm stops early to reduce comparisons if no swap occurs. Do not do an extra check at the end of the program to reduce comparisons

Why would the highest number as a pivot not work? (2)

All items less than it will not be split making it less efficient and increasing the time taken to complete the algorithm

Two properties of recursive functions

Must call itself. Base case triggers end of the recursion

What is a base case?

Smallest problem that can be solved without further recursion