# Data structures and Algorithms

kioria
In the problems below A[1, ..., n] denotes an array consisting of arbitrary n real numbers, and A[j] denotes the element in the j-th place of the array A[1, ..., n].

1) Let k be a fixed natural number. Consider the family $$A_{k}$$ of all arrays A[1, ..., n] satisfying that for every in there are at most k elements among A[1, ..., (i - 1)] larger than A[i]. Show that there exists a constant C such that every array A[1, ..., n] from $$A_{k}$$ can be sorted in time $$Cn$$.

nb. This seems like a simple question, I just need to adapt to the style of approaching these types of questions. Your help will be greatly appreciated.

Homework Helper
A0 can be sorted in C0n time for some constant C0 (obviously, C0 = 0). Assume Ak can be sorted in Ckn time. Take your Ak+1 list and do one iteration of a swap sort, taking Dk+1n time. You will be left with an Ak list, which you can proceed to sort in Ckn time. The task will be complete in Ck+1n = (Dk+1 + Ck)n time, as required.

Why does this swap give us an Ak list? Well if any given element has k or fewer elements preceeding it that are greater in value than it, then we don't care what the swap does. However, suppose an element has k+1 greater elements preceeding it. Suppose the element prior to it is greater. Well we know that the prior element has at most k greater elements preceeding it, otherwise if it had k + m elements greater preceeding it, then the element after it would have k + m + 1 greater elements, but we already said it only has k + 1 elements greater preceeding it. After we swap these two elements, the greater one will be on the right, and still have at most k elements preceeding it which are greater. The lesser of those two elements has had one of its k+1 greater preceeding elements moved behind it, so it's down to having only k elements greater than it preceeding it, so it looks like an Ak list.

What if the A has k+1 greater elements preceeding it, but A[i-1] < A (we just did the case with A[i-1] > A)? Well we know that A[i-1] then also has k+1 greater elements preceeding it. We can then look at A[i-2] and A[i-1]. If A[i-2] > A[i-1] then they will be swapped, and as above, they will be put in the right place to make the list an Ak list. We already assumed that A has k+1 greater elements preceeding it, and if A[i-2] were less than A, then there would be k+1 elements preceeding A[i-2] that are greater than A, and hence all those elements greater than A[i-1]. But then we'd also have A[i-2] itself which is greater than A[i-1] giving us k+2 elements greater than A[i-1], contradiction. So A[i-2] > A. Once A[i-1] and A[i-2] are swapped, A[i-2] will become A[i-1], and as we just showed, at this piont, A and A[i-1] will be swapped, thereby putting A in the right place.

Now assume that A[j+1] < A[j+2] < ... < A, but A[j] > A[j+1]. Then like above, we will do a bunch of swaps that will put the first i elements in the correct place to be an Ak list. I wrote the above in a rush. I'm pretty sure it's correct but it might be a little hard to follow. If it is, then it should be a good exercise for you to clarify the reasoning.

kioria
Ok I'm going to need some time for this. Will post back if I can't reason it. First paragraph seems understandable - rest I'll give it a try. Thanks.

kioria
The $$C_{k}$$ tends to increase dramatically as the input changes, say from well sorted array to totally reversed array. For example:

$$A_{1}$$ = {1,2,7,3,4,5,6} : C = 4
$$B_{3}$$ = {1,6,5,4,2,3,7} : C = 9, that is almost double the number of swaps.

What accounts for these? (Unless I totally misunderstood the concept)

Homework Helper
Consider the 1-array {7,1,2,3,4,5,6} and the 6-array {7,6,5,4,3,2,1}. Both will require 6 swaps. I actually have no idea how you could have had 9 swaps for B3. On the other hand, the 1-array {1,2,3,4,5,7,6} requires 1 swap. As the characteristic number of the array (the characteristic number of Ak is k) increases, the average number of swaps required for one sift through the array will naturally increase. In a 6-array, the number of swaps will always be 6. In a 1-array, you get anywhere from 1 to 6, and you can use combinatorics to find the precise expected number of swaps. You can do the same for the general k-array, but you don't need to do this.

Note that the algorithm I gave asks for only one sift through with the swap, you don't complete an entire swap sort. Well actually, you may indeed end up with a swap sort because to sort a (k+1)-array you do one sift, and then do whatever would be done for a k-array. If the algorithm for the k-array happens to be a swap sort, then you would end up doing a swap sort. However, with your B3 you would do:

{1,6,5,4,2,3,7} --> {1,5,4,2,3,6,7}

It's actually been quite a while since I've done this, so I don't know if the terminology is right. The above shows one sift through with the swap, and no matter what your array looks like, this will ensure that the largest element is at the end, and if I remember correctly, that's like what the bubble sort does, so maybe I should be calling this a bubble sort. If you were to continue with this type of sort (whatever it may be called) you would get:

{1,5,4,2,3,6,7} --> {1,4,2,3,5,6,7} --> {1,2,3,4,5,6,7}

However, my algorithm says simply to do one iteration so you have {1,5,4,2,3,6,7} then do whatever you'd do for a 2-array in C2n time and you'll end up with {1,5,4,2,3,6,7}. You don't need to know what is done for a 2-array, you just make the (inductive) assumption that whatever is done does the task in C2n time.

Now that I think about it, this is indeed a swap sort. What you do for Ak+1 is one swap, plus whatever you do for Ak. But for Ak, you do one swap, plus whatever you do for Ak-1... eventually you have to solve an A2, where you do a swap, plus whatever you do for an A1, and to solve that, you do a swap, plus whatever you do for an A0, which is nothing. So yes, it's a swap sort.

Suppose each swap takes t time. Suppose for one sift you have to swap every pair you come across, that being n-1 pairs. If you have an Ak array, you'll have to do the swapping k times until you bring it down to an A0. So the total time will be:

kt(n-1) < (kt)n

so if you let Ck = kt, then any k-array can be done in Ckn time.

Homework Helper
In case it hasn't been clear, it is a proof by induction. Show that you can solve any A0 array in at most C0n time for some constant C0. You should be able to see how this is obvious, and that constant C0 is just 0. Next, you assume inductively that any Ak array can be solved in at most Ckn time for some constant Ck. Finally, you want to show that there is some constant Ck+1 such that any Ak+1 array can be solved in at most Ck+1n time. I suggested that you show this by showing that if you reduce any Ak+1 array to an Ak array, then proceed to do whatever it takes to solve the Ak array in Ckn time, that the total time taken by those two subtasks (1. the reduction to Ak, and 2. the sorting of the Ak array) is at most Ck+1n for some constant Ck+1.

If you can convince yourself that a) going through the list once, from left to right, and swapping whenever an element preceeds a smaller element reduces an Ak+1 list to an Ak list, and b) the reduction process takes at most Dk+1n time for any Ak+1 list, then you can tell that the total time to sort the Ak+1 list is at most:

Dk+1n + Ckn = (Dk+1 + Ck)n

Letting Ck+1 = Dk+1 + Ck, you see that Ck+1 is clearly a constant, and any Ak+1 can be solved in at most Ck+1n time.

The ideas labelled a) and b) are the key things to prove, and b) is quite simple. Can you prove them? Once you do that, can you put it all together? I've basically spelled out how to put it all together above, so that really shouldn't be a problem unless I was unclear.

kioria
Thanks AKG, its very clear.