Suppose that we consider an array A of n distinct integers that is "d-sorted" which will mean that every entry is guaranteed to be no more than a distance d from the position it would take if the array were sorted. For example, for a 1-sorted array A, the integer at index k, will move to one of {k-1,k,k+1} when the array is sorted.
For example [1 2 4 3 5 ] is 1-sorted, and [ 2 1 5 3 4 ] is 2-sorted as the ‘5’ needs to move 2 spaces.
Give algorithms, using pseudo-code, that can take as inputs the value d, and a d- sorted array A, and that gives as output a sorted array, and that are based upon each of:
Insertion sort
Bubble sort
For fixed but arbitrary constant d, the algorithms should run in time O(n).
E.g. for d=1 they should be O(n), for d=2 they should be O(n), etc.
You should justify why they are correct, and also justify that they are O(n).
Give a small example of their working with the 2-sorted array [ 2 1 5 3 4 ].
Describe and explain the conditions for a Binary tree to be a Binary search tree. Then explain the operation for deleting an element, justify why it is correct, and give its complexity as a function of the size and/or height of the tree.
Give a method that runs in O(n log n) and that will allow insertion of n elements from an array into a BST in such a way that the height of the tree is guaranteed to be O(log n).