Sorts Flashcards
Internal need for sorting
Binary search
External need for sorting
Names in alphabetical order
What are total orders?
Assignment of an ordering to every pair of elements
What are partial orders?
Not an assignment for an ordering for every pair of elements
What is a sort algorithm?
The placement of a structure into the order induced by the sort order
How does an insertion sort work?
- walk along a list
- if value is larger than one of its left, do nothing
- if it is smaller, shuffle the elements to its left and insert it into the correct place
What is the average time for an insertion sort?
O(n^2)
What is the space for insertion sort?
O(1)
Describe the workings of a selection sort
- Search for the lowest value
- Swap it with the first element
- Continue from the second element
Average complexity of selection sort
O(n^2)
What are the three stages in a divide and conquer algorithm?
Divide
Recurse
Conquer
Describe the divide stage of divide and conquer
Take a problem S and split it into two smaller sub problems S1 and S2
Describe the recurse stage of divide and conquer
Recursively solve S1 and S2, either directly (by the base case) or by further division
Describe the conquer stage of divide and conquer
Combine the solutions to S1 and S2 into a solution to S
What type of algorithm is a merge sort?
Divide and conquer
Structural
Describe the divide stage for merge sort
Sorting n elements can be simplified into two problems sorting n/2 elements each
Describe the recurse stage for the merge sort
Base case - a problem of 1 element in solved other we can recursively divide
Describe the conquer stage for the merge sort
The sorted sub lists are merged into a single list
Where does the logarithmic complexity aspect come from in merge sort?
By definition, you can divide a list of length n in two logn times
What is the space complexity for merge sort?
O(n*logn)
What is the average time complexity for merge sort?
O(n*logn)
Where is memory reclaimed from as the merging process proceeds?
From the middle
What will each sequence of length n give rise to?
Exactly the same recursive structure
Benefits of merge sort
VERY predictable
Disadvantage of merge sort
Extra memory needed to hold intermediate results, held across the whole run
What type of sort is quick sort?
Value based
Describe how quick sort works
Splits the list based on heuristic choice of middle value and works to sort the sub lists
Which step is the trivial step in merge sort?
Split
Which step is the trivial step in quick sort?
Division
What is the pivot?
The value used to split the array in quick sort
What is the average complexity of quick sort?
O(n*logn)
What is the worst complexity of quick sort?
O(n^2)
What are the three ways we can choose our pivot?
- Last element
- Random element
- Median of three
Describe the median of three approach for choosing a pivot
Take first, last and middle element in sequence
Choose the median value
