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