Brainscape's Knowledge GenomeTM

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


See full index

Algorithms and Data Structures > Sorting Algorithms > Flashcards

Sorting Algorithms Flashcards

1
Q

what are the different design approaches to sorting algorithms

A

brute force/exhaustive

decrease and conquer

divide and conquer

transform and conquer

dynamic programming

greedy

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

examples of brute force sorting algorithms

A

bubble sort

selection sort

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

when are the brute force sorting algorithms best

A

for small cases and simple situations

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

examples of the decrease and conquer algorithms

A

insertion sort

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

what does decrease and conquer involve

A

breaking down the problem into smaller problems and solving them

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

what are some examples of transform and conquer sorting algorithms

A

balanced search trees

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

what are some examples of divide and conquer algorithms

A

quick sort and merge sort

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

what does divide and conquer mean

A

split problem and solve separately usually recursively

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

what is dynamic programming

A

solves problems by combining the solution to subproblems

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

examples of dynamic programming

A

Warshall’s and Floyd’s shortest path algorithm

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

what are greedy algorithms

A

always make the choice that looks best in the moment

do not always yield the optimal solution but often does

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

examples of greedy programmin

A

Dijkstra shortest path

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

binary search is an example of what type of sorting algorihm

A

divide and conquer

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

what does it mean if an algorithm is stable

A

in the final sorted array, repeats of numbers stay in the same order that they were in the original array

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

which are examples of stable algorithms

A

insertion sort, bubble sort, merge sort

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

what does it mean if an algorithm is in place

A

no extra space is needed

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

when do we not care if the algorithm is stable

A

when equal elements are indistinguishable eg integers

if all the keys are different

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

when do we care about stability in sorting algorithms

A

when there are duplicate keys and we want to maintain original order

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

examples of the in place sorting algorithms

A

selection sort, insertion sort, shell sort, quick sort

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

how does insertion sort work

A
  • start from first element of the array
  • move it back until you find a smaller element
  • if you dont find a smaller element, it gets shifted all the way back to the 0th index
  • keep the LHS of the current index sorted and the RHS are the elements you are yet to sort
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

when is insertion sort useful

A

when arrays are small and almost sorted

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

best case input for insertion sort

A

almost sorted or already sorted

because it won’t require much swapping

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

what is the worst case input for insertion sort

A

a reverse order array

as every element will have to be moved the max number of times

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

what is the time complexity of insertion sort

A

O(n)

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

is insertion sort stable

A

yes

as it only moves one element at a time

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

is insertion sort in place

A

yes

it doesn’t use extra space

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

how does bubble sort work

A

compare elements adjacent to each other and swap if they are out of order

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

time complexity of bubble sort

A

O(n^2)

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

what is the best case input for bubble sort

A

array is sorted

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

what is the worst case input for bubblesort

A

array is sorted in reverse order

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

best case performance of bubblesort

A

n

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

is bubblesort in place

A

yes

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

is bubble sort stable

A

yes

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

how does selection sort work

A

in each iteration it finds the smallest remaining entry and swaps the current element with that one

LHS entries are sorted
RHS are unsorted

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

whats the maximum number of times an element will be swapped in selection sort

A

once

36
Q

worst case input for selection sort

A

sorted array

as it still has to compare all elements

37
Q

best case input for selection sort

A

sorted array

as no swaps

38
Q

time complexity of selection sort

A

O(n^2)

39
Q

is selection sort stable

A

no

40
Q

is selection sort in place

A

yes

41
Q

why might one use selection sort

A

minimises swaps which is good for memory

42
Q

how does shellsort work

A

take every nth entry and sort these,

keep reducing n until n = 1

43
Q

is shell sort stable

A

no

44
Q

is shell sort in plae

A

yes

45
Q

what is the best increment sequence to use for shellsort

A

3^k-1

eg 40, 13, 4, 1

46
Q

what is the best case for shellsort

A

sorted array

47
Q

what is the worst case for shell sort

A

array sorted in reverse order

48
Q

shell sort time complexity

A

O(n)

49
Q

in java arrays.sort what is used for primitive types

A

quick sort

50
Q

in java arrays.sort what is used for sorting arrays of objects

A

merge sort

51
Q

what are the two types of merge sort

A

iterative (bottom up) and recursive (top down)

52
Q

how does recursive merge sort work

A

divide array in two halves
sort these
merge

53
Q

how does bottom up (iterative) merge sort work

A

through merging arrays of size 1, 2, 4, 8 etc

54
Q

time complexity of merge sort

A

O(nLogn)

55
Q

space complexity of merge sort

A

O(n)

56
Q

is merge sort in place

A

no

it uses an extra array when merging

57
Q

what is typically the cutoff for merge sort when a simpler sorting algorithm is introduced

A

10 elements

58
Q

possible improvements for merge sort

A

stop if already sorted

59
Q

drawbacks of merge sort

A

not good for smaller tasks
goes through whole process even if sorted
not in place

60
Q

how does quicksort work

A
  1. shuffle array
  2. partition array around a pivot so that everything left of the pivot is less than it and everythihg right of it is greater than it
  3. Sort each array in this way recursively
61
Q

what are the different ways of picking a pivot element

A

median value

random

first element

62
Q

why is picking a random element as the pivot not ideal

A

need a random number generator

needs to know the largest element

63
Q

why is picking the median value of the list as the pivot not ideal

A

expensive to calculate

64
Q

when is picking the first element of the list as the pivot bad

A

if the first element is the smallest

there will never be any swaps, only reducing the array by one element at a time rather than halving it

65
Q

what is the worst case for quick sort

A

already sorted

all elements are the same

66
Q

how do we avoid the worst case for quick sort

A

shuffle array beforehand

67
Q

what is the time complexity of quick sort

A

O(nlogn)

68
Q

is merge sort stable

A

yes

69
Q

is merge sort in place

A

no

70
Q

time complexity of already sorted array quick sort

A

o(n^2)

71
Q

Insertion sort is an example of which algorithm design approach

A

decrease and conquer

72
Q

Which one of the sorting algorithms listed below is NOT stable?

insertion
Selection
Merge sort
All 3 are stable

A

selection sort

73
Q

What is the worst case input for standard quicksort, if the 1st element in the (sub)array is always used as a pivot?

A

already sorted array

74
Q

What is the worst case complexity for merge sort algorithm?

A

O(n log n)

75
Q

Which of the following algorithms, in its basic implementation, has space complexity of O(n)?

insertion sort
bubble sort
quick sort
merge sort

A

merge sort

76
Q

Given an array of 8 almost sorted integers, which of the following algorithms would be the most suitable to use to sort it?

Insertion sort
Merge sort
Quick sort
Bubble sort

A

insertion sort

77
Q 
Which one of the following sort algorithms is generally not implemented using recursion?
Most Signicant Digit Radix Sort
Least Signicant Digit Radix Sort
Merge sort
quick sort
A

Least Signicant Digit Radix Sort

78
Q 
Which of the following substring search algorithms does NOT require backup?
Knuth-Morris-Prath
Brute force approach
Boyer-Moore
all of the above require backup
A

Knuth-Morris-Prath

79
Q

Given an array of 100,000 Student objects, where Student consists of student_id, first_name, and last_name, which algorithm would be the most suitable to use to sort it?

A

merge

80
Q

What is recurrence for worst case of QuickSort

A

T(n) = T(n-1)

81
Q

Consider a situation where swap operation is very costly. Which sorting algorithm should be preferred so that the number of swap operations are minimized in general?

A

selection sort

makes at most n swaps

82
Q

What is the best time complexity of bubble sort?

A

O(N)

already sorted array

83
Q

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

A

insertion sort

84
Q

possible optimisation of bubble sort

A

add swapped boolean

at each iteration, if no elements were swapped this means that the elements are already sorted and another iteration is not neccessary

85
Q

how can shell sort be used to help insertion sort

A

by bringing elements closer to their proper sorted position

means less swaps when it comes to insertion sort

86
Q

Why is shell sort not stable

A

because this algorithm does not examine the elements lying in between the intervals

87
Q

Why is selexgion sort not stable

A

Selection sort works by finding the minimum element and then inserting it in its correct position by swapping with the element which is in the position of this minimum element. This is what makes it unstable

Algorithms and Data Structures (19 decks)

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