Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms & Data Structures 2 > Comparison Algorithms > Flashcards

Comparison Algorithms Flashcards

1
Q

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

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Is insertion in-place?

A

Insertion sort is in-place.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Best time to use insertion sort?

A

When there is a small number of elements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Is insertion sort stable?

A

Yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How does insertion sort work?

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Is merge sort , divide and conquer based?

A

Yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the merge sort Big-Oh complexity?

A

O(nlogn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How does merge sort work?`

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the memory requirement of MERGE?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Yes, but stability is lost.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Is merge-sort in place?

A

No

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Some possible improvements for merge sort?

A
  • iterative implementation

- use insertion-sort on small sections of array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the best Big-Oh complexity of quicksort?

A

O(nlogn)

17
Q

What is the worst Big-Oh complexity of quicksort?

A

O(n^2)

18
Q

How does quicksort operate?

A
  • 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
19
Q

Is quicksort in place?

A

Yes

20
Q

Is quicksort stable?

A

No

21
Q

What provides the best quicksort performance?

A
  • choosing median as the pivot
22
Q

Which algorithm is quicksort similar to?

A

Merge Sort

23
Q

How does quicksort differ from merge sort?

A
  • 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.
24
Q

Quicksort schemes…

A
  • choose middle
  • choose median of three
  • randon choice
  • choose last
25
Q

Possible improvments?

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

What data structure is heap sort based on?

A

A heap (min or max one)

27
Q

What is the complexity of heap sort?

A

O(nlogn) at all times

28
Q

How does heap sort work?

A
  • 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
29
Q

What is a heap data structure?

A

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.

30
Q

What is the space complexity of heap sort?

A

O(1)

31
Q

Is heap sort stable?

A

No

32
Q

Is heap sort normally iterative?

A

Yes

33
Q

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

A

index * 2 +1

34
Q

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

A

index * 2 + 2

35
Q

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

A

No

36
Q

What is min/max - heapify?

A

A function, which restores the heap property.

Algorithms & Data Structures 2 (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions