Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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
is insertion sort stable
yes | as it only moves one element at a time
26
is insertion sort in place
yes | it doesn't use extra space
27
how does bubble sort work
compare elements adjacent to each other and swap if they are out of order
28
time complexity of bubble sort
O(n^2)
29
what is the best case input for bubble sort
array is sorted
30
what is the worst case input for bubblesort
array is sorted in reverse order
31
best case performance of bubblesort
n
32
is bubblesort in place
yes
33
is bubble sort stable
yes
34
how does selection sort work
in each iteration it finds the smallest remaining entry and swaps the current element with that one LHS entries are sorted RHS are unsorted
35
whats the maximum number of times an element will be swapped in selection sort
once
36
worst case input for selection sort
sorted array as it still has to compare all elements
37
best case input for selection sort
sorted array as no swaps
38
time complexity of selection sort
O(n^2)
39
is selection sort stable
no
40
is selection sort in place
yes
41
why might one use selection sort
minimises swaps which is good for memory
42
how does shellsort work
take every nth entry and sort these, | keep reducing n until n = 1
43
is shell sort stable
no
44
is shell sort in plae
yes
45
what is the best increment sequence to use for shellsort
3^k-1 | eg 40, 13, 4, 1
46
what is the best case for shellsort
sorted array
47
what is the worst case for shell sort
array sorted in reverse order
48
shell sort time complexity
O(n)
49
in java arrays.sort what is used for primitive types
quick sort
50
in java arrays.sort what is used for sorting arrays of objects
merge sort
51
what are the two types of merge sort
iterative (bottom up) and recursive (top down)
52
how does recursive merge sort work
divide array in two halves sort these merge
53
how does bottom up (iterative) merge sort work
through merging arrays of size 1, 2, 4, 8 etc
54
time complexity of merge sort
O(nLogn)
55
space complexity of merge sort
O(n)
56
is merge sort in place
no it uses an extra array when merging
57
what is typically the cutoff for merge sort when a simpler sorting algorithm is introduced
10 elements
58
possible improvements for merge sort
stop if already sorted
59
drawbacks of merge sort
not good for smaller tasks goes through whole process even if sorted not in place
60
how does quicksort work
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
what are the different ways of picking a pivot element
median value random first element
62
why is picking a random element as the pivot not ideal
need a random number generator | needs to know the largest element
63
why is picking the median value of the list as the pivot not ideal
expensive to calculate
64
when is picking the first element of the list as the pivot bad
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
what is the worst case for quick sort
already sorted | all elements are the same
66
how do we avoid the worst case for quick sort
shuffle array beforehand
67
what is the time complexity of quick sort
O(nlogn)
68
is merge sort stable
yes
69
is merge sort in place
no
70
time complexity of already sorted array quick sort
o(n^2)
71
Insertion sort is an example of which algorithm design approach
decrease and conquer
72
Which one of the sorting algorithms listed below is NOT stable? insertion Selection Merge sort All 3 are stable
selection sort
73
What is the worst case input for standard quicksort, if the 1st element in the (sub)array is always used as a pivot?
already sorted array
74
What is the worst case complexity for merge sort algorithm?
O(n log n)
75
Which of the following algorithms, in its basic implementation, has space complexity of O(n)? insertion sort bubble sort quick sort merge sort
merge sort
76
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
insertion sort
77
``` 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 ```
Least Signicant Digit Radix Sort
78
``` 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 ```
Knuth-Morris-Prath
79
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?
merge
80
What is recurrence for worst case of QuickSort
T(n) = T(n-1)
81
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?
selection sort | makes at most n swaps
82
What is the best time complexity of bubble sort?
O(N) | already sorted array
83
Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
insertion sort
84
possible optimisation of bubble sort
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
how can shell sort be used to help insertion sort
by bringing elements closer to their proper sorted position means less swaps when it comes to insertion sort
86
Why is shell sort not stable
because this algorithm does not examine the elements lying in between the intervals
87
Why is selexgion sort not stable
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.
© 2025 Bold Learning Solutions. Terms and Conditions