Comparison Algorithms

Question 1

What is the best Big-Oh complexity of insertion sort?

Answer 1

O(n)

Question 2

What is the worst Big-Oh complexity of insertion sort?

Answer 2

O(n^2)

Question 3

Is insertion in-place?

Answer 3

Insertion sort is in-place.

Question 4

Best time to use insertion sort?

Answer 4

When there is a small number of elements.

Question 5

Is insertion sort stable?

Answer 5

Yes

Question 6

What does it mean for a comparison algorithm to be stable?

Answer 6

The order of equal elements in the original sequence is preserved in the sorted sequence.

Question 7

How does insertion sort work?

Answer 7

• The array is split into a sorted and unsorted section.
• We iterate through the unsorted part and handle each element
• We check whether the element is smaller than the first rightmost element of the sorted section.
• If smaller then we swap them, this repeats until the end of the sorted section or there is no swap (this is when correct position for element is found)

Question 8

Is merge sort , divide and conquer based?

Answer 8

Yes

Question 9

What is the merge sort Big-Oh complexity?

Answer 9

O(nlogn)

Question 10

How does merge sort work?`

Answer 10

• The algorithm keeps splitting the array using the midpoint, until 1 element ‘arrays’
• The units are compared and sorted upon comparison (first iteration we compare 1 element vs 1, second 2 element vs 2)
• Repeat until the last comparison is on the 2 halves of the array

Question 11

What is the complexity of the procedure of MERGE (no merge sort)

Answer 11

O(n), as we iterate through 2 sections of array, which is at worst length of array

Question 12

What is the memory requirement of MERGE?

Answer 12

O(n), as we copy split sections into left and right arrays.

Question 13

Is in-place implementation of MERGE (and hence merge-sort) possible?

Answer 13

Yes, but stability is lost.

Question 14

Is merge-sort in place?

Answer 14

No

Question 15

Some possible improvements for merge sort?

Answer 15

• iterative implementation

- use insertion-sort on small sections of array

Question 16

What is the best Big-Oh complexity of quicksort?

Answer 16

O(nlogn)

Question 17

What is the worst Big-Oh complexity of quicksort?

Answer 17

O(n^2)

Question 18

How does quicksort operate?

Answer 18

• we split the array into smaller and smaller units, until atomic units, but one part contains smaller elements, while the other bigger. We split based on the pivot, which can be picked in a variety of ways.
• we merge 2 halves, one contains smaller items , other bigger, natrually sorted
• we build up a sorted sequence

Question 19

Is quicksort in place?

Answer 19

Yes

Question 20

Is quicksort stable?

Answer 20

No

Question 21

What provides the best quicksort performance?

Answer 21

• choosing median as the pivot

Question 22

Which algorithm is quicksort similar to?

Answer 22

Merge Sort

Question 23

How does quicksort differ from merge sort?

Answer 23

• Quicksort splits based on the pivot. One section has smaller, other bigger. Merge sort splits in half.
• Merge compares upon combining 2 sections. Quicksort just combines the 2 sections, as one is greater, other smaller.
• Quicksort is in place, merge not.

Question 24

Quicksort schemes…

Answer 24

• choose middle
• choose median of three
• randon choice
• choose last

Question 25

Possible improvments?

Answer 25

- set a cut-off to insertion sort - tail recursion optimisation - iterative implementation - 3 way quicksort

Question 26

What data structure is heap sort based on?

Answer 26

A heap (min or max one)

Question 27

What is the complexity of heap sort?

Answer 27

O(nlogn) at all times

Question 28

How does heap sort work?

Answer 28

- we make the array into a min-heap structure - we extract max and place it at the end recursively, until end of structure is reached , upon removal we have to fix the min-heap by running a heapify function on the array

Question 29

What is a heap data structure?

Answer 29

A nearly completed binary tree, where parent is either greater or smaller then child, depending on whether is a min heap or a max heap. Root is therefore the min/max.

Question 30

What is the space complexity of heap sort?

Answer 30

O(1)

Question 31

Is heap sort stable?

Answer 31

No

Question 32

Is heap sort normally iterative?

Answer 32

Yes

Question 33

Formula for left child of a node in array implementation of heap data structure?

Answer 33

index * 2 +1

Question 34

Formula for right child of a node in array implementation of heap data structure?

Answer 34

index * 2 + 2

Question 35

Can a new level be started on a heap data strcutre without previous one being complete?

Answer 35

No

Question 36

What is min/max - heapify?

Answer 36

A function, which restores the heap property.