How Can Arrays with Limited Larger Elements Be Efficiently Sorted?

[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 i ≤ n 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.

 

[AKG]

A₀ can be sorted in C₀n time for some constant C₀ (obviously, C₀ = 0). Assume A_k can be sorted in C_kn time. Take your A_k+1 list and do one iteration of a swap sort, taking D_k+1n time. You will be left with an A_k list, which you can proceed to sort in C_kn time. The task will be complete in C_k+1n = (D_k+1 + C_k)n time, as required.

Why does this swap give us an A_k 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 A_k 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 A_k 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 A_k 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)

 

[AKG]

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 B₃. 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 A_k 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 B₃ 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 C₂n 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 C₂n time.

Now that I think about it, this is indeed a swap sort. What you do for A_k+1 is one swap, plus whatever you do for A_k. But for A_k, you do one swap, plus whatever you do for A_k-1... eventually you have to solve an A₂, where you do a swap, plus whatever you do for an A₁, and to solve that, you do a swap, plus whatever you do for an A₀, 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 A_k array, you'll have to do the swapping k times until you bring it down to an A₀. So the total time will be:

kt(n-1) < (kt)n

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

 

[AKG]

In case it hasn't been clear, it is a proof by induction. Show that you can solve any A₀ array in at most C₀n time for some constant C₀. You should be able to see how this is obvious, and that constant C₀ is just 0. Next, you assume inductively that any A_k array can be solved in at most C_kn time for some constant C_k. Finally, you want to show that there is some constant C_k+1 such that any A_k+1 array can be solved in at most C_k+1n time. I suggested that you show this by showing that if you reduce any A_k+1 array to an A_k array, then proceed to do whatever it takes to solve the A_k array in C_kn time, that the total time taken by those two subtasks (1. the reduction to A_k, and 2. the sorting of the A_k array) is at most C_k+1n for some constant C_k+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 A_k+1 list to an A_k list, and b) the reduction process takes at most D_k+1n time for any A_k+1 list, then you can tell that the total time to sort the A_k+1 list is at most:

D_k+1n + C_kn = (D_k+1 + C_k)n

Letting C_k+1 = D_k+1 + C_k, you see that C_k+1 is clearly a constant, and any A_k+1 can be solved in at most C_k+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.