Sorting Algorithms Flashcards
what are the different design approaches to sorting algorithms
brute force/exhaustive
decrease and conquer
divide and conquer
transform and conquer
dynamic programming
greedy
examples of brute force sorting algorithms
bubble sort
selection sort
when are the brute force sorting algorithms best
for small cases and simple situations
examples of the decrease and conquer algorithms
insertion sort
what does decrease and conquer involve
breaking down the problem into smaller problems and solving them
what are some examples of transform and conquer sorting algorithms
balanced search trees
what are some examples of divide and conquer algorithms
quick sort and merge sort
what does divide and conquer mean
split problem and solve separately usually recursively
what is dynamic programming
solves problems by combining the solution to subproblems
examples of dynamic programming
Warshall’s and Floyd’s shortest path algorithm
what are greedy algorithms
always make the choice that looks best in the moment
do not always yield the optimal solution but often does
examples of greedy programmin
Dijkstra shortest path
binary search is an example of what type of sorting algorihm
divide and conquer
what does it mean if an algorithm is stable
in the final sorted array, repeats of numbers stay in the same order that they were in the original array
which are examples of stable algorithms
insertion sort, bubble sort, merge sort
what does it mean if an algorithm is in place
no extra space is needed
when do we not care if the algorithm is stable
when equal elements are indistinguishable eg integers
if all the keys are different
when do we care about stability in sorting algorithms
when there are duplicate keys and we want to maintain original order
examples of the in place sorting algorithms
selection sort, insertion sort, shell sort, quick sort
how does insertion sort work
- 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
when is insertion sort useful
when arrays are small and almost sorted
best case input for insertion sort
almost sorted or already sorted
because it won’t require much swapping
what is the worst case input for insertion sort
a reverse order array
as every element will have to be moved the max number of times
what is the time complexity of insertion sort
O(n)
is insertion sort stable
yes
as it only moves one element at a time
is insertion sort in place
yes
it doesn’t use extra space
how does bubble sort work
compare elements adjacent to each other and swap if they are out of order
time complexity of bubble sort
O(n^2)
what is the best case input for bubble sort
array is sorted
what is the worst case input for bubblesort
array is sorted in reverse order
best case performance of bubblesort
n
is bubblesort in place
yes
is bubble sort stable
yes
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
whats the maximum number of times an element will be swapped in selection sort
once
worst case input for selection sort
sorted array
as it still has to compare all elements
best case input for selection sort
sorted array
as no swaps
time complexity of selection sort
O(n^2)
is selection sort stable
no
is selection sort in place
yes
why might one use selection sort
minimises swaps which is good for memory
how does shellsort work
take every nth entry and sort these,
keep reducing n until n = 1
is shell sort stable
no
is shell sort in plae
yes
what is the best increment sequence to use for shellsort
3^k-1
eg 40, 13, 4, 1
what is the best case for shellsort
sorted array
what is the worst case for shell sort
array sorted in reverse order
shell sort time complexity
O(n)
in java arrays.sort what is used for primitive types
quick sort
in java arrays.sort what is used for sorting arrays of objects
merge sort
what are the two types of merge sort
iterative (bottom up) and recursive (top down)
how does recursive merge sort work
divide array in two halves
sort these
merge
how does bottom up (iterative) merge sort work
through merging arrays of size 1, 2, 4, 8 etc
time complexity of merge sort
O(nLogn)
space complexity of merge sort
O(n)
is merge sort in place
no
it uses an extra array when merging
what is typically the cutoff for merge sort when a simpler sorting algorithm is introduced
10 elements
possible improvements for merge sort
stop if already sorted
drawbacks of merge sort
not good for smaller tasks
goes through whole process even if sorted
not in place
how does quicksort work
- shuffle array
- 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
- Sort each array in this way recursively
what are the different ways of picking a pivot element
median value
random
first element
why is picking a random element as the pivot not ideal
need a random number generator
needs to know the largest element
why is picking the median value of the list as the pivot not ideal
expensive to calculate
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
what is the worst case for quick sort
already sorted
all elements are the same
how do we avoid the worst case for quick sort
shuffle array beforehand
what is the time complexity of quick sort
O(nlogn)
is merge sort stable
yes
is merge sort in place
no
time complexity of already sorted array quick sort
o(n^2)
Insertion sort is an example of which algorithm design approach
decrease and conquer
Which one of the sorting algorithms listed below is NOT stable?
insertion
Selection
Merge sort
All 3 are stable
selection sort
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
What is the worst case complexity for merge sort algorithm?
O(n log n)
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
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
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
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
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
What is recurrence for worst case of QuickSort
T(n) = T(n-1)
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
What is the best time complexity of bubble sort?
O(N)
already sorted array
Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
insertion sort
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
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
Why is shell sort not stable
because this algorithm does not examine the elements lying in between the intervals
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
