Flashcard 20231216

Date:

Sorting

Explain how the bubble sort algorithm works

The Bubble sort algorithm is used to sort a list of values, normally in ascending order.

The bubble sort algorithm works by performing pairwise comparisons of adjacent values in a list and swapping them if the second item is smaller than the first value.

This process is done for each pair of values in the array.

Bubble sort is complete and the items are sorted by after an iteration of pairwise comparisons there are no swaps that occur.

Bubble sort has a complexity of O (n^2)

Explain how the selection sort algorithm works

Explain how the insertion sort algorithm works

The insertion sort algorithm is an algorithm used to sort.

This algorithm maintains a subset of “sorted” values increasing by one value on each iteration until the whole array is sorted.

The first item in insertion sort algorithm is assumed to be sorted.

The second item in the list is then compared with the first item, if the second item is smaller than the first then they swap.

The first two items are then considered to be sorted.

The third item is then compared with the second number, if the third is smaller than the second then they are swapped.

If not swapped then considered to be in the right position

If swapped, then the new item which is now in the second position is now compared with the first item.

Insertion sort has a complexity of O(n^2)

Explain how the merge sort algorithm works

Explain how the quick sort algorithm works

Explain how the heap sort algorithm works

Searching

Explain how the linear search algorithm works

Explain how the binary search algorithm works

Explain how the jump search algorithm works

Explain how the Interpolation search algorithm works

Big O notation

What is Big O notation

O notation is a way of describing how computationally expensive (or time consuming) algorithms are at completing their objectives as the input data grows

What is the time complexity of the bubble sort algorithm

What is the time complexity of the selection sort algorithm

What are the various types of complexity described by O notation

O(n^2) - quadratic time. As dat

O(1) - constant time. As data increases the time stays the same

O(n) - linear time complexity. As data increases the time increases in a linear fashion.

O(log(n)) - log time complexity - as data increases the time increases to a point then levels out.

O(n!) - factorial time

O(n log n) - quasilinear time